数据分布的两条路径 1、复制（replication）：将同一份数据拷贝到多个节点（主从master-slave方式、对等式peer-to-peer） 2、分片（sharding）：将不同数据存放在不同节点

Shuffle 根据 Key 分发 balance 均匀分发 broadcast 在所有分区上广播 forward 在物理机上直传

布隆过滤器 当一个元素被加入集合时，通过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来做的， 只是具体的实现不同。 它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中， 而可以先将最新的数据驻留在内存中，等到积累到最后多之后，再使用归

Cuckoo哈希 布谷鸟哈希最早于2001 年由Rasmus Pagh 和Flemming Friche Rodler 提出。该哈希方法是为了解决哈希冲突的问题而提出，利用较少计算换取了较大空间。名称源于该哈希方法行为类似于布谷鸟在别的鸟巢中下蛋，并将别的鸟蛋挤出的行为。它具有占用空间小、查询迅速等特性，可用于Bloom filter 和内存管理。 算法描述 算法使用hashA 和hashB 计算