Redis的数据模型和最终一致性

原文:http://antirez.com/news/36

作者:Antirez weblog

最近我注意到Amazon Dynamo的设计和它的原稿,可以说是数据库领域的最有趣的事情之一,Redis的最终一致性从来没有特别讨论过。

Redis的集群实例,系统更偏向一致性而非可用性。 Redis的哨兵(Sentinel)本身是具有一致性目标和Master/Slave部署的HA解决方案。

偏向一致性超过可用性,具有最终一致性的确有一些很好的理由,我大致可概括一下三点:

1)Dynamo设计部分依赖于写入而不是修改值的方法,除了重写一个全新的值。在Redis的数据模型中,大多数的操作是修改现有值。

2)另外Dynamo对值的大小进行了约定,即应限制在1MB左右。 Redis的Key可以容纳多个百万元素的聚合数据类型。

3)当Redis的集群规范制定好的时候,已经有相当数量的最终一致性的数据库正在开发,或者已经实现。我的猜测是,提供一个不同权衡的分布式系统可以惠及更多的用户群,提供了一个不拘泥流行特性的选择。

不过我每次介绍Redis的一个新版本时,我需要一些时间来解释新的想法,或者说,我从来不认为是可行的思路。MIGRATE, DUMP和RESTORE命令的引入,Lua脚本的支持,和设置毫秒级过期的能力,这些使得Redis创建客户端集群第一次变得如此容易。

所以我花了几个小时的时间来验证Redis的数据模型的想法,不需要修改Redis服务器本身而构建出一个最终一致性的集群。这是相当有趣的,在这个博客中我分享一些有关该话题的发现和想法。

分区

===

在Dynamo设计中数据分区使用一致性哈希。

写入数据被传输到N个节点中的优先级列表(preference list),如果有不可用的节点,使用下一个节点。

读取使用N+M个节点,以达到优先级列表(preference list)外的节点,并负责哈希环(hash ring)的修改(例如增加一个新的节点)。

在我的Redis-rb客户端分布式测试中我使用了一致的散列实现,为了我的需要稍做修改。

===

写操作被执行发送相同的命令给优先级列表中的每一个节点,一个接一个地并且跳过不可用的节点。

写的过程中,不执行任何跨节点锁定,所以读取时可能会发现仅仅一个节点的子集的更新。这个问题在读取时被处理。通常在客户端设计中,大部分的复杂性是在读取端。

当执行写入或读取时,不可用节点(用户配置的超时后未响应)从下一个请求被临时暂停持续一个配置的时间值(例如一分钟),以避免为每个请求增加延迟。在我的测试中,在N个连续的错误后我使用一个简单的错误计数器来暂停该节点。

===

读操作发送相同的命令给在优先级列表中的每个节点,以及一定数量的附加连续节点。

读操作有两类:

1 )主动读取操作。在此类读取中,来自不同节点的结果被比较,以检测可能的不一致性,在可能的情况下将触发一个合并操作。

2 )被动读取操作。为了返回最合适的结果,该操作中不同的答复被简单地过滤,而不会触发合并。

例如GET是一个主动读操作,如果在结果中发现不一致则可以触发一个合并操作。

ZRANK取而代之的是一个被动的读操作。被动读操作使用一个依赖于命令的胜出者结果选择。例如在ZRANK的具体情况下各个节点之间的最常见的应答被返回。在每一个节点返回一个不同排名(rank)的指定元素的情况下,返回最小的排名(rank)(带有minor 整数值) 。

不一致检测

===

在读取时同时,以一个类型和操作相关的方式进行不一致的检测。

例如GET命令检测字符串类型时,如果检查到所关联的节点返回的结果中至少有一个值与其它值不同,则说明存在不一致。

然而,在高写入负载的情况下很容易看到一个GET可能只发现传播到节点的子集的部分写入。在这种情况下应该不会被检测到不一致,以避免无用的合并操作。

