Massive Technical Interviews Tips: Redis设计与实现

Friday, December 11, 2015

Redis设计与实现

http://blog.me115.com/2015/03/817

数据ACID特性满足了几条？
为了保持简单，redis事务保证了其中的一致性和隔离性；
不满足原子性和持久性；

原子性

redis事务在执行的中途遇到错误，不会回滚，而是继续执行后续命令；（违反原子性）

事务可以理解为一个打包的批量执行脚本，但批量指令并非原子化的操作；
中间某条指令的失败不会导致前面已做指令的回滚，也不会造成后续的指令不做；

持久性

事务不过是用队列包裹起了一组 Redis 命令，并没有提供任何额外的持久性功能，所以事务的持久性由 Redis 所使用的持久化模式决定：

在单纯的内存模式下，事务肯定是不持久的。
在 RDB 模式下，服务器可能在事务执行之后、RDB 文件更新之前的这段时间失败，所以 RDB 模式下的 Redis 事务也是不持久的。
在 AOF 的“总是 SYNC ”模式下，事务的每条命令在执行成功之后，都会立即调用 fsync 或 fdatasync 将事务数据写入到 AOF 文件。但是，这种保存是由后台线程进行的，主线程不会阻塞直到保存成功，所以从命令执行成功到数据保存到硬盘之间，还是有一段非常小的间隔，所以这种模式下的事务也是不持久的。
其他 AOF 模式也和“总是 SYNC ”模式类似，所以它们都是不持久的。

隔离性和一致性

redis事务在执行的过程中，不会处理其它命令，而是等所有命令都执行完后，再处理其它命令（满足隔离性）
redis事务在执行过程中发生错误或进程被终结，都能保证数据的一致性；（详见参考资料1)

redis事务的缺陷

除了不保证原子性和持久性，在实际使用中还有以下问题:

1）遇到有查询的情况穿插在事务中间，不会返回结果；
设置事务开始标志后，所有的命令都是queued，即使是查询指令；
如果后续的更新操作需要依赖于前面的查询指令，那redis事务就无法有效的完成任务；

2) 事务中的每条命令都与redis服务器进行了一次网络交互；
redis 事务指定开始后，执行一个事务返回的都是queued，那这个入队操作是在客户端实现，还是在服务器端实现的？
查看源码，很容易发现是在服务器端实现；
在Redis.c中有这么一段：

int processCommand(redisClient *c) {
...
    /* Exec the command */
    if (c->flags & REDIS_MULTI &&
        c->cmd->proc != execCommand && c->cmd->proc != discardCommand &&
        c->cmd->proc != multiCommand && c->cmd->proc != watchCommand)
    {
        queueMultiCommand(c); // 将事务中的命令都放入到队列中，然后返回"QUEUED"
        addReply(c,shared.queued);
    } else {
        if (server.vm_enabled && server.vm_max_threads > 0 &&
            blockClientOnSwappedKeys(c)) return REDIS_ERR;

        //调用该命令函数来处理命令
        call(c);
    }
    return REDIS_OK;
}

这里就涉及到客户端与服务器端的多次交互，明明是需要一次批量执行的n条命令，还需要通过多次网络交互，有些浪费；

http://blog.me115.com/2015/12/891
Redis的事件循环在一个线程中处理，作为一个单线程程序，重要的是要保证事件处理的时延短，这样，事件循环中的后续任务才不会阻塞；
当redis的数据量达到一定级别后（比如20G），阻塞操作对性能的影响尤为严重；

耗时长的命令造成阻塞

keys、sort等命令

keys命令用于查找所有符合给定模式 pattern 的 key，时间复杂度为O(N)， N 为数据库中 key 的数量。当数据库中的个数达到千万时，这个命令会造成读写线程阻塞数秒；
类似的命令有sunion sort等操作；
如果业务需求中一定要使用keys、sort等操作怎么办？

