5.1 NoSQL简介

关系型数据库中的表都是存储一些格式化的数据结构，每个元组字段的组成都一样，即使不是每个元组都需要所有的字段，但数据库会为每个元组分配所有的字段，这样的结构可以便于表与表之间进行连接等操作。但从另一个角度来说，它也是关系型数据库性能瓶颈的一个因素。

NoSQL 是一种不同于关系型数据库的数据库管理系统设计方式，是对非关系型数据库的统称。它所采用的数据模型并非关系型数据库的关系模型，而是类似键值、列族、文档等的非今系模型。它打破了长久以来关系型数据库与 ACID（原子性（Atomicity）、一致性（Consistency）隔离性（Isolation）和持久性（Durability））理论大一统的局面。
NoSQL 数据存储不需要固定的表结构，每一个元组可以有不一样的字段，每个元组可以根据需要增加一些自己的键值对，这样就不会局限于固定的结构，可以减少一些时间和空间的开销。
NoSQL 在大数据存取上具备关系型数据库无法比拟的性能优势。

1. 灵活的可扩展性
   多年来，数据库负载需要增加时，只能依赖于纵向扩展，也就是买更强的服务器，而不是依赖横向扩展将数据库分布在多台主机上。

NoSQL 在数据设计上就是要能够透明地利用新结点进行扩展。NoSQL 数据库种类繁多，但是一个共同的特点是都去掉了关系型数据库的关系型裝性。数据之间无关系，非常容易扩展，从而也在架构层面上带来了可横向扩展的能力。

1. 灵活的数据模型，可以处理半结构化/非结构化的大数据

对于大型的生产性的关系型数据库来讲，变更数据模型是一件很困难的事情。即使只对一个数据模型做很小的改动，也许就需要停机或降低服务水平。
NoSQL 数据库在数据模型约束方面更加宽松，无须事先为要存储的数据建立字段，随时可以存储自定义的数据格式。NoSQL 数据库可以让应用程序在一个数据元素里存储任何结构的数据，包括半结构化/非结构化数据。

5.2 NoSQL兴起的原因

NoSQL 数据库的产生就是为了解决大规模数据集合多重数据种类带来的挑战，尤其是大数据应用难题。

1. 无法满足对海量数据的高效率存储和访问的需求
   Web 2.0 网站要根据用户个性化信息来实时生成动态页面和提供动态信息，基本上无法使用动态页面静态化技术，因此数据库并发负载非常高，往往要处理每秒上万次的读写请求。

关系型数据库处理上万次 SQL 查询已经很困难了，要处理上万次 SQL 写数据请求，硬盘 I/O 实在无法承受。
另外，在大型的社交网站中，用户每天产生海量的动态数据，关系型数据库难以存储这么大量的半结构化数据。在一张上亿条记录的表里面进行 SQL 查询，效率会非常低甚至是不可忍受的。

1. 无法满足对数据库的高可扩展性和高可用性的需求

在基于 Web 的架构当中，数据库是最难进行横向扩展的，当一个应用系统的用户量和访问量与日倶增时，数据库无法像 Web 服务器那样简单地通过添加更多的硬件和服务器结点来扩展性能和负载能力。

1. 关系数据库无法存储和处理半结构化/非结构化数据

现在开发者可以通过 Facebook、腾讯和阿里等第三方网站获取与访问数据，如个人用户信息、地理位置数据、社交图谱、用户产生的内容、机器日志数据及传感器生成的数据等。
对这些数据的使用正在快速改变着通信、购物、广告、娱乐及关系管理的特质。开发者希望使用非常灵活的数据库，轻松容纳新的数据类型，并且不会被第三方数据提供商内容结构的变化所限制。很多新数据都是非结构化或是半结构化的，因此开发者还需要能够高效存储这种数据的数据库。
但是，关系型数据库所使用的定义严格、基于模式的方式是无法快速容纳新的数据类型的，对于非结构化或是半结构化的数据更是无能为力。
NoSQL 提供的数据模型则能很好地满足这种需求。很多应用都会从这种非结构化数据模型中获益，如 CRM、ERP、BPM 等，它们可以通过这种灵活性存储数据而无须修改表或是创建更多的列。

1. 关系数据库的事务特性对 Web 2.0 是不必要的

关系数据库对数据库事务一致性需求很强。插入一条数据之后立刻查询，肯定可以读出这条数据。很多 Web 实时系统并不要求严格的数据库事务，对读一致性的要求很低，有些场合对写一致性要求也不高。
所以，对于 Web 系统来讲，就没有必要像关系数据库那样实现复杂的事务机制，从而可以降低系统开销，提高系统效率。

1. Web 2.0 无须进行复杂的 SQL 查询，特别是多表关联查询

复杂的 SQL 查询通常包含多表连接操作，该类操作代价高昂。但是，社交类型的网站，往往更多的是单表的主键查询，以及单表的简单条件分页查询，SQL 的功能被极大地弱化了。
因此，Web 2.0 时代的各类网站的数据管理需求已经与传统企业应用大不相同，关系数据库很难满足新时期的需求，于是 NoSQL 数据库应运而生。

MySQL集群是否可以完全解决问题？

• 复杂性：部署、管理、配置很复杂
• 数据库复制：MySQL主备之间采用复制方式，只能是异步复制，当主库压力较大时可能产生较大延迟，主备切换可能会丢失最后一部分更新事务，这时往往需要人工介入，备份和恢复不方便
• 扩容问题：如果系统压力过大需要增加新的机器，这个过程涉及数据重新划分，整个过程比较复杂，且容易出错
• 动态数据迁移问题：如果某个数据库组压力过大，需要将其中部分数据迁移出去，迁移过程需要总控节点整体协调，以及数据库节点的配合。这个过程很难做到自动化

5.3 NoSQL与关系数据库的比较

总结
关系数据库

• 优势：以完善的关系代数理论作为基础，有严格的标准，支持事务ACID四性，借助索引机制可以实现高效的查询，技术成熟，有专业公司的技术支持
• 劣势：可扩展性较差，无法较好支持海量数据存储，数据模型过于死板、无法较好支持Web2.0应用，事务机制影响了系统的整体性能等
• 关系数据库应用场景：电信、银行等领域的关键业务系统，需要保证强事务一致性

NoSQL数据库

• 优势：可以支持超大规模数据存储，灵活的数据模型可以很好地支持Web2.0应用，具有强大的横向扩展能力等
• 劣势：缺乏数学理论基础，复杂查询性能不高，大都不能实现事务强一致性，很难实现数据完整性，技术尚不成熟，缺乏专业团队的技术支持，维护较困难等
• NoSQL数据库应用场景：互联网企业、传统企业的非关键业务（比如数据分析）

