副本更新策略 通常情况，大规模分布式存储系统会将一份数据在系统内复制多份并保存在不同的存储。一方面可以通过数据冗余来增加系统的可用性，另一方面也可以增加读操作的并发程度。在多副本的情况下，有3种可能的更新策略：同时更新策略、主从式更新策略和任意节点更新策略。 同时更新 类型1：不通过一致性协议 不通过任何一致性协议直接同时更新多个副本数据。这种情形存在法硕的数据一致性问题：如果同一时刻两个不同的客
哈希分片（Hash Partition） 哈希取模法（Round Robin） 假设要分 K 个区，编号 [0, K-1]，分片算法为： H(key) = hash(key) mod K 缺点："Key-分区" 和 "分区-物理" 耦合，增减分区打乱原有数据分片。 虚拟桶（Virtual Burket） 多加一层，哈希算法先映射到虚拟桶，再用一个表把虚拟桶映
数据分布的两条路径 1、复制（replication）：将同一份数据拷贝到多个节点（主从master-slave方式、对等式peer-to-peer） 2、分片（sharding）：将不同数据存放在不同节点
布隆过滤器 当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。 优点 相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 (O(
LZ77 / LZ78 / Snappy / LZSS LZ77 与 LZ78 是Abraham Lempel与Jacob Ziv在1977年以及1978年发表的论文中的两个无损数据压缩算法。这两个算法是大多数LZ算法变体如LZW、LZSS以及其它一些压缩算法的基础。 LZSS 是一种字典编码技术。它会尝试以符号字符串替换相同字符串为一个字典位置的引用，属于LZ77的派生。 Snappy 是 Go
Trie 树 对于字典树，有三个重要性质： 根节点不包含字符，除了根节点每个节点都只包含一个字符。root节点不含字符这样做的目的是为了能够包括所有字符串。 从根节点到某一个节点，路过字符串起来就是该节点对应的字符串。 每个节点的子节点字符不同，也就是找到对应单词、字符是唯一的。
SkipList 跳表是由William Pugh发明的，上面的引言就是他给出的解释。跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。 表头（head）：负责维护跳跃表的节点指针。 跳跃表节点：保存着元素值，以及多个层。 • 层：保存着指向
Mekle 哈希树 Merkle 树结构 默克尔树（又叫哈希树）是一种典型的二叉树结构，由一个根节点、一组中间节点和一组叶节点组成。默克尔树最早由 Merkle Ralf 在 1980 年提出，曾广泛用于文件系统和 P2P 系统中。 其主要特点为： 最下面的叶节点包含存储数据或其哈希值； 非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值。 进一步地，默克尔树可以推广到多叉树的情形
LSM 树 LSM树，即日志结构合并树(Log-Structured Merge-Tree)。 其实它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。 大多NoSQL数据库核心思想都是基于LSM来做的， 只是具体的实现不同。 它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中， 而可以先将最新的数据驻留在内存中，等到积累到最后多之后，再使用归