在架构设计中，有“分流”一招，说的是将处理快的请求和处理慢的请求分离来开，否则，慢的影响到了快的，让快的也快不起来；这在redis的设计中体现的非常明显，redis的纯内存操作，epoll非阻塞IO事件处理，这些快的放在一个线程中搞定，而持久化，AOF重写、Master-slave同步数据这些耗时的操作就单开一个进程来处理，不要慢的影响到快的；
同样，既然需要使用keys这些耗时的操作，那么我们就将它们剥离出去，比如单开一个redis slave结点，专门用于keys、sort等耗时的操作，这些查询一般不会是线上的实时业务，查询慢点就慢点，主要是能完成任务，而对于线上的耗时快的任务没有影响；

fork产生的阻塞

在redis需要执行耗时的操作时，会新建一个进程来做，比如数据持久化bgsave：
开启RDB持久化后，当达到持久化的阈值，redis会fork一个新的进程来做持久化，采用了操作系统的copy-on-wirte写时复制策略，子进程与父进程共享Page。如果父进程的Page（每页4K）有修改，父进程自己创建那个Page的副本，不会影响到子进程；
fork新进程时，虽然可共享的数据内容不需要复制，但会复制之前进程空间的内存页表，如果内存空间有40G（考虑每个页表条目消耗 8 个字节），那么页表大小就有80M，这个复制是需要时间的，如果使用虚拟机，特别是Xen虚拟服务器，耗时会更长；
在我们有的服务器结点上测试，35G的数据bgsave瞬间会阻塞200ms以上；

类似的，以下这些操作都有进程fork；

Master向slave首次同步数据：当master结点收到slave结点来的syn同步请求，会生成一个新的进程，将内存数据dump到文件上，然后再同步到slave结点中；
AOF日志重写：使用AOF持久化方式，做AOF文件重写操作会创建新的进程做重写；（重写并不会去读已有的文件，而是直接使用内存中的数据写成归档日志）；

解决方案：
为了应对大内存页表复制时带来的影响，有些可用的措施：

控制每个redis实例的最大内存量；
不让fork带来的限制太多，可以从内存量上控制fork的时延；
一般建议不超过20G，可根据自己服务器的性能来确定（内存越大，持久化的时间越长，复制页表的时间越长，对事件循环的阻塞就延长）
新浪微博给的建议是不超过20G，而我们虚机上的测试，要想保证应用毛刺不明显，可能得在10G以下；
使用大内存页，默认内存页使用4KB，这样，当使用40G的内存时，页表就有80M；而将每个内存页扩大到4M，页表就只有80K；这样复制页表几乎没有阻塞，同时也会提高快速页表缓冲TLB（translation lookaside buffer）的命中率；但大内存页也有问题，在写时复制时，只要一个页快中任何一个元素被修改，这个页块都需要复制一份（COW机制的粒度是页面），这样在写时复制期间，会耗用更多的内存空间；
使用物理机；

http://blog.me115.com/2015/11/884
一个hash表中的数据可能有几百上千万，不可能一次rehash转移完，需要分批逐渐转移；
在rehash的过程中，对redis的查询、更新操作首先会在hash0中查找，没有找到，然后转到hash1中操作；
对于插入操作，直接插入到hash1中；最终目标是将hash表1变为空表，rehash完成；
http://get.ftqq.com/522.get

1. 简单动态字符串sds