采用混合架构
案例：亚马逊公司就使用不同类型的数据库来支撑它的电子商务应用

• 对于“购物篮”这种临时性数据，采用键值存储会更加高效
• 当前的产品和订单信息则适合存放在关系数据库中
• 大量的历史订单信息则适合保存在类似MongoDB的文档数据库中

5.4 NoSQL的四大类型

NoSQL数据库虽然数量众多，但是，归结起来，典型的NoSQL数据库通常包括键值数据库、列族数据库、文档数据库和图形数据库

5.4.1 键值数据库

（Redis）、Youtube（Memcached）、Wikipedia（Memcached） |

5.4.2 列族数据库

and HBase）、Facebook（HBase）、Yahoo!（HBase） |

5.4.3 文档数据库

“文档”其实是一个数据记录，这个记录能够对包含的数据类型和内容进行“自我描述”。XML文档、HTML文档和JSON 文档就属于这一类。SequoiaDB就是使用JSON格式的文档数据库，它的存储的数据是这样的：

• 数据是不规则的，每一条记录包含了所有的有关“SequoiaDB”的信息而没有任何外部的引用，这条记录就是“自包含”的
• 这使得记录很容易完全移动到其他服务器，因为这条记录的所有信息都包含在里面了，不需要考虑还有信息在别的表没有一起迁移走
• 同时，因为在移动过程中，只有被移动的那一条记录（文档）需要操作，而不像关系型中每个有关联的表都需要锁住来保证一致性，这样一来ACID的保证就会变得更快速，读写的速度也会有很大的提升

（MongoDB）、Codecademy （MongoDB）、Foursquare （MongoDB）、NBC News （RavenDB） |

5.4.4 图形数据库

| 相关产品 | Neo4J、OrientDB、InfoGrid、Infinite Graph、GraphDB | | —- | —- | | 数据模型 | 图结构 | | 典型应用 | 专门用于处理具有高度相互关联关系的数据，比较适合于社交网络、模式识别、依赖分析、推荐系统以及路径寻找等问题 | | 优点 | 灵活性高，支持复杂的图形算法，可用于构建复杂的关系图谱 | | 缺点 | 复杂性高，只能支持一定的数据规模 | | 使用者 | Adobe（Neo4J）、Cisco（Neo4J）、T-Mobile（Neo4J） |

5.4.5 不同类型数据库比较分析

• MySQL产生年代较早，而且随着LAMP大潮得以成熟。尽管其没有什么大的改进，但是新兴的互联网使用的最多的数据库
• MongoDB是个新生事物，提供更灵活的数据模型、异步提交、地理位置索引等五花十色的功能
• HBase是个“仗势欺人”的大象兵。依仗着Hadoop的生态环境，可以有很好的扩展性。但是就像象兵一样，使用者需要养一头大象(Hadoop),才能驱使他
• Redis是键值存储的代表，功能最简单。提供随机数据存储。就像一根棒子一样，没有多余的构造。但是也正是因此，它的伸缩性特别好。就像悟空手里的金箍棒，大可捅破天，小能成缩成针

5.5 NoSQL的三大基石

5.5.1 CAP

所谓的CAP指的是：

• C（Consistency）：一致性，是指任何一个读操作总是能够读到之前完成的写操作的结果，也就是在分布式环境中，多点的数据是一致的，或者说，所有节点在同一时间具有相同的数据
• A:（Availability）：可用性，是指快速获取数据，可以在确定的时间内返回操作结果，保证每个请求不管成功或者失败都有响应；
• P（Tolerance of Network Partition）：分区容忍性，是指当出现网络分区的情况时（即系统中的一部分节点无法和其他节点进行通信），分离的系统也能够正常运行，也就是说，系统中任意信息的丢失或失败不会影响系统的继续运作。

CAP理论告诉我们，一个分布式系统不可能同时满足一致性、可用性和分区容忍性这三个需求，最多只能同时满足其中两个，正所谓“鱼和熊掌不可兼得”。

当处理CAP的问题时，可以有几个明显的选择：

• CA：也就是强调一致性（C）和可用性（A），放弃分区容忍性（P），最简单的做法是把所有与事务相关的内容都放到同一台机器上。很显然，这种做法会严重影响系统的可扩展性。传统的关系数据库（MySQL、SQL Server和PostgreSQL），都采用了这种设计原则，因此，扩展性都比较差
• CP：也就是强调一致性（C）和分区容忍性（P），放弃可用性（A），当出现网络分区的情况时，受影响的服务需要等待数据一致，因此在等待期间就无法对外提供服务
• AP：也就是强调可用性（A）和分区容忍性（P），放弃一致性（C），允许系统返回不一致的数据

5.5.2 BASE

说起BASE（Basically Availble, Soft-state, Eventual consistency），不得不谈到ACID。
ACID
ACID是关系型数据库强一致性（Strong consistency）的四个要求。

1. 原子性（Atomicity）：事务里的所有操作要么全都执行完成，要么全都不执行。只要有一个操作失败，整个事务就失败，事务会回滚至它们最初的状态。
2. 一致性（Consistency）：数据库要一直处于一致的状态，事务的运行不会改变数据库原本的一致性约束。
3. 隔离性（Isolation）：事务的执行不被其他事务干扰。如果一个事务要访问的数据正在被另外一个事务修改，只要另外一个事务未提交，它所访问的数据就不受未提交事务的影响。

4. 持久性（Durable）：一旦事务提交后，它所做的修改将会永久的保存在数据库上，即使出现系统故障也不会丢失。

   （注：事务（Transaction）是用户定义的一个操作序列。）
   
   BASE
   BASE是基于CAP理论逐步演化而来的，核心思想是即便不能达到强一致性，但是可以根据应用的特点采用适当的方式来达到最终一致性（Eventual consistency）。

5. 基本可用（Basically Available）：分布式系统在出现故障的时候，允许损失部分可用性，即保证核心功能或者当前最重要功能可用。

6. 软状态/柔性事务（Soft-state）：“软状态（soft-state）”是与“硬状态（hard-state）”相对应的一种提法。数据库保存的数据是“硬状态”时，可以保证数据一致性，即保证数据一直是正确的。“软状态”是指状态可以有一段时间不同步，具有一定的滞后性
7. 最终一致性（Eventual consistency）：一致性的类型包括强一致性和弱一致性，二者的主要区别在于高并发的数据访问操作下，后续操作是否能够获取最新的数据。对于强一致性而言，当执行完一次更新操作后，后续的其他读操作就可以保证读到更新后的最新数据；反之，如果不能保证后续访问读到的都是更新后的最新数据，那么就是弱一致性。而最终一致性只不过是弱一致性的一种特例，允许后续的访问操作可以暂时读不到更新后的数据，但是经过一段时间之后，必须最终读到更新后的数据。