解决这个问题的方法是在更新非常接近时(不到几毫秒)忽略差异。我在Redis2.6实现了这样一个系统,使用PSETEX命令创建了一个生存大约数毫秒时间的Key。

所以字符串类型实际的不一致检测用下列两个测试执行:

1)一个或多个值是不同的(包括不存在的或有错误的类型)。

2)如果第一个条件为真,同样的节点都使用同一个Key的EXIST操作来探测对该Key最近的修改。只有当所有节点不一致返回false时操作被认为是有效的,合并操作才被触发。

对于这个系统,该系统库中的SET命令的实现在发送实际的SET命令之前应该使用PSETEX命令。

不一致的聚合数据类型

===

更复杂的数据类型使用更复杂的不一致性检测算法,以及使用值级别的短生命Key来作为最近的变化信号。

例如作为Set类型,SISMEMBER是一个主动读操作,如果以下两个条件都为真,则说明检测到不一致。

1)对应SISMEMBER中集合内的特定值至少一个节点返回不同的结果。

2)在任何所涉及的节点中最近没有添加或从该集合中移除值。

合并(Merge)操作

===

在我看来合并阶段是实验中最有趣的部分,因为Redis的数据模型相比于Dynamo数据模型是不同的,更加复杂。

我使用类型相关的合并策略,数据库用户可以用它来选择不同的权衡取舍,以满足应用程序需要非常高的数据库写入可用性的不同需求。

*字符串使用的是最后写胜出合并。

*集合(Set)使用的是所有的版本冲突的并集合并。

*列表(List)的合并通过在头部和尾部两侧插入丢失值来试图保持插入顺序,一直遇到两侧的第一个正常值。

*哈希(Hash)的合并增加正常和不正常的域(fields),使用的是最近发生的不同的更新值。

*排序集(Sorted set),类似于一个集合合并。我没有做更多的验证,所以这是一个正在进行中的工作。

例如在亚马逊Dynamo文档中的购物车的具体例子将很容易使用Set类型来建模,这样旧的项可以恢复而不会丢失。

另一方面,针对关注顺序的事件,使用列表(list)更加合适。

在我的测试中,字符串,哈希值和列表元素的前面带一个二进制字节的8微秒时间戳,因此对于客户端时钟脉冲相位差这是个明智选择。

当执行客户合并操作时,Lua脚本是非常合适的。例如对旧的节点发送胜出值时,我用以下的Lua脚本:

   if (redis.call(“type”,KEYS[1]) ~= “string” or

        redis.call(“get”,KEYS[1]) ~= ARGV[1])

    then

        redis.call(“set”,KEYS[1],ARGV[2])

    end

因此只有当发现无效的旧版本时值才会被替换。

合并大值

===

在客户端集群中,合并大值的一个问题是,使用Redis vanilla API在客户端驱动两个大集合的合并可能耗费大量时间。

不过幸运的是使用DUMP,RESTORE和MIGRATE命令可以带来帮助。在Redis的不稳定分支中MIGRATE命令现在已经支持COPY和REPLACE选项,使得它在这种情况下更加有用。

举例来说,为了执行两个节点A和B中两个集合的并集操作,有可能只是使用临时Key从一个节点MIGRATE COPY(COPY意味着不删除源Key)集合到另外一个节点,然后调用SUNIONSTORE来完成这项工作。

MIGRATE是非常有效的,可以在较短的时间内传输大的Key,但是在Redis的集群本身,在这篇博客文章中描述的设计并不适用于大数目的大尺寸Key的应用程序。

结论

===

有许多未解决的问题和实现细节,这个博客帖子我省略了,但我希望提供一些背景作进一步实验。

我希望在未来几周或几个月内能尽最大的努力持续这项工作,但在这一点目前尚不清楚是否会达到可用库的形式,但是我很想看到可以使用的产品出现。

如果我有这项工作的消息我肯定会写一个新的博客文章。

    原文作者:wilbertzhou
    原文地址: https://blog.csdn.net/wilbertzhou/article/details/17320597
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