NoSQL数据库中的分布式算法

作者 李士窑

随着互联网Web2.0的发展，传统的关系数据库在应对超大规模和高并发的SNS类型的Web2.0动态网站关系型数据库性能遭遇了瓶颈，再加上当前移动互联网的发展，关系数据库已经不能满足应用的扩展性、灵活性、高可用性的需要而NoSQL数据库则显得更加能够适应这些需求。NoSQL(即Not Only SQL)，即“不仅仅是SQL”，它是一种非关系型(结构化/半结构化)的数据库，且已经引起了一项全新的数据库革命性运动，从而引发了多种相关协议和算法的研究以及实践，并经过不断的尝试逐渐总结出了一些行之有效的数据库构建方法。

在专注于大数据、NoSQL和高扩展性的软件工程方面报道的博客“Highly Scalable Blog”中报道了一篇关于NoSQL数据库中的分布式算法的文章。在这篇文章里，作者从数据一致性、数据布局、系统协调三个方面以及分布式相关策略（数据复制策略、数据恢复策略、数据分布策略、集群领导选举算法等）对NoSQL数据库的分布式特点进行了一系列系统化的描述。

在数据一致性方面，考虑到一致性问题是由数据隔离盒复制引起的，文章首先从复制的可用性、读写延迟、读写扩展性、容错性、数据持久性、一致性等特点进行了分析，尤其对一致性中的读写一致性、写一致性进行了详细讨论。还以图型的形式分析了不同复制技术之间的逻辑关系和不同技术在系统的一致性、扩展性、可用性、延迟性之间的权衡以及每个技术的详细情况，如下两图所示：

文章还针对能够处理数据一致性维护和集群状态同步的反熵协议以及能够使得所有副本都最终达到一个语义上正确的数据最终一致性进行了介绍。

在数据布局方面，文章主要讲述了控制分布式数据库中如何高效放置数据的算法。这些算法主要负责把数据项映射到合适的屋里借点上，在节点间迁移数据和内存资源的分配。对如何在集群扩容时做到数据的平衡分配、如何合理在动态环境中进行数据分片和复制以实现把记录合理地映射到物理节点上、如何按照多个属性进行数据分片以及如何合理利用内存而提高数据随机读取性能的要求等方面进行了一一介绍。

在如何系统协调方面，文章讨论了与系统协调相关的故障检测和协调者选举两种技术。故障检测是任何一个拥有容错性的分布式系统的基本功能，且所有的故障检测协议都是基于心跳通讯机制的，而真正的分布式系统还要有一些额外的功能要求，如能够应对暂时的网络故障和延迟，以及集群拓扑、负载和带宽的变化的自适应行、应对节点失效、作业重新分配以及释放相关资源的自适应性、分布式系统中失败检测功能的可扩展性和健壮性等要求。协调者选举是保证强一致性数据库的一个重要技术，而Bully算法是一种相对简单的协调者选举算法，MongoDB就用了该算法来决定副本集中主机节点。

分布式算法还包括分布式锁、一致性协议以及其他一些基础技术的内容，这些内容可以通过很多其他书籍或者网络资源查看。

文章出处：infoq