最常见的实现最终一致性的系统是DNS（域名系统）。一个域名更新操作根据配置的形式被分发出去，并结合有过期机制的缓存；最终所有的客户端可以看到最新的值。

5.5.3 最终一致性

最终一致性根据更新数据后各进程访问到数据的时间和方式的不同，又可以区分为：

• 因果一致性：如果进程A通知进程B它已更新了一个数据项，那么进程B的后续访问将获得A写入的最新值。而与进程A无因果关系的进程C的访问，仍然遵守一般的最终一致性规则
• “读己之所写”一致性：可以视为因果一致性的一个特例。当进程A自己执行一个更新操作之后，它自己总是可以访问到更新过的值，绝不会看到旧值
• 单调读一致性：如果进程已经看到过数据对象的某个值，那么任何后续访问都不会返回在那个值之前的值
• 会话一致性：它把访问存储系统的进程放到会话（session）的上下文中，只要会话还存在，系统就保证“读己之所写”一致性。如果由于某些失败情形令会话终止，就要建立新的会话，而且系统保证不会延续到新的会话
• 单调写一致性：系统保证来自同一个进程的写操作顺序执行。系统必须保证这种程度的一致性，否则就非常难以编程了

如何实现各种类型的一致性？
对于分布式数据系统：

• N — 数据复制的份数
• W — 更新数据是需要保证写完成的节点数
• R — 读取数据的时候需要读取的节点数

如果W+R>N，写的节点和读的节点重叠，则是强一致性。例如对于典型的一主一备同步复制的关系型数据库，N=2,W=2,R=1，则不管读的是主库还是备库的数据，都是一致的。一般设定是R＋W = N+1，这是保证强一致性的最小设定
如果W+R<=N，则是弱一致性。例如对于一主一备异步复制的关系型数据库，N=2,W=1,R=1，则如果读的是备库，就可能无法读取主库已经更新过的数据，所以是弱一致性。

• 对于分布式系统，为了保证高可用性，一般设置N>=3。不同的N,W,R组合，是在可用性和一致性之间取一个平衡，以适应不同的应用场景。
• 如果N=W,R=1，任何一个写节点失效，都会导致写失败，因此可用性会降低，但是由于数据分布的N个节点是同步写入的，因此可以保证强一致性。
• 实例：HBase是借助其底层的HDFS来实现其数据冗余备份的。HDFS采用的就是强一致性保证。在数据没有完全同步到N个节点前，写操作是不会返回成功的。也就是说它的W＝N，而读操作只需要读到一个值即可，也就是说它R＝1。
• 像Voldemort，Cassandra和Riak这些类Dynamo的系统，通常都允许用户按需要设置N，R，W三个值，即使是设置成W＋R<= N也是可以的。也就是说他允许用户在强一致性和最终一致性之间自由选择。而在用户选择了最终一致性，或者是W<N的强一致性时，则总会出现一段“各个节点数据不同步导致系统处理不一致的时间”。为了提供最终一致性的支持，这些系统会提供一些工具来使数据更新被最终同步到所有相关节点。

5.6 从NoSQL到NewSQL数据库

5.7 NoSQL数据库编程实践

5.7.1 键值数据库Redis

Redis数据库是以的形式存储数据，格式为：
key = 表名:主键值:列名
value = 列值

# 把表格的第一行记录保存到Redis数据库中
set Student:95001:Sname 李勇
set Course:1:Cname 数据库
set SC:95001:1:Grade 92
# 插入数据
set Course:8:Cname 算法
set Course:8:Ccredit 4
# 修改数据
get Course:8:Cname
set Course:8:Cname 编译原理
get Course:8:Cname
# 删除数据
get Course:8:Cname
del Course:8:Cname
get Course:8:Cname

5.7.2 文档数据库MongoDB

下面的还没有在阿里云ECS上面跑通，还需要看情况

# 查看MongoDB版本
mongo -version
# 打开或者关闭MongoB
sudo service mongod start
sudo service mongod stop
# 进入MongoDB Shell界面
mongo
# MongoDB常用命令
show dbs
show collections
show users
use yourDB
# 显示数据库操作命令
db.help()
# 显示集合操作命令
db.yourCollection.help()
# 实验操作
use School
db.createCollection('teacher')
db.createCollection('student')
db.student.insert({_id:1, sname: 'zhangsan', sage: 20})
db.student.save({_id:1, sname: 'zhangsan', sage: 22})
s = [{sname:'lisi',sage:20},{sname:'wangwu',sage:20},{sname:'chenliu',sage:20}]
db.student.insert(s)
# 搜索：db.youCollection.find(criteria, filterDisplay)
db.student.find()
db.student.find({sname:'lisi'})
db.student.find({},{sname:1, sage:1})
db.student.find({sname: 'zhangsan', sage: 22})
db.student.find({$or: [{sage: 22}, {sage: 25}]})
# 修改数据 db.youCollection.update(criteria, objNew, upsert, multi)
db.student.update({sname: 'lisi'}, {$set: {sage: 30}}, false, true)
# 删除操作
db.student.remove({sname: 'chenliu'})
db.student.drop()
exit

下载Java MongoDB Driver驱动jar包：

wget https://repo1.maven.org/maven2/org/mongodb/mongo-java-driver/3.2.2/mongo-java-driver-3.2.2.jar

