1、目录目录什么是什么是NoSQLNoSQL1NoSQLNoSQL种类与特点种类与特点2CAPCAP定理定理3ACIDACID与与BASEBASE4小结小结101最终一致性技术基础最终一致性技术基础5数据复制与分片数据复制与分片6NoSQLNoSQL数据库与云计算数据库与云计算7NoSQLNoSQL数据库与物联网数据库与物联网8NoSQLNoSQL数据库与区块链数据库与区块链91.1 什么是什么是NoSQL2n研究不同特点大数据存储的数据库技术；研究不同特点大数据存储的数据库技术；nNoSQLNoSQL数据库是非关系型数据存储的广义定数据库是非关系型数据存储的广义定义；义；n它不同于符合它不同于符
2、合ACIDACID理论的关系型数据库，理论的关系型数据库，数据存储不需要固定的表结构；数据存储不需要固定的表结构；n通常也不存在连接操作；通常也不存在连接操作；nNoSQLNoSQL数据库不使用传统的关系数据库模型数据库不使用传统的关系数据库模型，而是使用键值模型、列模型、文档模型、，而是使用键值模型、列模型、文档模型、图模型等方式存储数据。图模型等方式存储数据。n数据库应用需求变化数据库应用需求变化n支撑支撑OLTPOLTP型应用：事务处理型应用：事务处理,RDB,RDB的强项的强项n支撑支撑OLAPOLAP型应用：多维分析处理型应用：多维分析处理n新需求：支撑面向大数据的存储、处理与应用新
3、需求：支撑面向大数据的存储、处理与应用n新挑战新挑战none-size does not fit alln高性能、低成本高性能、低成本n不同类型非结构化数据存储与管理不同类型非结构化数据存储与管理n计算机新技术助力计算机新技术助力NoSQLNoSQLn多核、大内存，多核、大内存，集群等技术的普及集群等技术的普及1.1 什么是什么是NoSQLNoSQLNoSQL诞生原因诞生原因 麻省理工麻省理工Michael Stonebraker现代主流数据库系统架构的现代主流数据库系统架构的奠基人，奠基人，20142014年获图灵年获图灵奖。奖。n关系型数据库面临的问题关系型数据库面临的问题n扩展困难扩展困
4、难：由于存在类似：由于存在类似JoinJoin这样多表查询机这样多表查询机制，使得数据库在扩展方面很艰难；制，使得数据库在扩展方面很艰难；n读写慢读写慢：这种情况主要发生在数据量达到一定：这种情况主要发生在数据量达到一定规模时由于关系型数据库系统逻辑复杂，使得规模时由于关系型数据库系统逻辑复杂，使得容易发生死锁等并发问题，所以导致大数据库容易发生死锁等并发问题，所以导致大数据库应用场景中读写速度下滑非常严重；应用场景中读写速度下滑非常严重；n成本高成本高：企业级数据库的：企业级数据库的LicenseLicense价格很惊人价格很惊人，并且随着系统规模，并且随着系统规模越越大，成本越高；大，成本
5、越高；n有限的支撑容量有限的支撑容量：现有关系型解决方案还无法：现有关系型解决方案还无法支撑支撑GoogleGoogle这样海量的数据存储；这样海量的数据存储；1.1 什么是什么是NoSQLNoSQLNoSQL诞生原因诞生原因 1.1 什么是什么是NoSQLNoSQLNoSQL诞生原因诞生原因 n大大数据库存储与管理新需求呼吁技术创新数据库存储与管理新需求呼吁技术创新 n低延迟的读写速度低延迟的读写速度：应用快速地响应能极大地提：应用快速地响应能极大地提升用户的满意度；升用户的满意度；n支撑海量的数据和流量支撑海量的数据和流量：对于互联网等企业级大：对于互联网等企业级大应用而言，需要高效存储处
6、理应用而言，需要高效存储处理PBPB级的数据和百万级的数据和百万级的并发访问量；级的并发访问量；n大规模集群的管理大规模集群的管理：系统管理员希望分布式应用：系统管理员希望分布式应用能更简单的部署和管理；能更简单的部署和管理；n尽可能地降低尽可能地降低运营成本运营成本：ITIT经理们希望在硬件成经理们希望在硬件成本、软件成本和人力成本能够有大幅度地降低；本、软件成本和人力成本能够有大幅度地降低；1.1 什么是什么是NoSQL典型的典型的共性共性需求需求n假设失效是必然发生的假设失效是必然发生的:需要具有需要具有高容错性。高容错性。nNOSQLNOSQL实现都建立在硬盘、机器和网络都会经常性失效
7、假设之上。实现都建立在硬盘、机器和网络都会经常性失效假设之上。n不能彻底阻止这些失效，需要让系统能够在即使非常极端的条件下也不能彻底阻止这些失效，需要让系统能够在即使非常极端的条件下也能应付这些失效。能应付这些失效。n对数据进行分区：对数据进行分区：需要高性能需要高性能n分布式存储分布式存储，将读写操作的负载分布到了不同的机器上，将读写操作的负载分布到了不同的机器上n提高数据存储与访问的并发性。提高数据存储与访问的并发性。n保存同一数据的多个副本：需要保存同一数据的多个副本：需要具有具有高可用性。高可用性。nNOSQLNOSQL提供数据副本机制，副本个数往往可配置提供数据副本机制，副本个数往往
8、可配置n查询支持查询支持n在这个方面，不同的实现有相当本质的区别。不同实现的一个共性在在这个方面，不同的实现有相当本质的区别。不同实现的一个共性在于哈希表中的于哈希表中的 key/value key/value 匹配。匹配。1.2 NoSQL分分类类与与特点特点7类型类型Top 3代表代表特点特点图图数据库数据库（Graph DBMS）Neo4jMicrosoft Azure Cosmos DB（Multi-model）OrientDB（Multi-model）图型数据的最佳存储。相比使用传统关系数据库性能更优，存储模式设计与使用更加灵活、简单。文档文档数据库数据库（Document Stor
9、es）MongoDBAmazon DynamoDB（Multi-model）CoucHBase 文档存储一般用类似JSON（JavaScript Object Notation）的格式存储，存储的内容是文档型的嵌套结构。可以对某些字段建立索引，实现类似关系数据库的某些功能。键值数据库键值数据库（KV KV DBMS）Redis（Multi-model）Amazon DynamoDB（Multi-model）Microsoft Azure Cosmos DB（Multi-model）可以通过Key快速查询到其Value。一般来说，存储不管Value的格式，照单全收。列族存储列族存储（Wide C
10、olumn Stores）CassandraHBaseMicrosoft Azure Cosmos DB（Multi-model）顾名思义，是按列存储数据的。最大的特点是方便存储结构化和半结构化数据，对某一列或者某几列的查询有非常大的性能优势。https:/db- 截止2019年11月排名如下表1.2 NoSQL种类与种类与特点特点8类型类型Top 3代表代表特点特点时序时序数据库数据库（Time Series DBMS）InfluxDBKdb+Prometheus时间序列数据库用于支撑时间序列数据的优化存储，每个条目都有一个相关的时间戳。时间序列数据可以来自传感器、智能电表等，或可以存储一个
11、高频股票交易系统的股票价格波动情况。对象存储对象存储(Object oriented DBMS)InterSystems Cach（Multi-model）Versant Object DBObjectStore通过类似面向对象语言的语法操作数据库，通过对象的方式存取数据。XML数据库数据库MarkLogicOracle Berkeley DBVirtuoso 可以高效地存储XML数据，并支持XML的内部查询语法，如XQuery、Xpath等。原生类XML DB有BaseX等。RDF数据库数据库MarkLogic（Multi-model）Virtuoso（Multi-model）Apache
12、Jena-TDB资源描述框架存储数据库是一种信息的描述方法，最初用于描述元数据。目前主要用于语义网、知识图谱的存储。资源描述框架存储数据库主要以主语、谓语、宾语三元组形式表示信息。搜索引擎搜索引擎（Search Engines）ElasticsearchSplunkSolr 搜索引擎是用于数据内容搜索的NoSQL数据库管理系统。除了这种应用的一般优化，专业化数据库通常还支持复杂搜索表达式、全文搜索、源搜索、搜索结果的排序和分组、空间搜索和高扩展性分布式搜索等功能。NoSQL DB的一般共性特点的一般共性特点n1 1）不需要预定义模式不需要预定义模式：不需要事先定义数据模式：不需要事先定义数据模
13、式，预定义表结构。数据中的每条记录都可能有不同，预定义表结构。数据中的每条记录都可能有不同的属性和格式，当插入数据时，并不需要预先定义的属性和格式，当插入数据时，并不需要预先定义它们的模式；它们的模式；n2 2）无共享架构无共享架构：相对于将所有数据存储在网络：相对于将所有数据存储在网络中中的的存储存储区域全区域全共享架构，共享架构，NoSQLNoSQL往往将数据划分往往将数据划分后存储在各个本地服务器上。因为从本地磁盘读取后存储在各个本地服务器上。因为从本地磁盘读取数据的性能往往好于通过网络传输读取数据的性能数据的性能往往好于通过网络传输读取数据的性能，从而，从而提高系统提高系统的的性能。性
14、能。1.2 NoSQL种类与种类与特点特点n3 3）弹性可扩展弹性可扩展：可以在系统运行的时候，：可以在系统运行的时候，动态增加或者删除结点。不需要停机维护，动态增加或者删除结点。不需要停机维护，数据可以自动数据可以自动迁移。迁移。n4 4）分区分区：相对于将数据存放于同一个节点：相对于将数据存放于同一个节点，NoSQLNoSQL数据库需要将数据进行分区，将记数据库需要将数据进行分区，将记录分散在多个节点上面。并且通常分区的同录分散在多个节点上面。并且通常分区的同时还要做复制。这样既提高了并行性能，又时还要做复制。这样既提高了并行性能，又能保证没有单点失效的问题能保证没有单点失效的问题；n5)
15、5)分发查询到数据分发查询到数据，而非数据到查询；，而非数据到查询；1.2 NoSQL种类与种类与特点特点n6 6）异步复制异步复制：和：和RAIDRAID存储系统不同的是，存储系统不同的是，NoSQLNoSQL中的复制，中的复制，往往是基于日志的异步复往往是基于日志的异步复制制。这样，数据就可以尽快地写入一个节点。这样，数据就可以尽快地写入一个节点，而不会被网络传输引起迟延。缺点是并不，而不会被网络传输引起迟延。缺点是并不总是能保证一致性，这样的方式在出现故障总是能保证一致性，这样的方式在出现故障的时候，可能会丢失少量的数据；的时候，可能会丢失少量的数据；n7 7）BASEBASE：相对于事
16、务严格的：相对于事务严格的ACIDACID特性，特性，NoSQLNoSQL数据库保证的是数据库保证的是BASEBASE特性。特性。1.2 NoSQL种类与种类与特点特点图数据库图数据库：将：将数据存储在图（数据存储在图（GraphGraph）结构中）结构中。如。如下图示下图示是一个简单的有向无环图。是一个简单的有向无环图。1.2 NoSQL种类与种类与特点特点n图图术语术语：节点、边、度、路径、最短距离、连通：节点、边、度、路径、最短距离、连通图、全连通图、子图等等。图、全连通图、子图等等。n图数据库图数据库可以看作是结点与关系的集合，可以看作是结点与关系的集合，图数据图数据库库就是将数据存储
17、在拥有属性的结点中，并用关就是将数据存储在拥有属性的结点中，并用关系将这些结点组织起来。系将这些结点组织起来。n数据数据存储的重要目的是为了检索存储的重要目的是为了检索。图。图的查找与搜的查找与搜索可以通过遍历算法索可以通过遍历算法完成。完成。n解决的查询问题根据解决的查询问题根据算法，从开始结点到与之相算法，从开始结点到与之相连的结点查询诸如连的结点查询诸如“某个人好友某个人好友的的好友的好友是好友的好友是哪些人哪些人”等问题等问题。n节点与节点间的距离（？）可以反映节点间关系节点与节点间的距离（？）可以反映节点间关系的紧密程度。的紧密程度。1.2 NoSQL种类与种类与特点特点n数据可以存
18、储为一个树形结构数据可以存储为一个树形结构n文档文档数据库就是大量文档树形结构的集合数据库就是大量文档树形结构的集合n数据存储模式重点是树形、森林结构的抽象，文档模式可变数据存储模式重点是树形、森林结构的抽象，文档模式可变根节点根节点分支分支分支分支分支分支分支分支值值分支分支分支分支值值值值值值客户客户客户客户1客户客户n标识标识姓名姓名地址地址张三张三城市城市海淀区西土海淀区西土城路城路10号号北京北京112街道街道1.2 NoSQL种类与种类与特点特点文档文档类类：MongoDBMongoDBMongo Server-mongod实例，存储实际数据的模块。Config Server-存储
19、集群的元数据，如分片信息、数据块映射等。config服务器保存了两个映射关系，一个是key区间的数据都存放在那些chunk上的映射关系，另一个是chunk都存放在哪些分片节点上的映射关系。Route Server 客户端访问路由（统一接入点），查询优化，数据合并、排序、裁剪，请求推送等。客户端统一访问路由节点mongos，来进行数据操作。路由节点先访问config服务器获取信息，找到数据真正存放位置，然后再对其进行操作。文档文档类：类：MongoDBMongoDB1.2 NoSQL种类与种类与特点特点1.2 NoSQL种类与种类与特点特点键值键值类：类：RedisRedisn简洁简洁：数据主要
20、采用：数据主要采用Key-ValueKey-Value形式存储，形式存储，键为键为唯一标识符。唯一标识符。n高速高速：数据驻留内存，：数据驻留内存，RedisRedis也支持将内存中的数据持久化到也支持将内存中的数据持久化到磁盘中，重启的时候可以再次加载进行使用，同时保障数据的磁盘中，重启的时候可以再次加载进行使用，同时保障数据的高性能访问及可靠性。高性能访问及可靠性。n易易扩展：根据系统负载量，灵活添加或删除服务器。扩展：根据系统负载量，灵活添加或删除服务器。n对对键可设置失效时间，丰富的配置管理功能可以精准地设定数键可设置失效时间，丰富的配置管理功能可以精准地设定数据服务级别。据服务级别。
21、1.2 NoSQL种类与种类与特点特点列族数据库：列族数据库：HBASEHBASE，大数据技术基础中有学习，大数据技术基础中有学习该类数据库课程重点学习：该类数据库课程重点学习：CassandraCassandra1.3 CAP定理定理n一致性一致性（ConsistencyConsistency）n任何一个读操作总是能读取到之前完成的写操作结果任何一个读操作总是能读取到之前完成的写操作结果，也就是在分布式环境中，多点的数据是一致的；，也就是在分布式环境中，多点的数据是一致的；n可用性可用性（AvailabilityAvailability）n每一个操作总是能够在确定的时间内返回，也就是系每一个
22、操作总是能够在确定的时间内返回，也就是系统随时都是可用的。统随时都是可用的。n分区容忍性分区容忍性（Partition TolerancePartition Tolerance）n在出现网络分区（比如断网）的情况下，分离的系统在出现网络分区（比如断网）的情况下，分离的系统也能正常运行。也能正常运行。一个分布式系统不能同时满足一致一个分布式系统不能同时满足一致性，可用性和分区容错性这三个需性，可用性和分区容错性这三个需求求 ，最多只能同时满足两个。，最多只能同时满足两个。CAPCAP理论理论 1.3 CAP定理定理数据库数据库按按CAPCAP分类分类 （1 1）关注一致性和可用性的）关注一致性和
23、可用性的 (CA)(CA)n这些数据库对于分区容忍性方面比较弱，主这些数据库对于分区容忍性方面比较弱，主要采用复制（要采用复制（ReplicationReplication）这种方式来保证）这种方式来保证数据的安全性，常见的数据的安全性，常见的CACA系统有：系统有：n传统关系型数据库，比如传统关系型数据库，比如PostgresPostgres和和MySQLMySQL等等(Relational)(Relational)nVerticaVertica(Column-oriented)(Column-oriented)nAster Data(Relational)Aster Data(Relati
24、onal)nGreenplumGreenplum(Relational)(Relational)1.3 CAP定理定理（2 2）关注一致性和分区容忍性的）关注一致性和分区容忍性的(CP)(CP)n这种系统将数据分布在多个网络分区的节点上，并保证这这种系统将数据分布在多个网络分区的节点上，并保证这些数据的一致性，但是对于可用性的支持方面有问题，比些数据的一致性，但是对于可用性的支持方面有问题，比如当集群出现问题的话，节点有可能因无法确保数据是一如当集群出现问题的话，节点有可能因无法确保数据是一致性的而拒绝提供服务，主要的致性的而拒绝提供服务，主要的CPCP系统有：系统有：nBigTableBig
25、Table(Column-oriented)(Column-oriented)nHypertableHypertable(Column-oriented)(Column-oriented)nHBaseHBase(Column-oriented)(Column-oriented)nMongoDBMongoDB(Document)(Document)nTerrastoreTerrastore(Document)(Document)nRedisRedis(Key-value)(Key-value)nScalarisScalaris(Key-value)(Key-value)nMemcacheDBMe
26、mcacheDB(Key-value)(Key-value)nBerkeley DB(Key-value)Berkeley DB(Key-value)1.3 CAP定理定理（3 3）关于可用性和分区容忍性的）关于可用性和分区容忍性的(AP)(AP)n这类系统主要以实现这类系统主要以实现“最终一致性（最终一致性（Eventual ConsistencyEventual Consistency）”来确保可用性和分区容忍性，来确保可用性和分区容忍性，APAP的系统有：的系统有：nDynamo(Key-value)Dynamo(Key-value)nVoldemortVoldemort(Key-val
27、ue)(Key-value)nTokyo Cabinet(Key-value)Tokyo Cabinet(Key-value)nKAI(Key-value)KAI(Key-value)nCassandra(Column-oriented)Cassandra(Column-oriented)nCouchDBCouchDB(Document-oriented)(Document-oriented)nSimpleDBSimpleDB(Document-oriented)(Document-oriented)nRiakRiak(Document-oriented)(Document-oriented)
28、1.3 CAP定理定理关系数据库关系数据库 VSVS NoSQLNoSQL n关系数据库关系数据库n表都是存储一些格式表都是存储一些格式化的数据结构化的数据结构n每个元组字段的组成每个元组字段的组成都一样都一样n即使不是每个元组都即使不是每个元组都需要所有的字段，但需要所有的字段，但数据库会为每个元组数据库会为每个元组分配所有的字段分配所有的字段n这样的结构可以便于这样的结构可以便于表与表之间进行连接表与表之间进行连接等操作等操作nNoSQLNoSQLn以键值对存储，它以键值对存储，它的结构不固定的结构不固定n每一个元组可以有每一个元组可以有不一样的字段不一样的字段n每个元组可以根据每个元组可
29、以根据需要增加一些自己需要增加一些自己的键值对的键值对n不会局限于固定的不会局限于固定的结构，可以减少一结构，可以减少一些时间和空间的开些时间和空间的开销销1.4 ACID与与BASEn关系数据库关系数据库n关系型数据库中强调关系型数据库中强调ACIDACID分别是分别是n原子性原子性（AtomicityAtomicity）n 一致性一致性（ConsistencyConsistency）n 隔离性隔离性（IsolationIsolation）n持久性持久性（DurabilityDurability）nACIDACID的目的就是通过的目的就是通过事事务务支持，保证数据的完支持，保证数据的完整性和
30、正确性整性和正确性nNoSQLNoSQLn弱弱一致性的理论一致性的理论BASEBASEnBASEBASE分别分别是：是：nBasically AvailableBasically AvailablenSoft-stateSoft-statenEventual Eventual ConsistencyConsistency1.4 ACID与与BASE251.4 ACID与与BASEn基本可用性基本可用性：分布式系统在出现不可预知故：分布式系统在出现不可预知故障的时候，允许损失部分可用性。障的时候，允许损失部分可用性。n软状态软状态：允许系统中的数据存在中间状态，：允许系统中的数据存在中间状态，并
31、认为该中间状态的存在不会影响系统的整并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。本之间进行数据同步的过程存在延时。n最终一致性最终一致性：BASEBASE系统显著的特点是要保系统显著的特点是要保证在短时间内，即使有不同步的风险，也要证在短时间内，即使有不同步的风险，也要允许新数据能够被存储。所有的数据副本，允许新数据能够被存储。所有的数据副本，在经过一段时间的同步后，最终能够达到一在经过一段时间的同步后，最终能够达到一个一致的状态。个一致的状态。1.5 最终一致性技术基础最终一致性技术基础2
32、6nNoSQLNoSQL分布式集群系统是由多个节点（指服分布式集群系统是由多个节点（指服务器、存储设备等）务器、存储设备等）构成构成n由于由于网络异常、服务器故障等原因，节点并网络异常、服务器故障等原因，节点并不总能保证正常工作，特别是在节点数量很不总能保证正常工作，特别是在节点数量很大的时候，出现异常状况在所难免大的时候，出现异常状况在所难免。n为了保证系统的正常运行，分布式系统中对为了保证系统的正常运行，分布式系统中对于数据的存储采用多数据副本来保证高可用于数据的存储采用多数据副本来保证高可用性，这个过程对于用户来说是透明的。性，这个过程对于用户来说是透明的。n如何保障多副本数据的最终一致
33、性？如何保障多副本数据的最终一致性？1.5.1一致性问题一致性问题27n按照服务保障能力的不同，客户端访问一致性可以按照服务保障能力的不同，客户端访问一致性可以分为以下几个类型分为以下几个类型。n严格严格一致性一致性：语义上相当于只存在一份数据。任何更新：语义上相当于只存在一份数据。任何更新看上去都是即时发生的。看上去都是即时发生的。n“读己之所写读己之所写”一致性一致性：客户端可立即看到自己所作的：客户端可立即看到自己所作的更新，且客户端可在不同请求之间切换服务器，但不能更新，且客户端可在不同请求之间切换服务器，但不能立即看到其他客户端所作的更新。立即看到其他客户端所作的更新。n会话会话一致
34、性一致性：对于客户端在同一会话作用域中发起的请：对于客户端在同一会话作用域中发起的请求，通常绑定到同一台服务器，提供求，通常绑定到同一台服务器，提供“读己之所写读己之所写”一一致性。致性。n单调单调读一致性读一致性：保证时间上的单调性，保证客户端在未：保证时间上的单调性，保证客户端在未来的请求中，只会读到比当前更新的数据。来的请求中，只会读到比当前更新的数据。n最终最终一致性一致性：这是最弱的一种保证。在更新的过程中，：这是最弱的一种保证。在更新的过程中，客户端可能看到不一致的视图客户端可能看到不一致的视图。1.5.2 Quorum的的NWR策略策略28nQuoromQuorom 机制是一种分
35、布式系统中常用的，用来保证机制是一种分布式系统中常用的，用来保证数据冗余和最终一致性的投票算法，其主要数学思数据冗余和最终一致性的投票算法，其主要数学思想来源于鸽巢原理想来源于鸽巢原理。nQuorumQuorum的的NWRNWR策略中策略中N N代表总的节点数量，代表总的节点数量，WW代表代表写的节点数量，写的节点数量，R R代表读的节点数量代表读的节点数量。nQuoromQuorom机制中分布式系统中的每一份数据拷贝对象机制中分布式系统中的每一份数据拷贝对象都被赋予一票。每一个操作必须要获得最小的读票都被赋予一票。每一个操作必须要获得最小的读票数（数（VrVr）或者最小的写票数）或者最小的写
36、票数(VwVw）才能读或者写）才能读或者写。1.5.2 Quorum的的NWR策略策略29n如果如果一个系统有一个系统有V V票（意味着一个数据对象有票（意味着一个数据对象有V V份冗份冗余拷贝），那么这最小读写票数必须满足：余拷贝），那么这最小读写票数必须满足：（1 1）VrVr+VwVw V V （2 2）VwVw V/2V/2n第第1 1条规条规则保证了一个数据不会被同时读写则保证了一个数据不会被同时读写。n第第2 2条规条规则保证了数据的串行化修改则保证了数据的串行化修改。nQuorumQuorum的读写最小票数可以用来作为系统在读、写的读写最小票数可以用来作为系统在读、写性能方面的一
37、个可调节参数。写票数性能方面的一个可调节参数。写票数VwVw越大，则读越大，则读票数票数VrVr越小，这时候系统写的开销就大。反之，则越小，这时候系统写的开销就大。反之，则写的开销就小。写的开销就小。1.5.2 Quorum的的NWR策略策略30n读数读数据据：n假设共有假设共有N N个数据副本，其中个数据副本，其中K K个已经更新，个已经更新，N-KN-K个未更新个未更新，那么任意读取，那么任意读取 N-K+1N-K+1个副本数据的时候就必定至少有个副本数据的时候就必定至少有1 1个是属于更新了的个是属于更新了的K K个里面的，也就是个里面的，也就是 Quorum Quorum 的的交集交集
38、n只需只需比较读取的比较读取的N-K+1N-K+1数据，并将其中版本数据，并将其中版本最高的那个最高的那个数数据返回据返回给用户就可以得到最新更新的给用户就可以得到最新更新的数据。数据。n写数据写数据：n只需要完成写只需要完成写K(K(大于大于N/2)N/2)个副本的更新后，就可以告诉客个副本的更新后，就可以告诉客户端操作完成，而不需要全部户端操作完成，而不需要全部写入完成；写入完成；n当然当然告诉用户完成操作后，系统内部还是会告诉用户完成操作后，系统内部还是会继续把继续把剩余的剩余的副本更新，这对于用户是透明的。副本更新，这对于用户是透明的。1.5.3 Paxos算法简介算法简介31nPax
39、osPaxos算法算法是是Leslie Leslie LamportLamport于于19901990年提出的，年提出的，类似于解决类似于解决拜占庭将军问题拜占庭将军问题，基于消息传递，基于消息传递解决分布式系统中的一致性问题解决分布式系统中的一致性问题。n一个被一个被PaxosPaxos管理的系统实际上谈论的是值管理的系统实际上谈论的是值状态和状态和跟踪的问题。跟踪的问题。nCassandraCassandra、GoogleGoogle的分布式锁服务的分布式锁服务ChubbyChubby等等采用的都是采用的都是PaxosPaxos算法进行一致性管理算法进行一致性管理。nPaxosPaxos完
40、成一次写操作需要两完成一次写操作需要两次交互过程，次交互过程，分别是分别是prepare/promiseprepare/promise和和propose/acceptpropose/accept。1.5.3 Paxos算法简介算法简介32nPaxosPaxos一致性一致性算法执行过程算法执行过程1.5.3 Paxos算法简介算法简介33nPaxosPaxos一致性一致性算法执行算法执行过程过程n第一次由提交者（第一次由提交者（LeaderLeader）向所有其他服务器发）向所有其他服务器发出出PreparePrepare消息请求准备，所有服务器中大多数消息请求准备，所有服务器中大多数如果回复诺
41、言（如果回复诺言（promisepromise）就表示准备好了，可）就表示准备好了，可以接受写入以接受写入；n第二第二次提交者向所有服务器发出正式建议次提交者向所有服务器发出正式建议ProposePropose，所有服务器中大多数如果回复已经接，所有服务器中大多数如果回复已经接收（收（acceptaccept）就表示成功）就表示成功。n这里这里大多数的含义一般指超过半数以上，即至大多数的含义一般指超过半数以上，即至少少N/2+1N/2+1个节点，个节点，N N为节点总数。为节点总数。1.5.3 Paxos算法简介算法简介34nPaxosPaxos一致性一致性算法执行算法执行过程过程n接受的过程
42、可能会发生失败，在回复了诺言消接受的过程可能会发生失败，在回复了诺言消息以后，在接受到息以后，在接受到AcceptAccept消息之前，如果有足够消息之前，如果有足够多的服务器正好在这个时间段失败，那么执行多的服务器正好在这个时间段失败，那么执行接受行为只能是少数接受行为只能是少数服务器；服务器；nPaxosPaxos算法不允许在没有达成共识情况下任何写算法不允许在没有达成共识情况下任何写操作发生，这种坏的情况在实践中经常通过操作发生，这种坏的情况在实践中经常通过重重复接受阶段复接受阶段来让大多数节点最终来让大多数节点最终接受；接受；nPaxosPaxos算法中会维护一个全局唯一的序列算法中会
43、维护一个全局唯一的序列号。号。序序列号是由建议流程列号是由建议流程产生，产生，它定义了接受流程应它定义了接受流程应该准备接受该准备接受带有最新序列带有最新序列号的建议号的建议，序列，序列号是号是算法的算法的关键；关键；1.5.4 Raft算法算法简介简介35nRaftRaft算法算法是是由斯坦福大学由斯坦福大学Diego Diego OngaroOngaro博士在博士在20142014年提出的一种更易于理解的分布式架构年提出的一种更易于理解的分布式架构中日志一致性管理算法中日志一致性管理算法。n相比于相比于PaxosPaxos，RaftRaft算法更容易理解，也更容算法更容易理解，也更容易应用
44、到实际的系统当中。易应用到实际的系统当中。RaftRaft算法是算法是ZookeeperZookeeper框架的核心算法，也是区块链中联框架的核心算法，也是区块链中联盟链采用比较多的共识算法盟链采用比较多的共识算法。nRaftRaft算法中，分布式系统中的节点有三种角算法中，分布式系统中的节点有三种角色色。n领导者、领导者、候选者、追随者候选者、追随者36nRaftRaft算法作用示意算法作用示意1.5.4 Raft算法简介算法简介37nRaftRaft算法三种算法三种节点节点角色作用角色作用n领导者领导者（LeaderLeader）：只有一个，负责接收客户端：只有一个，负责接收客户端的请求，
45、将日志复制到其他节点并告知其他节的请求，将日志复制到其他节点并告知其他节点何时应用这些日志是安全的。点何时应用这些日志是安全的。n候选候选者（者（CandidateCandidate）：通常多个，用于选举：通常多个，用于选举LeaderLeader的一种角色。的一种角色。n追随者追随者（FollowerFollower）：通常多个，负责响应来自：通常多个，负责响应来自LeaderLeader或者或者CandidateCandidate的请求。的请求。1.5.4 Raft算法简介算法简介38nRaftRaft算法思想算法思想n类似民主选举，领导者由民众投票选举产生，集类似民主选举，领导者由民众投
46、票选举产生，集群刚开始没有领导者，所有服务器节点都是群刚开始没有领导者，所有服务器节点都是追随追随者；者；n接下来接下来进行选举，角色转换为候选者参与投票，进行选举，角色转换为候选者参与投票，每台服务器只能投一票，得票超过半数以上的当每台服务器只能投一票，得票超过半数以上的当选为领导者，并设定这届领导者的任期（选为领导者，并设定这届领导者的任期（TermTerm），从而选举，从而选举结束；结束；n其他其他候选人转换为追随者，并无条件服从领导者候选人转换为追随者，并无条件服从领导者的领导的领导。nRaftRaft把时间切割为任意长度的任期，每个任期都把时间切割为任意长度的任期，每个任期都有一个任
47、期号，采用连续的整数。有一个任期号，采用连续的整数。1.5.4 Raft算法简介算法简介39nRaftRaft算法思想三类角色状态转换如算法思想三类角色状态转换如图所图所示示1.5.4 Raft算法简介算法简介40nRaftRaft算法从时间角度算法从时间角度看任期看任期，如，如图所图所示，每次选举示，每次选举如果成功则由领导者来负责集群中的事务及状态管如果成功则由领导者来负责集群中的事务及状态管理，有时也可能出现选举失败，则需要重新选举直理，有时也可能出现选举失败，则需要重新选举直到选举成功，如到选举成功，如图中图中的的t3 t3情况。情况。1.5.4 Raft算法简介算法简介41n基于基于
48、LeaderLeader的方法，的方法，RaftRaft算法算法可分解可分解成三个子成三个子问题问题n领导者领导者选举选举(Leader Election)(Leader Election)：原来的领导者挂掉：原来的领导者挂掉后，必须选出一个新的领导者，候选者可以自己后，必须选出一个新的领导者，候选者可以自己选自己。选自己。n日志日志复制复制(Log Replication)(Log Replication)：领导者从客户端接收：领导者从客户端接收日志，并向日志，并向FollowerFollower们发出指令，比如进行日志复们发出指令，比如进行日志复制。制。n安全性安全性(Safety)(Sa
49、fety)：如果有任意的：如果有任意的ServerServer将日志项回放将日志项回放到状态机中了，那么其他的到状态机中了，那么其他的ServerServer只会回放相同的只会回放相同的日志项。日志项。1.5.4 Raft算法简介算法简介42n领导者领导者选举选举(Leader Election)(Leader Election)：要要开始一次选举过程，开始一次选举过程，Follower Follower 会给当前会给当前termterm加加1 1并且转换成并且转换成CandidateCandidate状态，并行地状态，并行地向集群中的其他服务器节点发送请求投票的消息来给自己投向集群中的其他服
50、务器节点发送请求投票的消息来给自己投票。候选人的状态维持直到以下任何一个条件发生。票。候选人的状态维持直到以下任何一个条件发生。n(1(1)自己自己赢得这次选举赢得这次选举。给所有其它节点。给所有其它节点发送这个信息，发送这个信息，这样所有节点都会转成这样所有节点都会转成FollowerFollower。n(2(2)其他其他的服务器成为领导者的服务器成为领导者。如果。如果LeaderLeader的的termterm大于或等大于或等于自身的于自身的termterm，则该，则该Candidate Candidate 会转成会转成FollowerFollower；否则拒绝；否则拒绝该该 Leader
