A-A+

Anna KVS中的Lattice是什么?

2018年12月22日 分布式 评论 3 条 阅读 1,724 次
摘要:

Anna KVS官网对Anna的特性总结得非常到位:1. Crazy Fast, 2. Super-Scalable, 3. Flexibly Consistent。这里只关注Flexibly Consistent这一项,讲讲Anna是怎么实现灵活的consistency的。这篇博客算是论文导读,详细内容读者仍要仔细阅读论文原文 Anna: A KVS For Any Scale。
Lattice是什么,基于格怎么实现灵活的多种一致性,漫谈Consistency和Isolation Level。

// 一篇闲扯的博文

Anna KVS官网对Anna的特性总结得非常到位:1. Crazy Fast, 2. Super-Scalable, 3. Flexibly Consistent。

这里只关注Flexibly Consistent这一项,讲讲Anna是实现灵活的consistency的背后的东西。

这篇博客算是论文导读,详细内容读者仍要仔细阅读论文原文 Anna: A KVS For Any Scale。

 

Lattice是什么

lattice是离散数学里面的概念,中文教科书上叫格。

格是一种有上下确界的偏序集(论文用的是只有上确界的半格,join semilattice),那偏序集是什么呢?

偏序集(partially ordered set, poset):一个集合,以及该集合上一个偏序关系。

举个例子,集合S=\{1,2,3,4,6,8,9,12,72\},偏序定义成"可整除",将偏序集用图来表示的话,就是这个样子。

poset

其中,1是下确界(所有元素都能整除1),72是上确界(72能整除所有元素),所以这个偏序集是一个格,自然也是个join semilattice。

非join semilattice例子:如果上图再加上一个元素64,集合中没有元素既能整除64,又能整除72,那么就不再满足上确界条件,因此也不再是一个join semilattice。

 

回顾Lamport讲的事件序(逻辑时钟),我们会发现,lattice来描述分布式系统里面事件的先后顺序是非常自然的,分布式系统中happen-before本身就是个偏序关系。

 

不过,论文中提到的lattice,用的是跟上述定义等价的代数系统里面的定义。

满足如下性质的代数结构叫格:

  •  交换律 a\sqcup b=b\sqcup a
  • 结合律 (a\sqcup b)\sqcup c=a\sqcup(b\sqcup c)
  • 幂等律 a\sqcup a=a

 

论文使用这个定义,主要是为了贴切论文里面的说的merge动作。这里一个\sqcup运算(二元运算)就对应一个merge逻辑。再对应到前面一种定义方式的图示,可以理解成两个节点的最小的公共后缀节点(也就是最小公倍数,这也是两种定义方式等价的证明思路),比如4\sqcup 6=12, 12\sqcup 6=12

注:关于merge动作(conflict resolution),可以先参考2007年Dynamo论文。

 

基于格怎么实现灵活的多种一致性

基本思路:系统中的不同组件上都可能存在若干个lattice用于描述偏序关系,灵活的一致性说白了,一是增加/减少lattice,二是增加/减少lattice的边(也就是增加/减少\sqcup运算,也就是增加/减少自定义解决冲突的逻辑)。

但要注意的是,只靠lattice这套框架是无法实现各种灵活的一致性的,因为尤其是在涉及到事务粒度的隔离级别/一致性的时候,lattice能做的只是些局部的逻辑(要注意到论文提到的coordinator-free)。lattice得是在系统为了实现特定功能而增加/减少/改造组件之后才能应用。例如,论文实现Read Committed的例子中有诸如要在事务提交前将数据buffer到client的临时缓冲区中操作。这也是我觉得这篇论文不干净的地方(否则那就厉害了,我们甚至可以基于lattice来一统consistency和isolation level的定义了)。

 

漫谈Consistency和Isolation Level

论文把Isolation Level和Consistency放在一块,统一到论文框架里面了(实际上,涉及到Isolation Level的时候,可能会把client buffer write这类非事件的逻辑也牵涉进来)。

那么,Isolation Level和Consistency有什么相似性?这是一个很zen-like的问题。我的看法是,二者其实都是用来衡量整个系统对客户端表现出来的异常程度的。从这个角度,也算给consistency和isolation level二者“混为一谈”找到了一个理由。

另外,希望业界大牛把这堆乱七八糟的东西理一下,该重新定义的重新定义,该抹掉的抹掉,省的以后讨论到这个话题,还得先对一下双方对consistency的理解是不是一样 🙁 

 

3 条留言  访客:0 条  博主:0 条   引用: 1 条

  1. LoopJump

    jepsen 的那个Consistency Model,我理解就只是那么放在一块了,似乎算不上统一的自洽的定义。
    比如,涉及isolation level的应该理解成用排除异常phenomena来定义(来自jim gray的critique论文的定义方式);sequential consistency应该理解成data-centric角度的一组对象的更新顺序的可见性(来自lamport的一贯思路);还有一些是从session-centric角度定义的比如read your write等(不知道来自哪,可能是来自偏应用的一些场合)。

  2. no

    jepsen 的那个Consistency Model引用的High Available Transaction还不算统一了Transaction和Consistency吗

来自外部的引用: 1 条

  • LoopJump’s Blog

给我留言