import java.util.ArrayList;
import java.util.List;
import org.bson.Document;
import com.mongodb.MongoClient;
import com.mongodb.client.MongoCollection;
import com.mongodb.client.MongoCursor;
import com.mongodb.client.MongoDatabase;
import com.mongodb.client.model.Filters;
public class TestMongoDB {
    /**
     * @param args
     */
    public static void main(String[] args) {
//      insert();//插入数据。执行插入时，可将其他三句函数调用语句注释，下同
        find(); //查找数据
//      update();//更新数据
//      delete();//删除数据
    }
    /**
     * 返回指定数据库中的指定集合
     * @param dbname 数据库名
     * @param collectionname 集合名
     * @return
     */
    //MongoDB无需预定义数据库和集合,在使用的时候会自动创建
    public static MongoCollection<Document> getCollection(String dbname,String collectionname){
        //实例化一个mongo客户端,服务器地址：localhost(本地)，端口号：27017
        MongoClient  mongoClient=new MongoClient("localhost",27017);
        //实例化一个mongo数据库
        MongoDatabase mongoDatabase = mongoClient.getDatabase(dbname);
        //获取数据库中某个集合
        MongoCollection<Document> collection = mongoDatabase.getCollection(collectionname);
        return collection;
    }
    /**
     * 插入数据
     */
    public static void insert(){
        try{
            //连接MongoDB，指定连接数据库名，指定连接表名。
            MongoCollection<Document> collection= getCollection("School","student");    //数据库名:School 集合名:student
            //实例化一个文档,文档内容为{sname:'Mary',sage:25}，如果还有其他字段，可以继续追加append
            Document doc1=new Document("sname","Mary").append("sage", 25);
            //实例化一个文档,文档内容为{sname:'Bob',sage:20}
            Document doc2=new Document("sname","Bob").append("sage", 20);
            List<Document> documents = new ArrayList<Document>(); 
            //将doc1、doc2加入到documents列表中
            documents.add(doc1); 
            documents.add(doc2); 
            //将documents插入集合
            collection.insertMany(documents);  
            System.out.println("插入成功"); 
        }catch(Exception e){
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
        }
    }
    /**
     * 查询数据
     */
    public static void find(){
        try{
            MongoCollection<Document> collection = getCollection("School","student");  //数据库名:School 集合名:student
            //通过游标遍历检索出的文档集合 
//          MongoCursor<Document>  cursor= collection.find(new Document("sname","Mary")). projection(new Document("sname",1).append("sage",1).append("_id", 0)).iterator();   //find查询条件：sname='Mary'。projection筛选：显示sname和sage,不显示_id(_id默认会显示)
            //查询所有数据
            MongoCursor<Document>  cursor= collection.find().iterator();
            while(cursor.hasNext()){
                System.out.println(cursor.next().toJson());
            }
        }catch(Exception e){
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
        }
    }
    /**
     * 更新数据
     */
    public static void update(){
        try{
            MongoCollection<Document> collection = getCollection("School","student");  //数据库名:School 集合名:student
             //更新文档   将文档中sname='Mary'的文档修改为sage=22   
             collection.updateMany(Filters.eq("sname", "Mary"), new Document("$set",new Document("sage",22)));  
             System.out.println("更新成功！");
        }catch(Exception e){
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
        }
    }
    /**
     * 删除数据
     */
    public static void delete(){
        try{
            MongoCollection<Document> collection = getCollection("School","student");  //数据库名:School 集合名:student
                //删除符合条件的第一个文档  
            collection.deleteOne(Filters.eq("sname", "Bob"));  
            //删除所有符合条件的文档  
            //collection.deleteMany (Filters.eq("sname", "Bob"));
            System.out.println("删除成功！");
        }catch(Exception e){
            System.err.println( e.getClass().getName() + ": " + e.getMessage() );
        }
    }
}

NoSQL数据库的分布式算法

本文译自 Distributed Algorithms in NoSQL Databases
原文：NoSQL 数据库的分布式算法

系统的可扩展性是推动 NoSQL 运动发展的的主要理由，包含了分布式系统协调，故障转移，资源管理和许多其他特性。这么讲使得 NoSQL 听起来像是一个大筐，什么都能塞进去。尽管 NoSQL 运动并没有给分布式数据处理带来根本性的技术变革，但是依然引发了铺天盖地的关于各种协议和算法的研究以及实践。正是通过这些尝试逐渐总结出了一些行之有效的数据库构建方法。在这篇文章里，我将针对 NoSQL 数据库的分布式特点进行一些系统化的描述。

接下来我们将研究一些分布式策略，比如故障检测中的复制，这些策略用黑体字标出，被分为三段：

• 数据一致性。NoSQL 需要在分布式系统的一致性，容错性和性能，低延迟及高可用之间作出权衡，一般来说，数据一致性是一个必选项，所以这一节主要是关于数据复制和数据恢复。
• 数据放置。一个数据库产品应该能够应对不同的数据分布，集群拓扑和硬件配置。在这一节我们将讨论如何分布以及调整数据分布才能够能够及时解决故障，提供持久化保证，高效查询和保证集群中的资源（如内存和硬盘空间）得到均衡使用。
• 对等系统。像 leader election 这样的的技术已经被用于多个数据库产品以实现容错和数据强一致性。然而，即使是分散的的数据库（无中心）也要跟踪它们的全局状态，检测故障和拓扑变化。这一节将介绍几种使系统保持一致状态的技术。

数据一致性

众所周知，分布式系统经常会遇到网络隔离或是延迟的情况，在这种情况下隔离的部分是不可用的，因此要保持高可用性而不牺牲一致性是不可能的。这一事实通常被称作“CAP 理论”。然而，一致性在分布式系统中是一个非常昂贵的东西，所以经常需要在这上面做一些让步，不只是针对可用性，还有多种权衡。为了研究这些权衡，我们注意到分布式系统的一致性问题是由数据隔离和复制引起的，所以我们将从研究复制的特点开始：

• 可用性。在网络隔离的情况下剩余部分仍然可以应对读写请求。
• 读写延迟。读写请求能够在短时间内处理。
• 读写延展性。读写的压力可由多个节点均衡分担。
• 容错性。对于读写请求的处理不依赖于任何一个特定节点。
• 数据持久性。特定条件下的节点故障不会造成数据丢失。
• 一致性。一致性比前面几个特性都要复杂得多，我们需要详细讨论一下几种不同的观点。 但是我们不会涉及过多的一致性理论和并发模型，因为这已经超出了本文的范畴，我只会使用一些简单特点构成的精简体系。
• 原子写。假如数据库提供了 API，一次写操作只能是一个单独的原子性的赋值，避免写冲突的办法是找出每个数据的“最新版本”。这使得所有的节点都能够在更新结束时获得同一版本，而与更新的顺序无关，网络故障和延迟经常造成各节点更新顺序不一致。 数据版本可以用时间戳或是用户指定的值来表示。Cassandra 用的就是这种方法。
• 原子化的读-改-写。应用有时候需要进行 读-改-写 序列操作而非单独的原子写操作。假如有两个客户端读取了同一版本的数据，修改并且把修改后的数据写回，按照原子写模型，时间上比较靠后的那一次更新将会覆盖前一次。这种行为在某些情况下是不正确的（例如，两个客户端往同一个列表值中添加新值）。数据库提供了至少两种解决方法：
• 冲突预防。 读-改-写 可以被认为是一种特殊情况下的事务，所以分布式锁或是 PAXOS [20, 21] 这样的一致协议都可以解决这种问题。这种技术支持原子读改写语义和任意隔离级别的事务。另一种方法是避免分布式的并发写操作，将对特定数据项的所有写操作路由到单个节点上（可以是全局主节点或者分区主节点）。为了避免冲突，数据库必须牺牲网络隔离情况下的可用性。这种方法常用于许多提供强一致性保证的系统（例如大多数关系数据库，HBase，MongoDB）。
• 冲突检测。数据库跟踪并发更新的冲突，并选择回滚其中之一或是维持两个版本交由客户端解决。并发更新通常用向量时钟 [19] （这是一种乐观锁）来跟踪，或者维护一个完整的版本历史。这个方法用于 Riak, Voldemort, CouchDB.
• 写一致性。分区的数据库经常会发生写冲突。数据库应当能处理这种冲突并保证多个写请求不会被不同的分区所处理。这方面数据库提供了几种不同的一致性模型：
• 写后读一致性。在数据项 X 上写操作的效果总是能够被后续的 X 上的读操作看见。
• 读后读一致性。在一次对数据项 X 的读操作之后，后续对 X 的读操作应该返回与第一次的返回值相同或是更加新的值。
• 读写一致性。从读写的观点来看，数据库的基本目标是使副本趋同的时间尽可能短（即更新传递到所有副本的时间），保证最终一致性。除了这个较弱的保证，还有一些更强的一致性特点：

