Maxim

希望不是未来的东西，它是看见此刻的方式。

分布式计算的谬论

refer to https://en.wikipedia.org/wiki/Fallacies_of_distributed_computing

The fallacies are:

1. The network is reliable 网络是可靠的
2. Latency is zero 延时为零
3. Bandwidth is infinite 带宽无限
4. The network is secure 网络是安全的
5. Topology doesn't change 网络拓扑是不变的
6. There is one administrator 有一个管理员
7. Transport cost is zero 传输成本为零
8. The network is homogeneous

key-value数据结构

一般有三种：Hash表、红黑树、SkipList，它们各自有着不同的优缺点（不考虑删除操作）：

• Hash表：插入、查找最快，为O(1)；如使用链表实现则可实现无锁；数据有序化需要显式的排序操作。
• 红黑树：插入、查找为O(logn)，但常数项较小；无锁实现的复杂性很高，一般需要加锁；数据天然有序。
• SkipList：插入、查找为O(logn)，但常数项比红黑树要大；底层结构为链表，可无锁实现；数据天然有序。

如果要实现一个key-value结构，需求的功能有插入、查找、迭代、修改，那么首先Hash表就不是很适合了，因为迭代的时间复杂度比较高；而红黑树的插入很可能会涉及多个结点的旋转、变色操作，因此需要在外层加锁，这无形中降低了它可能的并发度。而SkipList底层是用链表实现的，可以实现为lock free，同时它还有着不错的性能（单线程下只比红黑树略慢），非常适合用来实现我们需求的那种key-value结构。 LevelDB、Reddis的底层存储结构就是用的SkipList。