Programming Pearls

很喜欢《Programming Pearls》这本书,因此用了这个名字。介绍一些好看好玩的编程paper、slides、video等。

Skip Lists: A Probabilistic Alternative to Balanced Trees

🔗: skiplist
📝: skiplist 是一种概率数据结构,大概率下拥有和红黑树同样的查找和修改性能,但是实现简单很多,在很多场景都有使用,例如leveldb redis, 论文和c实现可以参考这里 ftp://ftp.cs.umd.edu/pub/skipLists。


In Search of an Understandable Consensus Algorithm

🔗: raft
📝: 鼎鼎大名的raft论文,文章按照Leader Election, Log Replication, Safety介绍了一致性算法,跟paxos做了对比,同时介绍了Cluster membership changes以及Log compaction.


MapReduce: Simplified Data Processing on Large Clusters

🔗: mapreduce
📝: Jeffrey Dean and Sanjay Ghemawat的mr论文,非常详细的介绍了mr模型,包括模型是如何被提出来的,为什么定义了mapper/reducer两个用户接口,以及整体的数据处理流程,数据的准备、任务的分配,中间结果的存储以及容错。个人觉得最优秀的是从google众多的大数据计算里抽象出了mr这个模型。