现在让我们仔细看看常用的复制技术，并按照描述的特点给他们分一下类。第一幅图描绘了不同技术之间的逻辑关系和不同技术在系统的一致性、扩展性、可用性、延迟性之间的权衡坐标。 第二张图详细描绘了每个技术。

复本因子是 4。读写协调者可以是一个外部客户端或是一个内部代理节点。

我们会依据一致性从弱到强把所有的技术过一遍：

• （A, 反熵） 一致性最弱，基于策略如下。写操作的时候选择任意一个节点更新，在读的时候如果新数据还没有通过后台的反熵协议传递到读的那个节点，那么读到的仍然是旧数据。（下一节会详细介绍反熵协议）。这种方法的主要特点是：
• 过高的传播延迟使它在数据同步方面不太好用，所以比较典型的用法是只作为辅助性的功能来检测和修复计划外的不一致。Cassandra 就使用了反熵算法来在各节点之间传递数据库拓扑和其他一些元数据信息。
• 一致性保证较弱：即使在没有发生故障的情况下，也会出现写冲突与读写不一致。
• 在网络隔离下的高可用和健壮性。用异步的批处理替代了逐个更新，这使得性能表现优异。
• 持久性保障较弱因为新的数据最初只有单个副本。
• （B） 对上面模式的一个改进是在任意一个节点收到更新数据请求的同时异步的发送更新给所有可用节点。这也被认为是定向的反熵。
• 与纯粹的反熵相比，这种做法只用一点小小的性能牺牲就极大地提高了一致性。然而，正式一致性和持久性保持不变。
• 假如某些节点因为网络故障或是节点失效在当时是不可用的，更新最终也会通过反熵传播过程来传递到该节点。
• （C） 在前一个模式中，使用提示移交技术 [8] 可以更好地处理某个节点的操作失败。对于失效节点的预期更新被记录在额外的代理节点上，并且标明一旦特点节点可用就要将更新传递给该节点。这样做提高了一致性，降低了复制收敛时间。
• （D, 一次性读写）因为提示移交的责任节点也有可能在将更新传递出去之前就已经失效，在这种情况下就有必要通过所谓的读修复来保证一致性。每个读操作都会启动一个异步过程，向存储这条数据的所有节点请求一份数据摘要（像签名或者 hash），如果发现各节点返回的摘要不一致则统一各节点上的数据版本。我们用一次性读写来命名组合了 A、B、C、D 的技术- 他们都没有提供严格的一致性保证，但是作为一个自备的方法已经可以用于实践了。
• （E, 读若干写若干） 上面的策略是降低了复制收敛时间的启发式增强。为了保证更强的一致性，必须牺牲可用性来保证一定的读写重叠。 通常的做法是同时写入 W 个副本而不是一个，读的时候也要读 R 个副本。
• 首先，可以配置写副本数 W>1。
• 其次，因为 R+W>N，写入的节点和读取的节点之间必然会有重叠，所以读取的多个数据副本里至少会有一个是比较新的数据（上面的图中 W=2, R=3, N=4 ）。这样在读写请求依序进行的时候（写执行完再读）能够保证一致性（对于单个用户的读写一致性），但是不能保障全局的读一致性。用下面图示里的例子来看，R=2，W=2，N=3，因为写操作对于两个副本的更新是非事务的，在更新没有完成的时候读就可能读到两个都是旧值或者一新一旧：

• 对于某种读延迟的要求，设置 R 和 W 的不同值可以调整写延迟与持久性，反之亦然。
• 如果 W<=N/2，并发的多个写入会写到不同的若干节点（如，写操作 A 写前 N/2 个，B 写后 N/2 个）。 设置 W>N/2 可以保证在符合回滚模型的原子读改写时及时检测到冲突。
• 严格来讲，这种模式虽然可以容忍个别节点的失效， 但是对于网络隔离的容错性并不好。在实践中，常使用”近似数量通过“这样的方法，通过牺牲一致性来提高某些情景下的可用性。
• （F, 读全部写若干）读一致性问题可以通过在读数据的时候访问所有副本（读数据或者检查摘要）来减轻。这确保了只要有至少一个节点上的数据更新新的数据就能被读取者看到。但是在网络隔离的情况下这种保证就不能起到作用了。
• （G, 主从） 这种技术常被用来提供原子写或者 冲突检测持久级别的读改写。为了实现冲突预防级别，必须要用一种集中管理方式或者是锁。最简单的策略是用主从异步复制。对于特定数据项的写操作全部被路由到一个中心节点，并在上面顺序执行。这种情况下主节点会成为瓶颈，所以必须要将数据划分成一个个独立的片区（不同片有不同的 master），这样才能提供扩展性。
• （H, Transactional Read Quorum Write Quorum and Read One Write All） 更新多个副本的方法可以通过使用事务控制技术来避免写冲突。 众所周知的方法是使用两阶段提交协议。但两阶段提交并不是完全可靠的，因为协调者失效可能会造成资源阻塞。 PAXOS 提交协议 [20, 21] 是更可靠的选择，但会损失一点性能。 在这个基础上再向前一小步就是读一个副本写所有副本，这种方法把所有副本的更新放在一个事务中，它提供了强容错一致性但会损失掉一些性能和可用性。

上面分析中的一些权衡有必要再强调一下：

