论文笔记：[ICDE'18] Anna: A KVS for any scale

发表于 更新于 分类于

Anna 是 Berkeley 大学研究的一种 Key-Value 存储 [1]。其开创性的使用 lattice 的方式允许用户自定义冲突解决方式，进而可以自定义一致性级别，在特定场景下极大的提升系统性能。Anna 使用了 Actor 模型而非传统的共享内存模型构建系统，使得系统可以以几乎一致的方式处理单机/分布式场景下的通信和协调，并且充分发挥硬件提供的并发能力。论文中没有详细叙述实现这两者的具体细节，由于这两者的实现方式都有一定难度，期待接下来的研究能够披露出进一步的细节。

整体结构上 Anna 与 Amazon Dynamo [2] 相同。区别在于 Dynamo 中节点是由物理节点构成，而 Anna 是由 Actor 构成。Anna 的 Actor 绑定在每个节点的可用线程上，以此避免线程切换开销，提供更高性能的服务。Anna 的读写处理无需 coordinator 而 Dynamo 的 sloppy quorum 需要。

Anna 的基本思想来源于 [3] 和 [4]（[5] 是 [4] 的一个补充）。定义 Highly Available 的含义为 guarantees a response from each non-failing server in the presence of arbitrary network partitions between them。如图 Partial ordering of HAT 所示，红色的表示在 HA 的限制下不可能实现的一致性级别，其他则是在 HA 的限制下也有可能实现的一致性级别。那么既要 HA，又要 Replication 的话，怎么达到一致性呢？答案就是*最终一致性*：在收到客户端请求时立刻做出响应，然后在后台定期传播这一变动，在一定的协议下令所有 replication 达成一致。这一最终一致性协议如何设计？Anna 根据之前在 Bloom 语言 [6] 中获得的经验 [7]，使用 lattice 这样一种结构让用户自行定义 CRDT [4]。在进行冲突解决时，即可根据用户定义的 CRDT 提供所需的一致性保证。

Partial ordering of HAT
Figure 1: Partial ordering of HAT

对于 CRDT 的设计，要求其符合 ACI 属性，如图 ACI properties 所示。

ACI properties
Figure 2: ACI properties

符合这样的性质有以下好处。幂等性使得我们可以轻易处理 at least once 语义的消息传播带来的问题。结合性和交换性使得我们可以任意排列组合这些操作。这样我们只需记录客户端请求的 merge 操作日志，然后在副本之间进行同步即可，无需处理他们之间的序关系。我理解 lattice 内部记录了因果关系和 versioning，因此这里实际上处理起来和 Dynamo 差不多，只是在冲突解决方面比 Dynamo 更加灵活。

Anna 的性能测试显示其比较其他 Key-Value Store 具有显著优势。我认为这有几方面可能：

  • Anna 具有更好的多线程性能

  • Anna 具有更低的一致性级别

  • Anna 具有更低的 Durability

References

  • [1] Chenggang Wu, Jose M Faleiro, Yihan Lin, and Joseph M Hellerstein. 2018. Anna : A KVS For Any Scale. ICDE 2018. Retrieved from https://icde2018.org/index.php/program/research-track/long-papers/

  • [2] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. 2007. Dynamo: Amazon’s Highly Available Key-value Store. SOSP 2007, 205–220. DOI:https://doi.org/10.1145/1323293.1294281

  • [3] Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2013. Highly Available Transactions: Virtues and Limitations. Proc. VLDB Endow. 7, 3 (2013), 181–192. DOI:https://doi.org/10.14778/2732232.2732237

  • [4] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. Conflict-Free Replicated Data Types. In Stabilization, Safety, and Security of Distributed Systems, 386–400. DOI:https://doi.org/10.1007/978-3-642-24550-3_29

  • [5] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. A comprehensive study of Convergent and Commutative Replicated Data Types. (2011).

  • [6] Peter Alvaro, Neil Conway, J Hellerstein, and Wr Marczak. 2011. Consistency Analysis in Bloom: a CALM and Collected Approach. Cidr 3, 2 (2011), 249–260. Retrieved from http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper35.pdf

  • [7] Neil Conway, William R. Marczak, Peter Alvaro, Joseph M. Hellerstein, and David Maier. 2012. Logic and lattices for distributed programming. In Proceedings of the Third ACM Symposium on Cloud Computing - SoCC ’12, 1–14. DOI:https://doi.org/10.1145/2391229.2391230