原理篇
数据存储
我们的目标是做一个可靠的,支持大规模扩展和容易维护的系统。计算机里面有个locality(局部性定律),如图所示。从下到上访问速度越来越快,但存储代价更大。
相对内存,磁盘和SSD就需要考虑数据的摆放, 因为性能会差异很大。磁盘好处是持久化,单位成本便宜,容易备份。但随着内存便宜,很多数据集合可以考虑直接放入内存并分布到各机器上,有些基于 key-value, Memcached用在缓存上。内存的持久化可以通过 (带电池的RAM),提前写入日志再定期做Snapshot或者在其他机器内存中复制。当重启时需要从磁盘或网络载入之前状态。其实写入磁盘就用在追加日志上面 ,读的话就直接从内存。像VoltDB, MemSQL,RAMCloud 关系型又基于内存数据库,可以提供高性能,解决之前磁盘管理的麻烦。
HyperLogLog & Bloom Filter & CountMin Sketch
都是是应用于大数据的算法,大致思路是用一组相互独立的哈希函数依次处理输入。HyperLogLog 用来计算一个很大集合的基数(即合理总共有多少不相同的元素),对哈希值分块计数:对高位统计有多少连续的0;用低位的值当做数据块。BloomFilter,在预处理阶段对输入算出所有哈希函数的值并做出标记。当查找一个特定的输入是否出现过,只需查找这一系列的哈希函数对应值上有没有标记。对于BloomFilter,可能有False Positive,但不可能有False Negative。BloomFilter可看做查找一个数据有或者没有的数据结构(数据的频率是否大于1)。CountMin Sketch在BloomFilter的基础上更进一步,它可用来估算某一个输入的频率(不局限于大于1)。
CAP Theorem
简单说是三个特性:一致性,可用性和网络分区,最多只能取其二。设计不同类型系统要多去权衡。分布式系统还有很多算法和高深理论,比如:Paxos算法(paxos分布式一致性算法--讲述诸葛亮的反穿越),Gossip协议(Cassandra学习笔记之Gossip协议),Quorum (分布式系统),时间逻辑,向量时钟(一致性算法之四: 时间戳和向量图),拜占庭将军问题,二阶段提交等,需要耐心研究。