• 一致性与可用性。 严密的权衡已经由 CAP 理论给出了。在网络隔离的情况下，数据库要么将数据集中，要么既要接受数据丢失的风险。
• 一致性与扩展性。 看得出即使读写一致性保证降低了副本集的扩展性，只有在原子写模型中才可以以一种相对可扩展的方式处理写冲突。原子读改写模型通过给数据加上临时性的全局锁来避免冲突。这表明， 数据或操作之间的依赖，即使是很小范围内或很短时间的，也会损害扩展性。所以精心设计数据模型，将数据分片分开存放对于扩展性非常重要。
• 一致性与延迟。 如上所述，当数据库需要提供强一致性或者持久性的时候应该偏向于读写所有副本技术。但是很明显一致性与请求延迟成反比，所以使用若干副本技术会是比较中允的办法。
• 故障转移与一致性/扩展性/延迟。有趣的是容错性与一致性、扩展性、延迟的取舍冲突并不剧烈。通过合理的放弃一些性能与一致性，集群可以容忍多达 up to 的节点失效。这种折中在两阶段提交与 PAXOS 协议的区别里体现得很明显。这种折中的另一个例子是增加特定的一致性保障，比如使用严格会话进程的“读己所写”，但这又增加了故障转移的复杂性 [22]。

反熵协议， 谣言传播算法

让我们从以下场景开始：

有许多节点，每条数据会在其中的若干的节点上面存有副本。每个节点都可以单独处理更新请求，每个节点定期和其他节点同步状态，如此一段时间之后所有的副本都会趋向一致。同步过程是怎样进行的？同步何时开始？怎样选择同步的对象？怎么交换数据？我们假定两个节点总是用较新版本的数据覆盖旧的数据或者两个版本都保留以待应用层处理。

这个问题常见于数据一致性维护和集群状态同步（如集群成员信息传播）等场景。虽然引入一个监控数据库并制定同步计划的协调者可以解决这个问题，但是去中心化的数据库能够提供更好的容错性。去中心化的主要做法是利用精心设计的传染协议[7]，这种协议相对简单，但是提供了很好的收敛时间，而且能够容忍任何节点的失效和网络隔离。尽管有许多类型的传染算法，我们只关注反熵协议，因为 NoSQL 数据库都在使用它。

反熵协议假定同步会按照一个固定进度表执行，每个节点定期随机或是按照某种规则选择另外一个节点交换数据，消除差异。有三种反风格的反熵协议：推，拉和混合。推协议的原理是简单选取一个随机节点然后把数据状态发送过去。在真实应用中将全部数据都推送出去显然是愚蠢的，所以节点一般按照下图所示的方式工作。

节点 A 作为同步发起者准备好一份数据摘要，里面包含了 A 上数据的指纹。节点 B 接收到摘要之后将摘要中的数据与本地数据进行比较，并将数据差异做成一份摘要返回给 A。最后，A 发送一个更新给 B，B 再更新数据。拉方式和混合方式的协议与此类似，就如上图所示的。

反熵协议提供了足够好的收敛时间和扩展性。下图展示了一个在 100 个节点的集群中传播一个更新的模拟结果。在每次迭代中，每个节点只与一个随机选取的对等节点发生联系。

可以看到，拉方式的收敛性比推方式更好，这可以从理论上得到证明[7]。而且推方式还存在一个“收敛尾巴”的问题。在多次迭代之后，尽管几乎遍历到了所有的节点，但还是有很少的一部分没受到影响。与单纯的推和拉方式相比， 混合方式的效率更高，所以实际应用中通常使用这种方式。反熵是可扩展的，因为平均转换时间以集群规模的对数函数形式增长。

尽管这些技术看起来很简单，仍然有许多研究关注于不同约束条件下反熵协议的性能表现。其中之一通过一种更有效的结构使用网络拓扑来取代随机选取 [10] 。在网络带宽有限的条件下调整传输率或使用先进的规则来选取要同步的数据 [9]。摘要计算也面临挑战，数据库会维护一份最近更新的日志以有助于摘要计算。

最终一致数据类型 Eventually Consistent Data Types

在上一节我们假定两个节点总是合并他们的数据版本。但要解决更新冲突并不容易，让所有副本都最终达到一个语义上正确的值出乎意料的难。一个众所周知的例子是 Amazon Dynamo 数据库[8]中已经删除的条目可以重现。

我们假设一个例子来说明这个问题：数据库维护一个逻辑上的全局计数器，每个节点可以增加或者减少计数。虽然每个节点可以在本地维护一个自己的值，但这些本地计数却不能通过简单的加减来合并。假设这样一个例子：有三个节点 A、B 和 C，每个节点执行了一次加操作。如果 A 从 B 获得一个值，并且加到本地副本上，然后 C 从 B 获得值，然后 C 再从 A 获得值，那么 C 最后的值是 4，而这是错误的。解决这个问题的方法是用一个类似于向量时钟[19]的数据结构为每个节点维护一对计数器[1]：

class Counter {
2     int[] plus 
3     int[] minus 
4     int NODE_ID 
5 
6     increment() { 
7         plus[NODE_ID]++ 
8     } 
9 
10    decrement() { 
11        minus[NODE_ID]++ 
12    } 
13 
14    get() { 
15        return sum(plus) – sum(minus) 
16    } 
17 
18    merge(Counter other) { 
19        for i in 1..MAX_ID { 
20            plus[i] = max(plus[i], other.plus[i]) 
21            minus[i] = max(minus[i], other.minus[i]) 
22        }
23    } 
24 }

Cassandra 用类似的方法计数[11]。利用基于状态的或是基于操作的复制理论也可以设计出更复杂的最终一致的数据结构。例如，[1]中就提及了一系列这样的数据结构，包括：

• 计数器（加减操作）
• 集合（添加和移除操作）
• 图（增加边或顶点，移除边或顶点）
• 列表（插入某位置或者移除某位置）

最终一致数据类型的功能通常是有限的，还会带来额外的性能开销。

数据放置

这部分主要关注控制在分布式数据库中放置数据的算法。这些算法负责把数据项映射到合适的物理节点上，在节点间迁移数据以及像内存这样的资源的全局调配。

均衡数据

我们还是从一个简单的协议开始，它可以提供集群节点间无缝的数据迁移。这常发生于像集群扩容（加入新节点），故障转移（一些节点宕机）或是均衡数据（数据在节点间的分布不均衡）这样的场景。如下图 A 中所描绘的场景 - 有三个节点，数据随便分布在三个节点上（假设数据都是 key-value 型）。

