August 8, 2017
如果人生没有看过一个数据库的源码，那与咸鱼有什么区别。
准确的说，我所会写的代码都是从别人那里看来的。但是我所会写的代码就那么点儿，实在不怎么拿得出手。刚好遇到这个源码只有2万多行的纯C语言的数据库项目，怎么都得读读，否则不敢说自己会写代码。
Redis 简介 # 在之前有一篇关于redis的简介和安装的文章，所以就不从宏观上介绍了。
与memcached相比有下面这几个特点：
Redis不仅仅支持简单的k/v类型的数据，同时还提供list，set，zset，hash等数据结构的存储。 Redis支持数据的备份，即master-slave模式的数据备份。 Redis支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用。 Redis可以实现主从复制，实现故障恢复。 Redis的Sharding技术： 很容易将数据分布到多个Redis实例中 GitHub地址
Redis是单线程的，运行在CPU的一个核上。所以在线程的思路上整个程序是很清晰的。我主要从代码中学习一些网络编程的方法，C语言数据结构的写法，内存操作。
在redis4.0.1中一共有600多个文件，包含了C文件、bash脚本、Lua脚本、tcl脚本，额，，还有一些没见过的东西。太菜了，连文件后缀都没见过。
但是这些并不都是redis的代码，在src/文件夹中可以看到只有120多个c文件，这些才是核心。600多个是包含了一些测试文件和单元测试等等。
Redis的数据结构 # redis对外提供的数据结构在上一篇中也都介绍过，这里带着介绍一下其内部实现的方式。
August 7, 2017
在redis中还有一个很奇怪的部分，Hyperloglog。看到这个东西后我的第一反应跟大多数人一样，这个日志的东西是干什么的？
然而这并不是日志，而是一个十分高深的玩意儿，他的主要功能是估算诸如一个集合中的不同元素的个数，也就是基数估计。
这个算法号称用1.5Kb内存为十亿对象计数。
下面就来看一下这个算法，其实我也没有完全搞懂这个算法的所有细节，就简单的介绍下就好了。
背景 # 我们有很多场景，需要计算一个MultiSet的基数，如统计网站的访问IP数量等。
传统做法 # 在传统的做法中，我们可以开辟一个数据表每次累加出来。但是这个开销无论从时间上还是空间上，当数据量变大以后会变得十分巨大。随着一个参数的增长所以整个系统的参数都应该在上升，也就是说整个数据库系统都在面临巨大的压力。这个时候如果还这样做就很不明智了。
BitMap # 后来就聪明点了，这个应该就是程序员想出来的。
就是把每个IP映射到一个内存bit上，出现了就置1，没出现就是0。然后统计一下个数就可以了，抑或一下嘛。但是这个在空间上只做了个常数优化，搞过ACM的都明白，常数优化不算优化。
Linear Counting # 这个算法就是一个有一定数学基础的程序员搞出来的。
将IP映射到m个内存bit上去，然后还是统计1的数量，但是用最大似然估计的方式来估计总数的大小。这个在数学上是说的通的。
算法要求映射函数符合均匀分布，那么当基数很大的时候可以用正态分布逼近二项分布，正态分布的期望的最大似然估计是样本均值。所以我们就用这个最大似然估计来统计这个基数。
但是这个理论在很多情况下会有很大的误差，并且其对于m的要求很多，所以其空间复杂度也没有优化到哪里去。
LogLog Counting # 这个时候你应该懂标题中的LogLog是什么意思了吧，并不是日志的意思，而是算法复杂度。
这个算法对于Hash函数有下面几个要求：
H的结果具有很好的均匀性，也就是说无论原始集合元素的值分布如何，其哈希结果的值几乎服从均匀分布（完全服从均匀分布是不可能的，D. Knuth已经证明不可能通过一个哈希函数将一组不服从均匀分布的数据映射为绝对均匀分布，但是很多哈希函数可以生成几乎服从均匀分布的结果，这里我们忽略这种理论上的差异，认为哈希结果就是服从均匀分布）。
H的碰撞几乎可以忽略不计。也就是说我们认为对于不同的原始值，其哈希结果相同的概率非常小以至于可以忽略不计。
H的哈希结果是固定长度的。
以上对哈希函数的要求是随机化和后续概率分析的基础。后面的分析均认为是针对哈希后的均匀分布数据进行。
这个算法的基础是伯努利试验以及其推论。
伯努利试验是说：一次实验的结果只有发生和不发生两种，重复做这个实验，直到结果发生为止，记录下实验的次数。
然后讲与我们这个算法的联系。 算法的思路前面还是差不多，先把每个元素都Hash到一个固定长度的二进制串。那么这些二进制串最高位1的位置就符合这个定义。每个串都是一个伯努利过程，最高位1的位置就是第一次事件发生的试验次数。
回到理论本身，理论本身并没有给出解决这个问题的结论。但是在其一些推论的公式中隐含了我们要求得的基数，也就是伯努利过程的数量。
由两个问题引出这个公式：
进行n次伯努利过程，所有投掷次数都不大于k的概率是多少？ 进行n次伯努利过程，至少有一次投掷次数等于k的概率是多少？ (公式回头补，页面不支持latex很鸡肋)
这两个公式我们考虑极限情况的时候，就会发现，n就在2^k附近。这个就做为n的粗略估计。
下面就是要做偏差修正了。
July 28, 2017
在做Redis页面控制台命令支持的过程中，对于Redis的GEO模块突然很感兴趣，不明白这个数据结构为什么突然就跟Set、Sorted Set一起出现了。然后发现这个数据结构居然是用来存地理位置信息的，很不简单，要看一下到底是什么幺蛾子。
Geo模块专用于存储地理位置信息，突出的有点是可以快速获取某一地理位置附近的相关位置信息。比如你要在某个地方找吃的，搜索附近2km的餐厅，后台使用的就是GeoHash的算法，Redis原生就支持这个数据算法结构，可见其应用场景支持非常丰富，有很大的应用空间。
GeoHash算法 # 其实这个原理是很简单的，对于地理位置信息，一般我们用经纬度来表示，这就将球面转换成了一个二维平面。在二维平面快速的定位一个位置并查找周围位置信息，就是这个算法解决的主要问题。、
传统的我们可能用一种树结构来搞，但是那样的时间效率和空间效率都不高。
GeoHash过程 # Geohash的主要过程就是将经纬度信息Hash成一个字符串。
将经纬度各自Hash成一个二进制串。 将两个串插叠，奇数位插维度串，偶数位插经度串。 将该串用base32进行编码生成字符串。 原理 # 在第一步中主要用二分的方法来Hash生成二进制串。例如对于维度：北纬30，其在北纬第一位设成1，由位于0-45所以第二位为0，这样一直做20次二分，就可以得到一个长度是20的串。 对于精度同样这样做一遍。
然后插叠得到一个长度为40的二进制串，然后用base32方式编码生成一个长度为8的字符串。
将这个字符串存下来就好啦。
Geohash特性 # 由过程可以看出来，这个Hash出来的字符串的特性，就是相同区域的两个点的Hash结果前缀一致。这样当我们要查找某个位置周围2km的餐厅只要匹配到字符串的前5位相同就可以了。
边缘误差 # 这个算法是存在边缘误差的，因为如果两个点相距的很近，但是在二分的过程中分在不同的两块中，这样的Hash结果就相差很大, 如下图中的红点位置与两个绿点位置。
解决这个问题的方式也很直观。
当我们在查找某一点周围的地理位置的时候，将其对应的周围8块区域的点都取出来，然后计算一下距离做个筛选就可以了。 这个区域的点并不会太大。
这些小算法还是很好玩的。
July 14, 2017
redis 是一个高速的高级的键值对存储系统。开源的，高可用，高效。 其将数据完全保存在内存中，磁盘只做持久化。并且支持多种数据结构：list、set、hashtable等，使用方便。 使用的场景主要有:
如排行榜、计数器缓冲、数据统计（如TopN，交集，并集等）、最新项目检索、地理位置存储及range查询 实时统计和过期处理，如用户投票及排序；复杂的数据结构缓存及内存数据库 缓存，消息队列(Redis本地支持发布/订阅)，应用程序中的任何短期数据，例如，web应用程序中的会话，网页命中计数等。 由于其属于内存数据库，所以成本比较大，冈起来比较爽一点。
Install on Ubuntu # sudo apt-get install redis-server Startup # redis-server Work on it # redis-cli # 出现命令提示符即正常工作 支持的数据结构 # 正时因为支持这些数据结构才易用。
字符串 # Redis中的字符串是一个字节序列。Redis中的字符串是二进制安全的，这意味着它们的长度不由任何特殊的终止字符决定。因此，可以在一个字符串中存储高达512兆字节的任何内容。
set name `Paladnix` # 存入key-value get name # 获取key对应的value Hash散列 # Redis散列/哈希(Hashes)是键值对的集合。Redis散列/哈希是字符串字段和字符串值之间的映射。因此，它们用于表示对象。
HMSET key uname "Paladnix" password "123" level 0 # key 对应一个对象 列表List # Redis列表只是字符串列表，按插入顺序排序。可以向Redis列表的头部或尾部添加元素。
lpush alist redis # 插入字符串 lpush alist Paladnix # 插入字符串 lrange alist 0 10 # 获取字符串 集合Set # Redis集合是字符串的无序集合。在Redis中，可以添加，删除和测试成员存在的时间O(1)复杂性。
...