The 4k Story

从 Redis 2.0 开始,Redis的作者就不断地被问道,你为什么要自己造一个VM轮子呢。尽管作者在FAQ里说明了,但是仍然有很多不同意见。

反向代理Varnish的开发人员,Poul-Henning Kamp 写了一篇文章,What’s wrong with 1975 programming ?,锋芒毕露,矛头直指竞争对手Squid,顺便也打击一大片牵连到了Redis的作者Antirez。他说:

I have spent many years working on the FreeBSD kernel, and only rarely did I venture into userland programming, but when I had occation to do so, I invariably found that people programmed like it was still 1975.

Kamp兄有来到user-space之后一夜回到解放前的感觉,又好像摇晃着饮料瓶子对着Antirez说:你Out啦!也许是因为作者就是个内核开发者,所以Varnish对操作系统的Virtual Memory机制充分信任,把Squid对内存的手动管理称为wasted work。”So Welcome to Varnish, a 2006 architecture program. ”

还有用户也提出

Redis doesn’t use OS swap. According to Salvatore Sanfilippo, the creator of Redis, it was because the page size of 4KB was too big. I personally don’t think that helps but it’d be better if Redis preallocated specified amount of buffer pool and bring related objects to the same page to increase locality of reference, instead of letting the heap manager blindly fragment objects. In my opinion, the page size of 32 bytes is too small, considering that the hardware architectures and the compilers are optimized for the conventional page size. In that scale, even the latency of reading something from RAM could be dominant (RAM is too slow for CPU, therefore it’s got L1/L2 cache), and RAM has the pipelined burst mode to pre-fetche memory contents at a few clock cycles, before they are actually requested.

5号,Antirez在博客上写了回击 What’s wrong with 2006 programming?,他认为:

  • OS Swap在一些情况下会导致客户端阻塞
  • 4K大小的Page可能包含很多key,其中总有一些被访问到,导致操作系统无法swap这些page
  • 使用自己实现的Paging为程序提供了极大的自由度,包括作者提到的2.2将会引入的数据压缩、新的数据结构以及自定义的过期算法

前段时间,Foursquare用MongoDB时,因为Sharding方法一些疏漏把大量的数据集中到了一台机器上,导致一台EC2实例内存耗尽无法工作。Mongodb的内部机制就是mmap,我的同事做过相关的测试,当内存耗尽时,读写操作都使用磁盘,这时mongodb的性能是完全无法使用的。事后10gen的开发人员Horowitz总结出现问题的原因总结出现问题的原因时,其中很重要的一点是

Document size is less than 4k. Such documents, when moved, may be too small to free up pages and, thus, memory.

看了这个原因,Redis的作者Twitter上大喜:”Real world instance of my 4k page + small objects concerns”

Redis Data Struct

Redis的几个核心数据结构定义在redis.h和dict.h中。Redis服务器总的数据结构里的根节点是redisServer,下面包含一个redisDb结构数组。数组的大小定义在redis.conf中的databases项,客户端可以通过select命令选择相应的DB。

一个redisDb定义了redis数据库的基本数据结构,redisDb结构定义如下

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */
    dict *io_keys;              /* Keys with clients waiting for VM I/O */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;
} redisDb;

其中

  • dict 用于存储键值的哈希表结构
  • expires 用于存储键、过期时间的哈希表结构
  • blocking_keys 用于存储键、阻塞数据的哈希表结构。目前仅仅在阻塞式的blpop brpop中使用。
  • io_keys 存储等待将数据从swap读出的key (vmThreadedIOCompletedJob, dontWaitForSwappedKey, waitForSwappedKey)
  • watched_keys 用于支持WATCH命令,实现乐观锁功能
  • id 数据库编号

dict结构定义在dict.h中,主要的定义有:

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;

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

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;

每个dict中包含两个dictht结构,用来在rehash的时候进行数据交换。rehashidx用于记录rehash的进程,值是当前rehash的table索引。dictht中table二维数组,以hash值为索引。size是哈希表的大小,初始值是4,随着rehash的进行,变成大于size的最小2n。sizemask是size-1,用来与哈希值做&运算。

redis在引如virtual memory之前,就是以这样的数据结构运行在内存中的。

Redis

Redis是一个高性能Key-Value store

Installation

下载解压,make之后就可以直接启动./redis-server 默认读取当前目录下的redis.conf作为配置,亦可参数指定。默认监听6379端口。

Features

支持多种数据结构

相较memcached,redis支持多种数据结构,包括

针对每种数据结构,redis都提供比较完整的操作支持。

高性能

据Wiki上说可以达到110,000 SETs/second, 81,000 GETs/second,数据根据一定的策略存在内存和磁盘上(支持持久化)。从1.1开始支持append-only持久化方式,数据被加到文件中,并进行异步的维护,保证文件的大小。从2.0(即1.3)开始支持virtual memory,当内存占用超过配置文件中vm-max-memory时,数据被写入virtual memory。

Replication

redis支持主从复制,从而提供多台实例进行读操作,可以在slave的配置文件里配置master的地址。

Protocol

redis目前只有基于TCP的文本协议,与memcache类似,有一些改进。
客户端通常发送
命令 参数… 值字节数\r\n
值\r\n

服务端的返回,根据第一个字节,可以判断:

  • - 错误信息
  • + 普通文本信息
  • $ 变长字节数,$6表示CRLF之后有6个字节的字符
  • : 返回一个整数
  • * 返回组数,即*6表示CRLF之后将返回6组变长字符

其他

项目地址
http://code.google.com/p/redis/
http://github.com/antirez/redis/
开发者twitter
http://twitter.com/antirez
http://twitter.com/pnoordhuis

Redis功能简单精悍,很符合Unix哲学,核心redis.c只有一万多行,实在是个让人爱不释手的东西。如果可能,争取把他用到生产环境来取代现在的memcached。

The post is brought to you by lekhonee v0.7