如果数据库不支持数据内部均衡，就要在每个节点上发布数据库实例，如上面图 B 所示。这需要手动进行集群扩展，停掉要迁移的数据库实例，把它转移到新节点上，再在新节点上启动，如图 C 所示。尽管数据库能够监控到每一条记录，包括 MongoDB, Oracle Coherence, 和还在开发中的 Redis Cluster 在内的许多系统仍然使用的是自动均衡技术。也即，将数据分片并把每个数据分片作为迁移的最小单位，这是基于效率的考虑。很明显分片数会比节点数多，数据分片可以在各节点间平均分布。按照一种简单的协议即可实现无缝数据迁移，这个协议可以在迁移数据分片的时候重定向客户的数据迁出节点和迁入节点。下图描绘了一个 Redis Cluster 中实现的 get（key）逻辑的状态机。

假定每个节点都知道集群拓扑，能够把任意 key 映射到相应的数据分片，把数据分片映射到节点。如果节点判断被请求的 key 属于本地分片，就会在本地查找（上图中上面的方框）。假如节点判断请求的 key 属于另一个节点 X，他会发送一个永久重定向命令给客户端（上图中下方的方框）。永久重定向意味着客户端可以缓存分片和节点间的映射关系。如果分片迁移正在进行，迁出节点和迁入节点会标记相应的分片并且将分片的数据加锁逐条加锁然后开始移动。迁出节点首先会在本地查找 key，如果没有找到，重定向客户端到迁入节点，假如 key 已经迁移完毕的话。这种重定向是一次性的，并且不能被缓存。迁入节点在本地处理重定向，但定期查询在迁移还没完成前被永久重定向。

动态环境中的数据分片和复制

我们关注的另一个问题是怎么把记录映射到物理节点。比较直接的方法是用一张表来记录每个范围的 key 与节点的映射关系，一个范围的 key 对应到一个节点，或者用 key 的 hash 值与节点数取模得到的值作为节点 ID。但是 hash 取模的方法在集群发生更改的情况下就不是很好用，因为增加或者减少节点都会引起集群内的数据彻底重排。导致很难进行复制和故障恢复。

有许多方法在复制和故障恢复的角度进行了增强。最著名的就是一致性 hash。网上已经有很多关于一致性 hash 的介绍了，所以在这里我只提供一个基本介绍，仅仅为了文章内容的完整性。下图描绘了一致性 hash 的基本原理：

一致性 hash 从根本上来讲是一个键值映射结构 - 它把键（通常是 hash 过的）映射到物理节点。键经过 hash 之后的取值空间是一个有序的定长二进制字符串，很显然每个在此范围内的键都会被映射到图 A 中 A、B、C 三个节点中的某一个。为了副本复制，将取值空间闭合成一个环，沿环顺时针前行直到所有副本都被映射到合适的节点上，如图 B 所示。换句话说，Y 将被定位在节点 B 上，因为它在 B 的范围内，第一个副本应该放置在 C，第二个副本放置在 A，以此类推。

这种结构的好处体现在增加或减少一个节点的时候，因为它只会引起临接区域的数据重新均衡。如图 C 所示，节点 D 的加入只会对数据项 X 产生影响而对 Y 无影响。同样，移除节点 B（或者 B 失效）只会影响 Y 和 X 的副本，而不会对 X 自身造成影响。但是，正如参考资料[8]中所提到的，这种做法在带来好处的同时也有弱点，那就是重新均衡的负担都由邻节点承受了，它们将移动大量的数据。通过将每个节点映射到多个范围而不是一个范围可以一定程度上减轻这个问题带来的不利影响，如图 D 所示。这是一个折中，它避免了重新均衡数据时负载过于集中，但是与基于模块的映射相比，保持了总均衡数量适当降低。

给大规模的集群维护一个完整连贯的 hash 环很不容易。对于相对小一点的数据库集群就不会有问题，研究如何在对等网络中将数据放置与网络路由结合起来很有意思。一个比较好的例子是 Chord 算法，它使环的完整性让步于单个节点的查找效率。Chord 算法也使用了环映射键到节点的理念，在这方面和一致性 hash 很相似。不同的是，一个特定节点维护一个短列表，列表中的节点在环上的逻辑位置是指数增长的（如下图）。这使得可以使用二分搜索只需要几次网络跳跃就可以定位一个键。

这张图画的是一个由 16 个节点组成的集群，描绘了节点 A 是如何查找放在节点 D 上的 key 的。 (A) 描绘了路由，(B) 描绘了环针对节点 A、B、C 的局部图像。在参考资料[15]中有更多关于分散式系统中的数据复制的内容。

按照多个属性的数据分片

当只需要通过主键来访问数据的时候，一致性 hash 的数据放置策略很有效，但是当需要按照多个属性来查询的时候事情就会复杂得多。一种简单的做法（MongoDB 使用的）是用主键来分布数据而不考虑其他属性。这样做的结果是依据主键的查询可以被路由到接个合适的节点上，但是对其他查询的处理就要遍历集群的所有节点。查询效率的不均衡造成下面的问题：

有一个数据集，其中的每条数据都有若干属性和相应的值。是否有一种数据分布策略能够使得限定了任意多个属性的查询会被交予尽量少的几个节点执行？

HyperDex 数据库提供了一种解决方案。基本思想是把每个属性视作多维空间中的一个轴，将空间中的区域映射到物理节点上。一次查询会被对应到一个由空间中多个相邻区域组成的超平面，所以只有这些区域与该查询有关。让我们看看参考资料[6]中的一个例子：

每一条数据都是一条用户信息，有三个属性 First Name 、Last Name 和 Phone Number。这些属性被视作一个三维空间，可行的数据分布策略是将每个象限映射到一个物理节点。像“First Name = John”这样的查询对应到一个贯穿 4 个象限的平面，也即只有 4 个节点会参与处理此次查询。有两个属性限制的查询对应于一条贯穿两个象限的直线，如上图所示，因此只有 2 个节点会参与处理。

这个方法的问题是空间象限会呈属性数的指数函数增长。结果就会是，只有几个属性限制的查询会投射到许多个空间区域，也即许多台服务器。将一个属性较多的数据项拆分成几个属性相对较少的子项，并将每个子项都映射到一个独立的子空间，而不是将整条数据映射到一个多维空间，这样可以一定程度上缓解这个问题：

这样能够提供更好的查询到节点的映射，但是增加了集群协调的复杂度，因为这种情况下一条数据会散布在多个独立的子空间，而每个子空间都对应各自的若干个物理节点，数据更新时就必须考虑事务问题。参考资料 [6]有这种技术的更多介绍和实现细节。

钝化副本

有的应用有很强的随机读取要求，这就需要把所有数据放在内存里。在这种情况下，将数据分片并把每个分片主从复制通常需要两倍以上的内存，因为每个数据都要在主节点和从节点上各有一份。为了在主节点失效的时候起到代替作用，从节点上的内存大小应该和主节点一样。如果系统能够容忍节点失效的时候出现短暂中断或性能下降，也可以不要分片。

