論文筆記：[ICDE18] 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。如 Figure 1: Partial ordering of HAT 所示，紅色的表示在 HA 的限制下不可能實現的一致性級別，其他則是在 HA 的限制下也有可能實現的一致性級別。那麼既要 HA，又要 Replication 的話，怎麼達到一致性呢？答案就是 最終一致性：在收到客戶端請求時立刻做出響應，然後在後台定期傳播這一變動，在一定的協議下令所有 replication 達成一致。這一最終一致性協議如何設計？Anna 根據之前在 Bloom 語言 [6] 中獲得的經驗 [7]，使用 lattice 這樣一種結構讓用戶自行定義 CRDT [4]。在進行衝突解決時，即可根據用戶定義的 CRDT 提供所需的一致性保證。

對於 CRDT 的設計，要求其符合 ACI 屬性，如 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. 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. 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. 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

推薦閱讀：