再谈Redis

  
  redis的hash/key lookup的实现就是在redis.c的lookupKey里.
  里面除了hash的查找过程dictFind之外,还有一些关于swap/vm的内容.
  暂且按下不表.
  
  redis的hash表"实现"是dict这个数据结构,在dict.h里定义.

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

  可以看出,redic是用了两个数组做hash table.
  
  至于为什么要用两个hash tbale,这个可以从dictRehash函数里看出.
  在做rehash的时候,其实是把ht[0]的所有内容移到ht[1].然后再把两者交换而已.
  
  至于什么时候以及为什么要rehash,一般是在查key的entry的时候,也就是_dictKeyIndex这个拿table index的时候,会看当前table里元素的大小.
  扩容的策略很简单,double.

  接下来看下table的分布情况.
  对于key计算出来的hash值,_dictKeyIndex先会将其跟table的sizemask做一个掩码.
  sizemask的值其实是table的"size" -1.
  
  由于table是按幂级数扩容的,于是sizemask上基本就是说,保留hash值的低级位的bit而已.

  得到计算出来的掩码之后,就以这个计算出来idx作为table的index.
  
  事实上,hash table数组里的值是一个链表.
  
  换句话说,其实redis hash table的分布方式类似内存的分页.

  用sizemask找出key所在的页,然后直接loop这个页的内容.
 
  于是,单对查找时间来衡量的话,当然是页内的东西越少查找越快了(因为是线性查找).
  换句话说,对于32bit的hash值,出去sizemaske的bit越多,查找理论上会越快.
  也就是说,当table越大,hash表越大的时候,查找效率会越高.
  当然,这也只是理论上的.
  
  而且,是在一定数量范围内才成立.

  因为redis毕竟是基于内存的,当数量超过可用内存的时候,自然效率不能担保.
  还有就是redis做save的时候(save到硬盘是通过fork clone一个进程做到的),也会占用一部分.

  所以,在处理redis的时候,需要考虑好内存的使用状况.
  不然out of memory的问题就麻烦了.

  至于redis的vm选项,貌似当开启的时候,不是用的内存而是用的swap或者说文件来存储的.
  这个可以在 lookupKey里看出点端倪.

  但vm选项开启,并且,第一次lookup出来的值没有REDIS_VM_MEMORY标记的时候,是从文件load进来的.

  至于,什么时候swap出去的嘛.
  还没看明白.

浅谈Redis

 
  redis的源代码(v1.3.14)应该算是挺简单的.
  "核心"部分就在redis.c,大概也就1W多行,不多.
  除去各种命令的处理,整体框架只有几千行吧.

  基本的处理流程在aeMain里.

  当然,在此之前,会先load数据.
  毕竟,这是一个基于基于内存的key-value.
  也所以呢,这成为它的第一个问题.
 
  appendonly模式下,是通过读log来恢复数据的.
  实际上,log的内容大概就是命令的内容,制造了一个fackeclient将log的内容重放一边.

  在非appendonly模式下,则是读数据文件,一个个都add回去.

  两者的不同在于,明显,非appendonly的文件必然是某个时期的数据快照.
  而log,只能说是某一段时间的数据操作过程吧.

  也就是说,如果停机回复的话,大概在log和数据文件上要小心处理.
  当然,省事的情况就是只load快照文件.

  不管是何种情况,可以肯定的一点是,启动时间跟数据量成正比.
 
  启动完成之后会在aeMain里面loop.
 
  redis是事件风格的,或者说是poll风格的.
  也就是说,每个命令会形成一个事件,然后如队列.
  在一次循环过程中poll出来处理.
  完了再下一次的从队列里select ready的event.


void aeMain(aeEventLoop *eventLoop) {
    eventLoop->stop = 0;
    while (!eventLoop->stop) {
        if (eventLoop->beforesleep != NULL)
            eventLoop->beforesleep(eventLoop);
        aeProcessEvents(eventLoop, AE_ALL_EVENTS);
    }
  }


  处理的基本主题在aeProcessEvents里.
  当然,更直接的是在aeApiPoll里.
  
  apiPoll里面会涉及到具体的socekt操作.
  其实也并不复杂,就是把ready的file descriptor放到read write的ready列表里.然后设置相应的事件标记.
  剩下的只是返回一个ready的数量,其余的依然在aeProcessEvent里.

  值得注意下的是,其实apiPoll有三个实现,通过宏控制.
  对应的其实就是通常io的三个基本模型,select,epoll,kqueue.

  不仅仅apipoll
. 所有aeApi族的函数都相对应于三个版本.
  
  某种程度上说,这其实是api族函数其实是跟io相关的底层调用.
  
  值得注意的是,在apipoll里面,只是准备好fd,实际的read write实在processevent里做的.
  更实际的get set等操作,其实是在更早之前的beforeSleep里.

  也就是eventloop那一段.
  
  实话,beforeSleep这个名字多少有些不恰当.
  因为它并不sleep,相反,还做了挺多事情.
  
  核心的redis命令执行入口call()就是在这里调用的.

  一个while循环各个ready的client.
  
  对于每个client,尝试取一个command来执行,调用call.
  完了之后,如果还有堆积的命令则调用processInputBuffer,有里面的processCommand做未竟的事业.
  等所有client处理完了,则会根据参数配置,看是否对log做一次flush操作.
  
  注意到这一个过程是单进程单线程的.
  考虑到client很多,并且请求很多的话,恐怕数据的顺序就不好说了.
  
  运气好的api call,恰好在靠前的client队列里,那自然就在log里比较靠前了.
  一种理论上的极端情况是,两个并发写同一个key值,先发起的也许由于机遇问题,分在了靠后的client的话,那么,不管你早多少,事实上先写到库的是后发的那个连接.
  某种程度上说,这靠的不是先天,而是后知后觉.

  所以,目前来看,redis在高并发的时候情况可能不会很乐观.

  连接数多,导致loop ready client处理api call的时候,靠后的client在时序上靠后了.
  理论上,不能保证比较强的时序性.

  其次就是每次loop 完rady client之后的写操作.
  尽管,通过参数配置,可以让它隔一段时间再写,但毕竟这是同步写过程,属于block io吧.
  而且,如果reids并发访问很高,那么加上loop ready client时所花费的时间,积累的log越多,block io的时间会越来越长吧.
  
  当然,这只是纯纸上谈兵.实际如何,很难说.
  因为,怎样才算是高并发和高频读写呢,这个没有确切说法吧.
  
  至于各个readis命令的大致实现以及hash的内存策略问题,有空再谈谈.
  其实也挺简单的.