Anna KVS中的Lattice是什么?
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):一个集合,以及该集合上一个偏序关系。
举个例子,集合,偏序定义成"可整除",将偏序集用图来表示的话,就是这个样子。
其中,1是下确界(所有元素都能整除1),72是上确界(72能整除所有元素),所以这个偏序集是一个格,自然也是个join semilattice。
非join semilattice例子:如果上图再加上一个元素64,集合中没有元素既能整除64,又能整除72,那么就不再满足上确界条件,因此也不再是一个join semilattice。
回顾Lamport讲的事件序(逻辑时钟),我们会发现,lattice来描述分布式系统里面事件的先后顺序是非常自然的,分布式系统中happen-before本身就是个偏序关系。
满足如下性质的代数结构叫格:
- 交换律
- 结合律
- 幂等律
论文使用这个定义,主要是为了贴切论文里面的说的merge动作。这里一个运算(二元运算)就对应一个merge逻辑。再对应到前面一种定义方式的图示,可以理解成两个节点的最小的公共后缀节点(也就是最小公倍数,这也是两种定义方式等价的证明思路),比如
。
基于格怎么实现灵活的多种一致性
基本思路:系统中的不同组件上都可能存在若干个lattice用于描述偏序关系,灵活的一致性说白了,一是增加/减少lattice,二是增加/减少lattice的边(也就是增加/减少运算,也就是增加/减少自定义解决冲突的逻辑)。
但要注意的是,只靠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的理解是不是一样 🙁
jepsen 的那个Consistency Model,我理解就只是那么放在一块了,似乎算不上统一的自洽的定义。
比如,涉及isolation level的应该理解成用排除异常phenomena来定义(来自jim gray的critique论文的定义方式);sequential consistency应该理解成data-centric角度的一组对象的更新顺序的可见性(来自lamport的一贯思路);还有一些是从session-centric角度定义的比如read your write等(不知道来自哪,可能是来自偏应用的一些场合)。
jepsen 的那个Consistency Model引用的High Available Transaction还不算统一了Transaction和Consistency吗