HCOONa's blog

本文从CAP理论和ACID性质为切入点，讨论分布式（存储）系统的设计。

分布式系统，尤其是分布式存储系统，在进行设计考虑时，首先需要想到的就是CAP问题，即在C（Consistency）和A（Availability）之间如何进行取舍的问题。我在思考的过程中发现，尽管对于Consistency有着诸多分类，如Linearizability、Sequential Consistency、Causal Consistency，但是对于Availability却没有一个对应的分类。这有悖于对CAP理论的理解：我们降低了Consistency之后，能得到什么程度的Availability？更进一步的，我们降低了Consistency后，是否真的能够提高Availability？

哈希表（hash table）是一种快速查找场景下常用的数据结构，本文对其主要问题及其高级应对方法进行有限的总结和讨论：

用 C++ 语言也有一些年头了，在此总结一些工作中比较实用的 C++ 的功能子集。这里的主要使用场景是系统编程，不包括各种通用类库。

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

我认为每个程序员都应该会点形式化证明，这有助于思考，更有助于写出正确的实现。

这是一篇关于单机存储引擎基本思路的总结和分析。

F4 是 Facebook 为了降低存储成本而开发的，应用于只读可删除不可写场景的，对象存储系统。

Haystack 是 Facebook 为了其图片存储场景进行特殊优化的热存储系统，系统接口是简单 Key-Value 存储。论文主要描述了其单机存储引擎的构建，针对一次写入多次读取从不修改的场景进行优化。本笔记只涉及到论文中单机存储引擎的部分。

Raft 是一种分布式共识算法，用于解决在异步通信网络中存在节点失效且本地存储可靠的情况下多个分布式节点达成一致的问题。在已经提出 Paxos 算法用于解决这一问题的情况下继续提出 Raft 算法，主要是为了解决 Paxos 理解困难的问题。Paxos 算法更偏向于理论研究，对于实现的很多细节虽然略有提及，但是并没有进行深入的讲解和讨论，因此对于算法的实现和优化而言还有很多困难。

Paxos 是一种分布式共识算法，用于解决在异步通信网络中存在节点失效且本地存储可靠的情况下多个分布式节点达成一致的问题。文中的算法只解决了决议一条法案（decree）的情况。如果需要决议多条法案，可以将该算法执行多次，每次分别对应一条法案。可以想象，有可能存在一些步骤在多次决议时无需重复执行，因此在多次决议法案的情况下，该算法可以进一步优化，但没有在本文中进行具体展开。