Yang Liu's blog

分布式系统之一致性与缓存技术

一致性(consistency)与局部性(locality)是分布式系统中致力于追求却又互相矛盾的两个目标。首先你必须保证数据在一定程度上一致,以保证计算逻辑的正确性;其次,你又希望数据离访问者越近越好,这样系统便能达到更好的性能。但要满足数据离各处分布的访问者都足够接近,就必然要求数据有多个本地缓存 – 这就让保持一致性的目标更难达到了。

所以说,当面对分布式系统的问题的时候,我们大多数时候是在面对一个权衡的问题。设计者需要根据应用的具体需求,决定系统需要保证何种 程度的一致性和局部性。

一致性

最终一致性 (eventually consistency)

最终一致性的要求比较低,它只要求当你做了某处修改之后,系统的其他部分,可能还会有一段时间访问到老的数据,但或早或晚地,它最终都 将看到最新的修改。一般来说,当这种数据不具备状态,或者没有时效性要求的时候, 最终一致性就足够用了。

大部分面向用户的系统都是最终一致性的,比如网盘,你在手机上修改了某个问题,在电脑端则可能要等个几秒甚至更长的时间才会更新到最后修改的状态。

最终一致性的实现非常简单,它只需要保证写数据的事件必定完成即可。当用户提出写数据请求时,首先系统将请求以日志的形式保存在持久化介质里(一般即硬盘),保证了此次修改的持久性(durability) 后,即可向用户返回操作成功。之后,系统再真正应用这次修改,并给所有其他的用户发送消息,通知这次修改。当发送失败则不断重试。这样或早或晚,这个修改就会普及到系统的所有角落。

当数据具备状态还使用最终一致性, 就极有可能产生问题。这种情况常常发生在系统内部。一个非常经典的例子,就是 Java 的线程模型:

举例:Java 线程模型

跨线程共享的变量只具备最终一致性,除非被 volatile 修饰

当你修改了某个共享变量的时候,变化并不是立刻体现到所有的子线程里的。线程系统将会给每个线程发送消息通知这个改变,线程在收到消息后才执行这个改变。线程模型并不对此过程做任何时间或同步的保证。由这个特性所引出的,就是经典的可见性(visibility) 问题了。

这个决定是出于性能考虑的。当然整个线程模型的提出也是出于性能考虑的。性能上的节省,带来的代价就是程序员对编写正确计算模型更多的责任。

严格一致性 (strict consistency)

反之,当新老数据共存有可能影响应用的正确性或可用性的时候,我们就必须用上严格一致性了。它保证了任意一次修改之后,所有的访问者都将立刻看到这个新的修改。这样的强要求当然带来了许多优秀的属性,但在接下来的分析中我们就会发现,它也同时带来了极大的性能损失。所以我们一般只在最需要的地方使用严格一致性。

下面以 Google 的分布式 Lock Service – Chubby 系统作为例子,描述在严格一致性的要求下,一次写数据操作是如何完成的。

撤销缓存 (invalidation)

当系统收到写请求时,它将首先向所有具备此位置数据缓存的用户发送撤销此位置缓存的消息。系统将等待所有的用户都回复操作成功之后才进入下一步。

由此我们知道,当这步完成的时候,我们可以保证,系统内部将不再保有旧数据的缓存。

执行更改 (commit)

同样的,系统首先将此次操作持久化地记录下来,接着真正执行操作。如果系统在记录日志后挂掉了,将会有从日志恢复的机构重新执行记录的动作。也就是说,只要硬盘没同时也挂了,被记录到日志里的修改就一定能最终被系统执行。

发送更改通知 (handle event propagation)

这一步对于保证一致性来说不是必须的,只是 Chubby 这个系统出于向后兼容的需要继续保有的一个功能而已。Chubby 在修改过后,将会向所有订阅了此位置修改的用户发送“数据已更改”的通知。

回复请求方

