再谈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出去的嘛.
  还没看明白.