《解读NoSQL》——2.4　使用一致性散列算法维护当前的缓存

在评估NoSQL系统如何工作时，一致性散列算法是一种有效的通用流程。一致性散列算法能很快判断出一个新的查询或者文档是否和缓存中的某一个对象是相同的。了解这些将有助于减少不必要的磁盘访问并且使数据库保持高速运行的状态

本节书摘来自异步社区出版社《解读NoSQL》一书中的第2章，第2.4节，作者： 【美】Dan McCreary（丹•麦克雷） , Ann Kelly（安•凯利），更多章节内容可以访问云栖社区“异步社区”公众号查看。

2.4 使用一致性散列算法维护当前的缓存

我们已经知道了将经常使用的数据保存在RAM缓存中的重要性，以及如何通过减少非必要的磁盘访问来提升数据库性能。NoSQL系统将基于这个概念进行深入探讨，并采用了一致性散列（consistent hashing）的算法使访问最频繁的数据保存在缓存中。

在评估NoSQL系统如何工作时，一致性散列算法是一种有效的通用流程。一致性散列算法能很快判断出一个新的查询或者文档是否和缓存中的某一个对象是相同的。了解这些将有助于减少不必要的磁盘访问并且使数据库保持高速运行的状态。

生成散列字符串（也称作校验和或者散列），是通过检查文档中的每一个字节并计算出一个字母序列的过程。散列字符串对于每个文档来说都是独一无二的标识，可以用来判断当前的文档和已有的文档是否一致。如果两个文档存在差异（即使是一个字节），那么散列的结果也会不同。从20世纪90年代开始，散列字符串就可以通过一些标准化的算法生成，如MD5、SHA-1、SHA-256和RIPEMD-160。图2-6展示了一个典型的散列处理过程。

图2-6 散列过程示例。一个文档（如商业发票）被作为一个散列函数的输入。散列函数处理的结果是一个字符串，这个字符串对原始的文档来说是独一无二的，哪怕是一个字节的改动都会导致散列函数处理的结果不同。散列可以被用来检测文件是否被修改或者对象是否已经存储在RAM缓存中

简单的查询或者是复杂的JSON和XML文档都可以生成散列值。一旦拥有了散列值，就可以用它来确保每次发送给其他人的信息是一致的。一致性散列使得网络中运行在不同节点上的两个不同的进程对于同一个对象能够生成同样的散列值。一致性散列确认了文档中信息没有被改动并且可以用于决定某个对象是否应该留在缓存或消息存储中，通过只在必要时才重新运行进程来节省宝贵的资源。

一致性散列也是同步分布式数据库的关键。例如，Git、Subversion之类的修改控制系统不仅对目录中的单个文档求散列值，还会对目录中的所有文件进行散列校验。通过持续地对所有文件进行校验，可以发现本地目录与远程的目录是否同步，如果不同步，可以只对那些改变的项目执行更新操作。

一致性散列是维护当前缓存和系统高速运行的重要工具，即使缓存被分散到许多分布式系统中，一致性散列也可以对其进行维护。一致性散列也被用来将文档分派到分布式系统的数据库节点，并在需要同步时能快速地比较远程数据库。分布式的NoSQL系统依靠散列显著地提升了数据库的读能力，并且没有妨碍到写事务。

散列冲突

两个不同的文档仍然存在极小的机会可能生成同样的散列值，这将会导致散列冲突（hash collision）。发生冲突的可能性取决于散列值的长度和需要存储的文档数。散列值越长，发生冲突的可能性就越低。如果增加文档数，发生冲突的可能性会增大。许多系统采用MD5散列算法生成128位的散列字符串。一个128位的散列可以生成大约1038种可能的输出。那就意味着，如果想将冲突的可能性保持在一个比较低的水平，如1018分之一以下，那么需要将维护的文档数降低到1013以下，或者限制在105亿文档左右。

对于大多数使用散列的应用，偶然的散列冲突并不是我们关注的焦点。但有些需要避免散列冲突的情况是我们关注的重点。那些使用散列作为安全验证的系统，如政府或者高度安全系统，需要超过128位的散列值。在这些情况中，更倾向于使用一些能生成超过128位散列值的算法，如SHA-1、SHA-256、SHA-384或者SHA-512。

12 张图看懂 CPU 缓存一致性与 MESI 协议，真的一致吗？ 什么是缓存一致性问题，CPU Cache 的读取和写入过程是如何执行的，MESI 缓存一致性协议又是什么？今天我们将围绕这些问题展开。
缓存一致性与内存屏障 计算机的演进就是一部在挖坑和填坑之间反复横跳的发展史。对这一点的理解会随着本文的后续讲述逐渐加深。比如高速缓存Cache很好地解决了CPU与内存的速度矛盾，但是也为计算机系统带来了更高的复杂度
异步社区 异步社区(www.epubit.com)是人民邮电出版社旗下IT专业图书旗舰社区，也是国内领先的IT专业图书社区，致力于优质学习内容的出版和分享，实现了纸书电子书的同步上架，于2015年8月上线运营。公众号【异步图书】，每日赠送异步新书。