在完成上述操作并收到所有涉及用户的确认回复之后,系统才向写操作提出方返回操作成功的消息。在后面的讨论里,我们可以看到,其性能的损失除了往返通信的成本以外,更大的损失出现在通信异常时的超时等待上。

租约 (lease)

租约可以说是关于不可信信道内通信的“拜占庭将军”问题的一个最实际的解法。同时它还具备了通信两端失败各自独立(fails independently) 的特性。是非常适合于分布式系统的实现的。

简单地说,服务器与用户两端各自约定一个租约期限,各自拥有一个计时的时钟。为了维持通信,其中一方或者两方具有在租约期限内向对方续约的责任。当双方保证了租约一直续签,通信就一直延续。当租约续签失败的时候,双方亦各自保持此通信会话,直至此租约过期。此时,双方都将认为通信已中断,便可释放此会话的资源,用于服务其他的通信需求上了。

由于之前讲过的时钟的误差,实践上服务器将固定等待比用户租约稍长一些的时间,这样就避免了因为时钟误差和通信延迟导致的竞争条件了。这样的固定等更长时间的做法,其实也就等效于服务器拥有时间流速最慢的时钟。因为我们一般认为服务端有需要释放重用的资源,服务端具有最慢时钟,方可保证不出现竞争条件。

在前面的发送撤销缓存等待用户回复的讨论里,并没有提及当用户通信中断的情况。实际上大部分分布式系统就是使用这种租约的方式来处理此情况。在 Chubby 里,如果通信正常,可能在毫秒数量级里,撤销缓存的消息往返就完成了。一旦有一个用户通信中断,服务器将等待整整 16 秒,直到租约过期。此时时间的损失,超过平均情况数个数量级。这也是分布式系统里常有的事情:我们更关心出错的最坏情况,而不是正常运行的平均情况。

在 Chubby 的例子里,租约时限是 16 秒或更短。这个信息隐含的意思是,用户所保存的缓存的时效最长亦为 16 秒,且用户有责任在 16 秒内向服务器报告自己健在并续约。

我们有时会称呼这种定时报平安的消息为“心跳”。

缓存技术

局部性

一般来说,在我们的通信模型里存在某种不对称性。这种不对称性包括,访问不同介质的速度差异,访问本地和网络资源的速度差异,以及读和写的频率差异。我们利用此种不对称结构提出的设计原则非常简单粗暴:

尽量避免较慢的访问

其次,局部性是我们对缓存技术生效的一个重要假设:

对大多数计算机程序,它往往在某个局部的时间段内(时间局部性),只频繁访问所有数据中的一个局部(空间局部性)

只有假设成立时,我们为前次访问的数据缓存才有意义。因为根据局部性,前次访问的数据有极大可能被再次访问到。

题外话:考虑到缓存往往是将某个顺序范围的区块一同加载进来的,那些符合这种顺序排列的结构如数组,以及利用此种顺序结构设计的算法,我们都说它们是“缓存友好”(cache friendly) 的。

基于不同介质的速度差异,我们有了单机里经典的“缓存-内存-磁盘”的分层缓存结构。在分布式缓存结构里,这种层级结构也不罕见。

本地缓存与代理 (proxy)

在 Lock Service 这一特定应用里,每个用户可能需要非常频繁地检测某个锁变量是否存在。此时若能将锁变量缓存在本地,将极大缓解服务端的访问压力。正因为此,在之前讨论的写操作过程中,我们才需要撤销缓存来保证一致性。可以说是基于读比写频繁这一使用场景,我们人为制造了读写不对称的结构。

这种读比写廉价的不对称结构非常常见,且最常见于具备“订阅”属性的系统里。比如 ADSL 和一些特定数据库的实现。不过我们之后也会见到写比读廉价的反例,那就是 BigTable 。

现在相当于我们有了 “缓存-磁盘” 的模型。当缓存未命中时,用户就必须访问服务端。当用户数量增加的时候,这个未命中的访问量也可能是惊人的。此时我们就有必要设计第二重缓存了。我们为服务端添加若干个代理,每个代理维护一份公共缓存,且服务若干个用户。这样,当本地缓存未命中后,还多了代理缓存的一层保障。而且这样的缓存树结构可以无限地展开,比如根据距离服务端物理距离导致的访问速度差异,设计多级代理,将用户直接访问服务端的几率进一步降低。