redis的字符串表示为sds，而不是C字符串（以\0结尾的char*）
对比C字符串，sds有以下特性
- 可以高效执行长度计算O(1)
- 可以高效执行append操作(通过free提前分配）
- 二进制安全
sds会为追加操作进行优化，加快追加操作的速度，并降低内存分配的次数，代价是多占用内存，且不会主动释放

这个一看名字就能知道个大概了，因为字符串操作无非是增删查改，如果使用char[]数组，那是要死人的，任何操作都是O(N)复杂度。所以，要对某些频繁的操作实现O(1)级性能。但是我们还是得思考：

为什么要对字符串造轮子？

因为redis是一个key-value类型的数据库，而key全部都是字符串，value可以是集合、hash、list等等。同时，在redis的各种操作中，都会频繁使用字符串的长度和append操作，对于char[]来说，长度操作是O(N)的，append会引起N次realloc。而且因为redis分为client和server，传输的协议内容必须是二进制安全的，而C的字符串必须保证是\0结尾，所以在这两点的基础上开发sds

知道了上面几点就可以看下实现了，其实实现特别简单。它通过一个结构体来代表字符串对象，内部有个len属性记录长度，有个free用于以后的append操作，具体的值还是一个char[]。长度就不说了，只在插入的时候用一下，以后只需要维护len就可以O(1)拿到；对于free也很简单，vector不也是这么实现的嘛。就是按照某个阈值进行翻倍叠加。

3. 字典（其实说Map更通俗）

字典是由键值对构成的抽象数据结构
redis中的数据库和哈希键值对都基于字典实现
字典的底层实现为哈希表，每个字典含有2个哈希表，一般只是用0号哈希表，1号哈希表是在rehash过程中才使用的
哈希表使用链地址法来解决碰撞问题
rehash可以用于扩展或者收缩哈希表
对哈希表的rehash是分多次、渐进式进行的

这个虽然说经常用，但是对于redis来说确实是重中之重。毕竟redis就是一个key-value的数据库，而key被称为键空间(key space)，这个键空间就是由字典实现的。第二个用途就是用作hash类型的其中一种底层实现。下面分别来说明。

键空间：redis是一个键值对数据库，数据库中的键值对就由字典保存：每个数据库都有一个与之相对应的字典，这个字典被称为键空间。当用户添加一个键值对到数据库（不论键值对是什么类型），程序就讲该键值对添加到键空间，删除同理。
用作hash类型键的其中一种底层实现：hash底层实现是通过压缩列表和字典实现的，当建立一个hash结构的时候，会优先使用空间占用率小的压缩列表。当有需要的时候会将压缩列表转化为字典

对于字典的实现这里简单说明一下即可，因为很简单。

字典是通过hash表实现的。每个字典含有2个hash表，分别为ht[0]和ht[1]，一般情况下使用的是ht[0],ht[1]只有在rehash的时候才用到。为什么呢？因为性能，我们知道，当hash表出现太多碰撞的话，查找会由O(1)增加到O(MAXLEN),redis为了性能，会在碰撞过多的情况下发生rehash，rehash就是扩大hash表的大小，从而将碰撞率降低，当hash表大小和节点数量维持在1：1时候性能最优，就是O(1)。另外的rehashidx字段也比较有看头，redis支持渐进式hash，下面会讲到原理。

下面讲一下rehash的触发条件：

当新插入一个键值对的时候，根据used/size得到一个比例，如果这个比例超过阈值，就自动触发rehash过程。rehash分为两种：

自然rehash:满足used/size >= 1 && dict_can_resize条件触发的
强制rehash:满足used/size >= dict_force_resize_ratio(默认为5)条件触发的。

思考一下，为什么需要两种rehash呢？答案还是为了性能，不过这点考虑的是redis服务的整体性能。当redis使用后台子进程对字典进行rehash的时候，为了最大化利用系统的copy on write机制，子进程会暂时将自然rehash关闭，这就是dict_can_resize的作用。当持久化任务完成后，将dict_can_resize设为true，就可以继续进行自然rehash；但是考虑另外一种情况，当现有字典的碰撞率太高了，size是指针数组的大小，used是hash表节点数量，那么就必须马上进行rehash防止再插入的值继续碰撞，这将浪费很长时间。所以超过dict_force_resize_ratio后，无论在进行什么操作，都必须进行rehash。

rehash过程很简单，分为3步：

给ht[1]分配至少2倍于ht[0]的空间
将ht[0]数据迁移到ht[1]
清空ht[0], 将ht[0]指针指向ht[1],ht[1]指针指向ht[0]

同样是为了性能（当用户对一个很大的字典插入时候，你不能让系统阻塞来完成整个字典的rehash。所以redis采用了渐进式rehash。说白了就是分步进行rehash。具体由下面2个函数完成：

dictRehashStep:从名字可以看出，是按照step进行的。当字典处于rehash状态(dict的rehashidx不为-1)，用户进行增删查改的时候会触发dictRehashStep，这个函数就是将第一个索引不为空的全部节点迁移到ht[1]，因为一般情况下节点数目不会超过5(超过基本会触发强制rehash），所以成本很低，不会影响到响应时间。
dictRehashMilliseconds:这个相当于时间片轮转rehash，定时进行redis cron job来进行rehash。会在指定时间内对dict的rehashidx不为-1的字典进行rehash

上面讲完了rehash过程，但是以前在组内分享redis的时候遇到过一个问题：

当进行rehash时候，我进行了增删查改怎么办？是在ht[0]进行还是在ht[1]进行呢？

redis采用的策略是rehash过程中ht[0]只减不增，所以增加肯定是ht[1]，查找、修改、删除则会同时在ht[0]和ht[1]进行。

Tips: redis为了减少存储空间，rehash还有一个特性是缩减空间，当多次进行删除操作后，如果used/size的比例小于一个阈值（现在是10%),那么就会触发缩减空间rehash，过程和增加空间类似，不详述了。

3. 跳跃表

跳跃表是一种随机化数据结构（它的层是随机产生的），查找、添加、删除操作都是O(logN)级别的。
跳跃表目前在redis的唯一用处就是有序集类型的底层数据结构之一（另外一个还是字典）
当然，根据redis的特性，作者对跳跃表进行了修改
- socre可以重复
- 对比一个元素需要同时检查它的score和member
- 每个节点带有高度为1的后退指针，用于从表尾方向向表头方向迭代

http://blog.me115.com/2014/08/720

http://db-engines.com/en/system/Memcached%3BNCache%3BRedis

http://docs.aws.amazon.com/AmazonElastiCache/latest/UserGuide/SelectEngine.Uses.html

Select Memcached if the following apply to your situation:

You need the simplest model possible.
You need to run large nodes with multiple cores or threads.
You need the ability to scale out/in, adding and removing nodes as demand on your system increases and decreases.
You need to partition your data across multiple shards.
You need to cache objects, such as a database.

Select Redis 2.8.x or Redis 3.2 (non-clustered mode) if the following apply to your situation:

You need complex data types, such as strings, hashes, lists, sets, sorted sets, and bitmaps.
You need to sort or rank in-memory data-sets.
You need persistence of your key store.
You need to replicate your data from the primary to one or more read replicas for read intensive applications.
You need automatic failover if your primary node fails.
You need publish and subscribe (pub/sub) capabilities—to inform clients about events on the server.
You need backup and restore capabilities.
You need to support multiple databases.

Select Redis 3.2 (clustered mode) if you require all the functionality of Redis 2.8.x with the following differences:

You need to partition your data across 2 to 15 node groups. (Cluster mode only.)
You need geospatial indexing. (clustered mode or non-clustered mode)
You do not need to support multiple databases.

Important

Redis (cluster mode enabled) cluster mode has the following limitations:

No scale up to larger node types.
No changing the number of node groups (partitions).
No changing the number of replicas in a node group (partition).

https://gist.github.com/Integralist/9c87172cb418e539dae0

When deciding between Memcached and Redis, here are a few questions to consider:

Is object caching your primary goal, for example to offload your database? If so, use Memcached.
Are you interested in as simple a caching model as possible? If so, use Memcached.
Are you planning on running large cache nodes, and require multithreaded performance with utilization of multiple cores? If so, use Memcached.
Do you want the ability to scale your cache horizontally as you grow? If so, use Memcached.
Does your app need to atomically increment or decrement counters? If so, use either Redis or Memcached.
Are you looking for more advanced data types, such as lists, hashes, and sets? If so, use Redis.
Does sorting and ranking datasets in memory help you, such as with leaderboards? If so, use Redis.
Are publish and subscribe (pub/sub) capabilities of use to your application? If so, use Redis.
Is persistence of your key store important? If so, use Redis.

https://systoilet.wordpress.com/2010/08/09/redis-vs-memcached/
http://www.infoworld.com/article/3063161/application-development/why-redis-beats-memcached-for-caching.html

https://hazelcast.com/use-cases/nosql/redis-replacement/