下面的图描绘了 4 个节点上的 16 个分片，每个分片都有一份在内存里，副本存在硬盘上：

灰色箭头突出了节点 2 上的分片复制。其他节点上的分片也是同样复制的。红色箭头描绘了在节点 2 失效的情况下副本怎样加载进内存。集群内副本的均匀分布使得只需要预留很少的内存就可以存放节点失效情况下激活的副本。在上面的图里，集群只预留了 1/3 的内存就可以承受单个节点的失效。特别要指出的是副本的激活（从硬盘加载入内存）会花费一些时间，这会造成短时间的性能下降或者正在恢复中的那部分数据服务中断。

系统协调

在这部分我们将讨论与系统协调相关的两种技术。分布式协调是一个比较大的领域，数十年以来有很多人对此进行了深入的研究。这篇文章里只涉及两种已经投入实用的技术。关于分布式锁，consensus 协议以及其他一些基础技术的内容可以在很多书或者网络资源中找到，也可以去看参考资料[17, 18, 21]。

故障检测

故障检测是任何一个拥有容错性的分布式系统的基本功能。实际上所有的故障检测协议都基于心跳通讯机制，原理很简单，被监控的组件定期发送心跳信息给监控进程（或者由监控进程轮询被监控组件），如果有一段时间没有收到心跳信息就被认为失效了。除此之外，真正的分布式系统还要有另外一些功能要求：

• 自适应。故障检测应该能够应对暂时的网络故障和延迟，以及集群拓扑、负载和带宽的变化。但这有很大难度，因为没有办法去分辨一个长时间没有响应的进程到底是不是真的失效了，因此，故障检测需要权衡故障识别时间（花多长时间才能识别一个真正的故障，也即一个进程失去响应多久之后会被认为是失效）和虚假警报率之间的轻重。这个权衡因子应该能够动态自动调整。
• 灵活性。乍看上去，故障检测只需要输出一个表明被监控进程是否处于工作状态的布尔值，但在实际应用中这是不够的。我们来看参考资料[12]中的一个类似 MapReduce 的例子。有一个由一个主节点和若干工作节点组成的分布式应用，主节点维护一个作业列表，并将列表中的作业分配给工作节点。主节点能够区分不同程度的失败。如果主节点怀疑某个工作节点挂了，他就不会再给这个节点分配作业。其次，随着时间推移，如果没有收到该节点的心跳信息，主节点就会把运行在这个节点上的作业重新分配给别的节点。最后，主节点确认这个节点已经失效，并释放所有相关资源。
• 可扩展性和健壮性。失败检测作为一个系统功能应该能够随着系统的扩大而扩展。他应该是健壮和一致的，也即，即使在发生通讯故障的情况下，系统中的所有节点都应该有一个一致的看法（即所有节点都应该知道哪些节点是不可用的，那些节点是可用的，各节点对此的认知不能发生冲突，不能出现一部分节点知道某节点 A 不可用，而另一部分节点不知道的情况）

所谓的累计失效检测器[12]可以解决前两个问题，Cassandra[16]对它进行了一些修改并应用在产品中。其基本工作流程如下：

• 对于每一个被监控资源，检测器记录心跳信息到达时间 Ti。
• 计算在统计预测范围内的到达时间的均值和方差。
• 假定到达时间的分布已知（下图包括一个正态分布的公式），我们可以计算心跳延迟（当前时间 t_now 和上一次到达时间 Tc 之间的差值） 的概率，用这个概率来判断是否发生故障。如参考资料[12]中所建议的，可以使用对数函数来调整它以提高可用性。在这种情况下，输出 1 意味着判断错误（认为节点失效）的概率是 10%，2 意味着 1%，以此类推。

根据重要程度不同来分层次组织监控区，各区域之间通过谣言传播协议或者中央容错库同步，这样可以满足扩展性的要求，又可以防止心跳信息在网络中泛滥[14]。如下图所示（6 个故障检测器组成了两个区域，互相之间通过谣言传播协议或者像 ZooKeeper 这样的健壮性库来联系）：

协调者竞选

协调者竞选是用于强一致性数据库的一个重要技术。首先，它可以组织主从结构的系统中主节点的故障恢复。其次，在网络隔离的情况下，它可以断开处于少数的那部分节点，以避免写冲突。

Bully 算法是一种相对简单的协调者竞选算法。MongoDB 用了这个算法来决定副本集中主要的那一个。Bully 算法的主要思想是集群的每个成员都可以声明它是协调者并通知其他节点。别的节点可以选择接受这个声称或是拒绝并进入协调者竞争。被其他所有节点接受的节点才能成为协调者。节点按照一些属性来判断谁应该胜出。这个属性可以是一个静态 ID，也可以是更新的度量像最近一次事务 ID（最新的节点会胜出）。

下图的例子展示了 bully 算法的执行过程。使用静态 ID 作为度量，ID 值更大的节点会胜出：

1. 最初集群有 5 个节点，节点 5 是一个公认的协调者。
2. 假设节点 5 挂了，并且节点 2 和节点 3 同时发现了这一情况。两个节点开始竞选并发送竞选消息给 ID 更大的节点。
3. 节点 4 淘汰了节点 2 和 3，节点 3 淘汰了节点 2。
4. 这时候节点 1 察觉了节点 5 失效并向所有 ID 更大的节点发送了竞选信息。
5. 节点 2、3 和 4 都淘汰了节点 1。
6. 节点 4 发送竞选信息给节点 5。
7. 节点 5 没有响应，所以节点 4 宣布自己当选并向其他节点通告了这一消息。

协调者竞选过程会统计参与的节点数目并确保集群中至少一半的节点参与了竞选。这确保了在网络隔离的情况下只有一部分节点能选出协调者（假设网络中网络会被分割成多块区域，之间互不联通，协调者竞选的结果必然会在节点数相对比较多的那个区域中选出协调者，当然前提是那个区域中的可用节点多于集群原有节点数的半数。如果集群被隔离成几个区块，而没有一个区块的节点数多于原有节点总数的一半，那就无法选举出协调者，当然这样的情况下也别指望集群能够继续提供服务了）。

参考

• 《大数据技术原理与应用》教材官网
• NoSQL非关系型数据库简介
• NoSQL Databases Explained

博文：NoSQL数据库的分布式算法
https://taohuawu.club/nosql-distributed-algorithm
https://my.oschina.net/juliashine/blog/88173
https://highlyscalable.wordpress.com/2012/09/18/distributed-algorithms-in-nosql-databases