举个缓存降低较慢访问的实例:设有用户A,依次访问数据 x, y, x;有用户B,依次访问数据 y, y, z。

  1. 当没有缓存时,A和B直接向服务端取数据,总共产生 6 次访问;
  2. 当本地缓存时,A和B不需访问重复的位置,A访问 x, y, B 访问 y, z,共访问服务端 4 次;
  3. 当仅存在代理时,A和B的请求都交由代理转达,代理只需向服务端请求 x, y, z 各一次,产生 3 次服务端访问,6 次代理访问;
  4. 当存在本地缓存及代理时,A只需向上请求 x, y, B 只需向上请求 y, z,代理向服务端请求 x, y, z 各一次,共产生 3 次服务端访问,4 次代理访问。

常见应用的局部性更加显著,即重复频繁请求的情况很多。这种时候,每添加一层缓存层级,就相当于幂次降低向上一级访问的频次。不过显然地,如果让两个毫无业务关联性的用户让同一个个代理服务,这种显著的局部性就很有可能不存在了。如果情况是前者,当然我们的应用可以通过添加代理来规模化了。

需要注意的是,若使用多重缓存,当写操作发送到服务端时,需要从上向下递归地撤销缓存。

利用 Bloom filter 减少实际访问

Bloom filter 是一种 Hash Set 的变体,被设计用来回答某个数据是否存在于数据库中,仅当 Bloom filter 回答存在的情况下,用户才真正访问数据库。当 Bloom filter 回答不存在的时候,具有 100% 的正确性,即用户可以安全地不去访问数据库;当 Bloom filter 回答存在时,它有一定的误报率,可即使这样,用户也不过是增加了一次数据库的访问而已,并不会对系统造成更大的损害。这就是它被命名为“过滤器”的原因 – 总会有漏网之鱼。

原理很简单,在原本的一个 hash function 对应一个 array 的标准模型上,我们现在让多个互不相同的 hash function 共享一个 array。当一个键值被插入的时候,多个哈希函数同时根据各自的哈希值向数组对应位置置1。当检测一个键值是否存在的时候,必须在所有哈希的对应哈希值位置上找到1,才认为它存在。因为哈希函数对同一个输入的哈希值是确定的(deterministic),如果键值真的被插入,那么它对应的多个哈希值位置就必定置1。故 Bloom filter 对键值不存在的判断是 100% 正确的。

但显然依然存在冲突,比如在有 3 个哈希函数的 Bloom filter 里,x 对应哈希值 1, 3, 5, y 对应哈希值 2, 4, 6, z 对应哈希值 1, 2, 3。当 x 和 y 都被插入之后,1,2, 3 均被置1,这样即使 z 实际不存在,当判断 z 的时候,Bloom filter 依然会误报为存在。

因此这里我们也有一个权衡,我们应用 Bloom filter 的目标有:

  1. 尽量少的误报率 (这就要求更少的插入数量和更大的数组容量,因为误报率显然是和被置1的比例强相关的)
  2. 尽量快的运算速度 (这就要求哈希函数的数量尽量少,但更少的哈希函数显然又增加了冲突的可能性)

另外考虑到它过滤掉的是对表中不存在的键值的访问,那么如果一个表的键值几乎全满的情况下,使用 Bloom filter 就没有什么意义了。因此,Bloom filter 适用于稀疏表。

数据压缩

最后稍微提一下压缩,压缩的原理基本都是通过找相似来去除冗余的。在一个表中,显然一列数据之间,要比一行数据之间具有更高的相似性。因此把数据按列压缩较有意义。但带来的弊端也很明显:如果有用户希望读一整行数据时,它将横跨所有的列压缩文件,造成很低的访问效率。从这里我们就可以看出,为什么有时候写会比读要廉价。