rsync 算法是一种远程块级增量备份/同步算法。源于UNIX 的一个命令。想了解详细，点这里。
rsync 算法
回复
标签归档：一致性
一致性哈希和分布式哈希表
一致性哈希（consistent hashing）和分布式哈希表（DHT: Distributed Hash Table）在最近的学习中经常用到，但是两个概念经常纠缠在一起，不容易分清楚。有时候就不明白这里为什么说的是consistent hashing，而不是用DHT。
从字面的意思来区分：consistent hashing 是一种满足特殊需求的哈希；DHT 是通过哈希实现的分布式的表，归根到底是一个分布式系统。consistent hashing 是理论上节点变化最少数据迁移的哈希方法，而DHT 在实现上更加具体，DHT 把传统的单个K-V 表在分布式多个节点中进行划分，既可以采用consistent hashing 实现，也可以采用其他哈希方法。
Dynamo: Amazon’s highly available key-value store
原文 中文翻译 参考：Kai – An Open Source Implementation of Amazon’s Dynamo
本文一直为分布式key-value 存储系统以及分布式存储的业内人士所推崇，个人觉得有两个原因：
- 分布式key-value 存储近年发展迅速。Dynamo 更是集成了近些年最新的技术如：DHT（分布式哈希表）、consistent hashing（一致性哈希）、多版本、副本策略和Merkle tree 等。
- 文章从设计、实施者的角度分析了分布式key-value 存储在实践中的问题和解决方法，并总结了Dynamo 在实现、配置等方面的经验与教训，对后来者非常有借鉴意义。
Web caching with consistent hashing 一致性哈希Web 缓存
读这篇文章源自于一致性哈希的开山之作：Consistent hashing and random trees: Distributed caching protocol for relieving hot spots on World Wide Web。在STOC 上下了原文后觉得估计得花和The part-time parliament 差不多时间来读吧，以后有必要深入学习再看吧！一致性哈希Web 缓存是与开山之作同一作者David Karger 1999年所写 。
STOC 会议上有许多经典的算法，但很多有晦涩难看懂没有引起大家的注意，直到某个采用了该算法的应用得到大家的认可，该算法才得以为大家所接受。分布式一致性Paxos 算法也是这样。（下面左图是consistent hash 开山作引用情况，右边是The part-time parliament 每年引用量，可见在这些牛文在引用量巅峰期之前都有几年的沉寂期，来自CiteSeerX）
言归正传：
problem
congested network and swmaped servers 集中式缓存存在问题
related work
cooperating cache 将缓存复制到不同的机器，存在数据复制和副本一致性问题
hashing 缓存通过哈希保存到不同机器上，存在扩展性以及churn 问题：当一个节点失效或新增一个节点会导致大量失效和缓存的迁移，比如 7×i+4 mod 24 到 7×i+4 mod 23
our work
浏览器上添加哈希函数，将URL 资源定向到动态变化的可用缓存，无副本且减少失效率
consistent hashing
假设有n 个缓存节点，根据其哈希结果使用二叉树进行组织
our system
组成：1.actual cache system 2.user’ browsers 3.domain name server
浏览器对URL 进行哈希得到虚拟地址，返回给DNS 服务器
DNS 服务器通过客户端的虚拟地址查到到对应的缓存节点物理地址IP
缓存节点从原始Web 服务器取数据并保存一份副本，可相应浏览器请求
Consistent hashing 的python 实现
部分代码参考之前的“写一个分布式存储系统有多简单？”，保持数据服务器端不变，修改客户端节点选择方式即可。
修改：1、添加HashRing 类，进行一致性哈希环的管理，保存在客户端client ，因此节点/数据服务器端可以不做任何修改（添加hello 测试）。2、客户端修改节点选择方式，使用consistent hashing。
接受一致性哈希的国内的也比较多了，可以参考这里
Paxos 算法
一、写在之前
Byzantine 算法面对分布式系统中节点的可信问题，提出了可信节点达成一致性解决方法。Paxos 算法是为了解决分布式系统中节点失效而提出的一致性算法。就分布式存储系统而言，Paxos 算法的价值更大，因为节点是可信的且会因为故障或者扩容发生节点失效。
不仅只用在分布式系统，凡是多个过程需要达成某种一致性的都可以用到Paxos 算法。一致性方法可以通过共享内存（需要锁）或者消息传递实现，Paxos 算法采用的是后者。下面是Paxos 算法适用的几种情况：一台机器中多个进程/线程达成数据一致；分布式文件系统或者分布式数据库中多客户端并发读写数据；分布式存储中多个副本响应读写请求的一致性。
Lamport 最初Paxos 算法的论文The Part-Time Parliament 在理解起来比较有挑战性，个人认为部分原因是Lamport 通过故事的方式来表述、解释这个问题，所以在阅读文章的时候读者需要透过故事讲的本身看到作者想说明什么。比如文章中会有很多讲到Paxon 文明没有被发现和考证的，这些映射到实际系统中往往是简单、大家都心知肚明的基础，但如果读者苦于想知道这些内容是什么时，就上当了。下面章节安排如下：第二节对应原文的1.1-2.1。第三节对应原文2.2-3.2。
