《NoSQL数据库技术课件(全)全书教学教程完整版电子教案最全幻灯片.pptx》由会员分享，可在线阅读，更多相关《NoSQL数据库技术课件(全)全书教学教程完整版电子教案最全幻灯片.pptx（676页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、NoSQL数据库技术数据库技术第第1章章 NoSQL数据库概述数据库概述 目录目录什么是什么是NoSQLNoSQL1NoSQLNoSQL种类与特点种类与特点2CAPCAP定理定理3ACIDACID与与BASEBASE4小结小结102最终一致性技术基础最终一致性技术基础5数据复制与分片数据复制与分片6NoSQLNoSQL数据库与云计算数据库与云计算7NoSQLNoSQL数据库与物联网数据库与物联网8NoSQLNoSQL数据库与区块链数据库与区块链91.1 什么是什么是NoSQL3n研究不同特点大数据存储的数据库技术；研究不同特点大数据存储的数据库技术；nNoSQLNoSQL数据库是非关系型数据存
2、储的广义定数据库是非关系型数据存储的广义定义；义；n它不同于符合它不同于符合ACIDACID理论的关系型数据库，数理论的关系型数据库，数据存储不需要固定的表结构；据存储不需要固定的表结构；n通常也不存在连接操作；通常也不存在连接操作；nNoSQLNoSQL数据库不使用传统的关系数据库模型，数据库不使用传统的关系数据库模型，而是使用键值模型、列模型、文档模型、图而是使用键值模型、列模型、文档模型、图模型等方式存储数据。模型等方式存储数据。n数据库应用需求变化数据库应用需求变化n支撑支撑OLTPOLTP型应用：事务处理型应用：事务处理,RDB,RDB的强项的强项n支撑支撑OLAPOLAP型应用：多
3、维分析处理型应用：多维分析处理n新需求：支撑面向大数据的存储、处理与应用新需求：支撑面向大数据的存储、处理与应用n新挑战新挑战none-size does not fit alln高性能、低成本高性能、低成本n不同类型非结构化数据存储与管理不同类型非结构化数据存储与管理n计算机新技术助力计算机新技术助力NoSQLNoSQLn多核、大内存，集群等技术的普及多核、大内存，集群等技术的普及1.1 什么是什么是NoSQLNoSQLNoSQL诞生原因诞生原因 麻省理工麻省理工Michael Stonebraker现代主流数据库系统架构的现代主流数据库系统架构的奠基人，奠基人，20142014年获图灵奖。
4、年获图灵奖。n关系型数据库面临的问题关系型数据库面临的问题n扩展困难扩展困难：由于存在类似：由于存在类似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假设失效是必然发生的假设失效是必然发生的:需要具有高容错性。需要具有
7、高容错性。nNOSQLNOSQL实现都建立在硬盘、机器和网络都会经常性失效假设之上。实现都建立在硬盘、机器和网络都会经常性失效假设之上。n不能彻底阻止这些失效，需要让系统能够在即使非常极端的条件下也不能彻底阻止这些失效，需要让系统能够在即使非常极端的条件下也能应付这些失效。能应付这些失效。n对数据进行分区：对数据进行分区：需要高性能需要高性能n分布式存储，将读写操作的负载分布到了不同的机器上分布式存储，将读写操作的负载分布到了不同的机器上n提高数据存储与访问的并发性。提高数据存储与访问的并发性。n保存同一数据的多个副本：需要保存同一数据的多个副本：需要具有高可用性。具有高可用性。nNOSQLN
8、OSQL提供数据副本机制，副本个数往往可配置提供数据副本机制，副本个数往往可配置n查询支持查询支持n在这个方面，不同的实现有相当本质的区别。不同实现的一个共性在在这个方面，不同的实现有相当本质的区别。不同实现的一个共性在于哈希表中的于哈希表中的 key/value key/value 匹配。匹配。1.2 NoSQL分类与特点分类与特点8类型型Top 3代表代表特点特点图数据数据库（Graph DBMS）Neo4jMicrosoftAzureCosmosDB（Multi-model）OrientDB（Multi-model）图型数据的最佳存储。相比使用传统关系数据库性能更优，存储模式设计与使用更
9、加灵活、简单。文档文档数据数据库（Document Stores）MongoDBAmazonDynamoDB（Multi-model）CoucHBase文档存储一般用类似JSON（JavaScriptObjectNotation）的格式存储，存储的内容是文档型的嵌套结构。可以对某些字段建立索引，实现类似关系数据库的某些功能。键值数据数据库（KV KV DBMS）Redis（Multi-model）AmazonDynamoDB（Multi-model）MicrosoftAzureCosmosDB（Multi-model）可以通过Key快速查询到其Value。一般来说，存储不管Value的格式，照
10、单全收。列族存列族存储（Wide Column Stores）CassandraHBaseMicrosoftAzureCosmosDB（Multi-model）顾名思义，是按列存储数据的。最大的特点是方便存储结构化和半结构化数据，对某一列或者某几列的查询有非常大的性能优势。https:/db- 截止2019年11月排名如下表1.2 NoSQL种类与特点种类与特点9类型型Top 3代表代表特点特点时序序数据数据库（Time Series DBMS）InfluxDBKdb+Prometheus时间序列数据库用于支撑时间序列数据的优化存储，每个条目都有一个相关的时间戳。时间序列数据可以来自传感器、智
11、能电表等，或可以存储一个高频股票交易系统的股票价格波动情况。对象存象存储(Object oriented DBMS)InterSystemsCach（Multi-model）VersantObjectDBObjectStore通过类似面向对象语言的语法操作数据库，通过对象的方式存取数据。XML数据数据库MarkLogicOracleBerkeleyDBVirtuoso可以高效地存储XML数据，并支持XML的内部查询语法，如XQuery、Xpath等。原生类XMLDB有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对键可设置失效时间，丰富的配置管理功能可以精准地设定数对键可设置失效时间，丰富的配置管理功能可以精准地设定数据服务级别。据服务级别。1.
21、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)nVertica(Column-oriented)Vertica(Column-oriented)nAster Data(Relational)Aster Data(Relation
24、al)nGreenplum(Relational)Greenplum(Relational)1.3 CAP定理定理（2 2）关注一致性和分区容忍性的）关注一致性和分区容忍性的(CP)(CP)n这种系统将数据分布在多个网络分区的节点上，并保证这这种系统将数据分布在多个网络分区的节点上，并保证这些数据的一致性，但是对于可用性的支持方面有问题，比些数据的一致性，但是对于可用性的支持方面有问题，比如当集群出现问题的话，节点有可能因无法确保数据是一如当集群出现问题的话，节点有可能因无法确保数据是一致性的而拒绝提供服务，主要的致性的而拒绝提供服务，主要的CPCP系统有：系统有：nBigTable(Colu
25、mn-oriented)BigTable(Column-oriented)nHypertable(Column-oriented)Hypertable(Column-oriented)nHBase(Column-oriented)HBase(Column-oriented)nMongoDB(Document)MongoDB(Document)nTerrastore(Document)Terrastore(Document)nRedis(Key-value)Redis(Key-value)nScalaris(Key-value)Scalaris(Key-value)nMemcacheDB(Key
26、-value)MemcacheDB(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)nVoldemort(Key-value)Voldemor
27、t(Key-value)nTokyo Cabinet(Key-value)Tokyo Cabinet(Key-value)nKAI(Key-value)KAI(Key-value)nCassandra(Column-oriented)Cassandra(Column-oriented)nCouchDB(Document-oriented)CouchDB(Document-oriented)nSimpleDB(Document-oriented)SimpleDB(Document-oriented)nRiak(Document-oriented)Riak(Document-oriented)1.
28、3 CAP定理定理关系数据库关系数据库 VSVS NoSQL NoSQL 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与与BASE261.4 ACID与与BASEn基本可用性基本可用性：分布式系统在出现不可预知故：分布式系统在出现不可预知故障的时候，允许损失部分可用性。障的时候，允许损失部分可用性。n软状态软状态：允许系统中的数据存在中间状态，：允许系统中的数据存在中间状态，并认
31、为该中间状态的存在不会影响系统的整并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。本之间进行数据同步的过程存在延时。n最终一致性最终一致性：BASEBASE系统显著的特点是要保系统显著的特点是要保证在短时间内，即使有不同步的风险，也要证在短时间内，即使有不同步的风险，也要允许新数据能够被存储。所有的数据副本，允许新数据能够被存储。所有的数据副本，在经过一段时间的同步后，最终能够达到一在经过一段时间的同步后，最终能够达到一个一致的状态。个一致的状态。1.5 最终一致性技术基础最终一致性技术基础27
32、nNoSQLNoSQL分布式集群系统是由多个节点（指服分布式集群系统是由多个节点（指服务器、存储设备等）构成务器、存储设备等）构成n由于网络异常、服务器故障等原因，节点并由于网络异常、服务器故障等原因，节点并不总能保证正常工作，特别是在节点数量很不总能保证正常工作，特别是在节点数量很大的时候，出现异常状况在所难免。大的时候，出现异常状况在所难免。n为了保证系统的正常运行，分布式系统中对为了保证系统的正常运行，分布式系统中对于数据的存储采用多数据副本来保证高可用于数据的存储采用多数据副本来保证高可用性，这个过程对于用户来说是透明的。性，这个过程对于用户来说是透明的。n如何保障多副本数据的最终一致
33、性？如何保障多副本数据的最终一致性？1.5.1一致性问题一致性问题28n按照服务保障能力的不同，客户端访问一致性可以按照服务保障能力的不同，客户端访问一致性可以分为以下几个类型。分为以下几个类型。n严格一致性严格一致性：语义上相当于只存在一份数据。任何更新：语义上相当于只存在一份数据。任何更新看上去都是即时发生的。看上去都是即时发生的。n“读己之所写读己之所写”一致性一致性：客户端可立即看到自己所作的：客户端可立即看到自己所作的更新，且客户端可在不同请求之间切换服务器，但不能更新，且客户端可在不同请求之间切换服务器，但不能立即看到其他客户端所作的更新。立即看到其他客户端所作的更新。n会话一致性
34、会话一致性：对于客户端在同一会话作用域中发起的请：对于客户端在同一会话作用域中发起的请求，通常绑定到同一台服务器，提供求，通常绑定到同一台服务器，提供“读己之所写读己之所写”一一致性。致性。n单调读一致性单调读一致性：保证时间上的单调性，保证客户端在未：保证时间上的单调性，保证客户端在未来的请求中，只会读到比当前更新的数据。来的请求中，只会读到比当前更新的数据。n最终一致性最终一致性：这是最弱的一种保证。在更新的过程中，：这是最弱的一种保证。在更新的过程中，客户端可能看到不一致的视图。客户端可能看到不一致的视图。1.5.2 Quorum的的NWR策略策略29nQuorom Quorom 机制是
35、一种分布式系统中常用的，用来保证机制是一种分布式系统中常用的，用来保证数据冗余和最终一致性的投票算法，其主要数学思数据冗余和最终一致性的投票算法，其主要数学思想来源于鸽巢原理。想来源于鸽巢原理。nQuorumQuorum的的NWRNWR策略中策略中N N代表总的节点数量，代表总的节点数量，WW代表代表写的节点数量，写的节点数量，R R代表读的节点数量。代表读的节点数量。nQuoromQuorom机制中分布式系统中的每一份数据拷贝对象机制中分布式系统中的每一份数据拷贝对象都被赋予一票。每一个操作必须要获得最小的读票都被赋予一票。每一个操作必须要获得最小的读票数（数（VrVr）或者最小的写票数）或
36、者最小的写票数(Vw(Vw）才能读或者写。）才能读或者写。1.5.2 Quorum的的NWR策略策略30n如果一个系统有如果一个系统有V V票（意味着一个数据对象有票（意味着一个数据对象有V V份冗份冗余拷贝），那么这最小读写票数必须满足：余拷贝），那么这最小读写票数必须满足：（1 1）Vr+Vw VVr+Vw V （2 2）Vw V/2Vw V/2n第第1 1条规则保证了一个数据不会被同时读写。条规则保证了一个数据不会被同时读写。n第第2 2条规则保证了数据的串行化修改。条规则保证了数据的串行化修改。nQuorumQuorum的读写最小票数可以用来作为系统在读、写的读写最小票数可以用来作为系
37、统在读、写性能方面的一个可调节参数。写票数性能方面的一个可调节参数。写票数VwVw越大，则读越大，则读票数票数VrVr越小，这时候系统写的开销就大。反之，则越小，这时候系统写的开销就大。反之，则写的开销就小。写的开销就小。1.5.2 Quorum的的NWR策略策略31n读数据读数据：n假设共有假设共有N N个数据副本，其中个数据副本，其中K K个已经更新，个已经更新，N-KN-K个未更新，个未更新，那么任意读取那么任意读取 N-K+1N-K+1个副本数据的时候就必定至少有个副本数据的时候就必定至少有1 1个个是属于更新了的是属于更新了的K K个里面的，也就是个里面的，也就是 Quorum Qu
38、orum 的交集的交集n只需比较读取的只需比较读取的N-K+1N-K+1数据，并将其中版本最高的那个数数据，并将其中版本最高的那个数据返回给用户就可以得到最新更新的数据。据返回给用户就可以得到最新更新的数据。n写数据写数据：n只需要完成写只需要完成写K(K(大于大于N/2)N/2)个副本的更新后，就可以告诉客个副本的更新后，就可以告诉客户端操作完成，而不需要全部写入完成；户端操作完成，而不需要全部写入完成；n当然告诉用户完成操作后，系统内部还是会继续把剩余的当然告诉用户完成操作后，系统内部还是会继续把剩余的副本更新，这对于用户是透明的。副本更新，这对于用户是透明的。1.5.3 Paxos算法简
39、介算法简介32nPaxosPaxos算法算法是是Leslie LamportLeslie Lamport于于19901990年提出的，年提出的，类似于解决类似于解决拜占庭将军问题拜占庭将军问题，基于消息传递，基于消息传递解决分布式系统中的一致性问题。解决分布式系统中的一致性问题。n一个被一个被PaxosPaxos管理的系统实际上谈论的是值状管理的系统实际上谈论的是值状态和跟踪的问题。态和跟踪的问题。nCassandraCassandra、GoogleGoogle的分布式锁服务的分布式锁服务ChubbyChubby等等采用的都是采用的都是PaxosPaxos算法进行一致性管理。算法进行一致性管理
40、。nPaxosPaxos完成一次写操作需要两次交互过程，分完成一次写操作需要两次交互过程，分别是别是prepare/promiseprepare/promise和和propose/acceptpropose/accept。1.5.3 Paxos算法简介算法简介33nPaxosPaxos一致性算法执行过程一致性算法执行过程1.5.3 Paxos算法简介算法简介34nPaxosPaxos一致性算法执行过程一致性算法执行过程n第一次由提交者（第一次由提交者（LeaderLeader）向所有其他服务器发）向所有其他服务器发出出PreparePrepare消息请求准备，所有服务器中大多数如消息请求准备，
41、所有服务器中大多数如果回复诺言（果回复诺言（promisepromise）就表示准备好了，可以）就表示准备好了，可以接受写入；接受写入；n第二次提交者向所有服务器发出正式建议第二次提交者向所有服务器发出正式建议ProposePropose，所有服务器中大多数如果回复已经接，所有服务器中大多数如果回复已经接收（收（acceptaccept）就表示成功。）就表示成功。n这里大多数的含义一般指超过半数以上，即至这里大多数的含义一般指超过半数以上，即至少少N/2+1N/2+1个节点，个节点，N N为节点总数。为节点总数。1.5.3 Paxos算法简介算法简介35nPaxosPaxos一致性算法执行过程
42、一致性算法执行过程n接受的过程可能会发生失败，在回复了诺言消接受的过程可能会发生失败，在回复了诺言消息以后，在接受到息以后，在接受到AcceptAccept消息之前，如果有足够消息之前，如果有足够多的服务器正好在这个时间段失败，那么执行多的服务器正好在这个时间段失败，那么执行接受行为只能是少数服务器；接受行为只能是少数服务器；nPaxosPaxos算法不允许在没有达成共识情况下任何写算法不允许在没有达成共识情况下任何写操作发生，这种坏的情况在实践中经常通过操作发生，这种坏的情况在实践中经常通过重重复接受阶段复接受阶段来让大多数节点最终接受；来让大多数节点最终接受；nPaxosPaxos算法中会
43、维护一个全局唯一的序列号。序算法中会维护一个全局唯一的序列号。序列号是由建议流程产生，它定义了接受流程应列号是由建议流程产生，它定义了接受流程应该准备接受带有最新序列号的建议，序列号是该准备接受带有最新序列号的建议，序列号是算法的关键；算法的关键；1.5.4 Raft算法简介算法简介36nRaftRaft算法算法是由斯坦福大学是由斯坦福大学Diego OngaroDiego Ongaro博士在博士在20142014年提出的一种更易于理解的分布式架构年提出的一种更易于理解的分布式架构中日志一致性管理算法。中日志一致性管理算法。n相比于相比于PaxosPaxos，RaftRaft算法更容易理解，也
44、更容算法更容易理解，也更容易应用到实际的系统当中。易应用到实际的系统当中。RaftRaft算法是算法是ZookeeperZookeeper框架的核心算法，也是区块链中联框架的核心算法，也是区块链中联盟链采用比较多的共识算法。盟链采用比较多的共识算法。nRaftRaft算法中，分布式系统中的节点有三种角算法中，分布式系统中的节点有三种角色。色。n领导者、候选者、追随者领导者、候选者、追随者37nRaftRaft算法作用示意算法作用示意1.5.4 Raft算法简介算法简介38nRaftRaft算法三种节点角色作用算法三种节点角色作用n领导者（领导者（LeaderLeader）：只有一个，负责接收客
45、户端：只有一个，负责接收客户端的请求，将日志复制到其他节点并告知其他节的请求，将日志复制到其他节点并告知其他节点何时应用这些日志是安全的。点何时应用这些日志是安全的。n候选者（候选者（CandidateCandidate）：通常多个，用于选举：通常多个，用于选举LeaderLeader的一种角色。的一种角色。n追随者（追随者（FollowerFollower）：通常多个，负责响应来自：通常多个，负责响应来自LeaderLeader或者或者CandidateCandidate的请求。的请求。1.5.4 Raft算法简介算法简介39nRaftRaft算法思想算法思想n类似民主选举，领导者由民众投票
46、选举产生，集类似民主选举，领导者由民众投票选举产生，集群刚开始没有领导者，所有服务器节点都是追随群刚开始没有领导者，所有服务器节点都是追随者；者；n接下来进行选举，角色转换为候选者参与投票，接下来进行选举，角色转换为候选者参与投票，每台服务器只能投一票，得票超过半数以上的当每台服务器只能投一票，得票超过半数以上的当选为领导者，并设定这届领导者的任期（选为领导者，并设定这届领导者的任期（TermTerm），），从而选举结束；从而选举结束；n其他候选人转换为追随者，并无条件服从领导者其他候选人转换为追随者，并无条件服从领导者的领导。的领导。nRaftRaft把时间切割为任意长度的任期，每个任期都把
47、时间切割为任意长度的任期，每个任期都有一个任期号，采用连续的整数。有一个任期号，采用连续的整数。1.5.4 Raft算法简介算法简介40nRaftRaft算法思想三类角色状态转换如图所示算法思想三类角色状态转换如图所示1.5.4 Raft算法简介算法简介41nRaftRaft算法从时间角度看任期算法从时间角度看任期，如图所示，每次选举，如图所示，每次选举如果成功则由领导者来负责集群中的事务及状态管如果成功则由领导者来负责集群中的事务及状态管理，有时也可能出现选举失败，则需要重新选举直理，有时也可能出现选举失败，则需要重新选举直到选举成功，如图中的到选举成功，如图中的t3 t3情况。情况。1.5
48、.4 Raft算法简介算法简介42n基于基于LeaderLeader的方法，的方法，RaftRaft算法可分解成三个子问题算法可分解成三个子问题n领导者选举领导者选举(Leader Election)(Leader Election)：原来的领导者挂掉：原来的领导者挂掉后，必须选出一个新的领导者，候选者可以自己后，必须选出一个新的领导者，候选者可以自己选自己。选自己。n日志复制日志复制(Log Replication)(Log Replication)：领导者从客户端接收：领导者从客户端接收日志，并向日志，并向FollowerFollower们发出指令，比如进行日志复们发出指令，比如进行日志复
49、制。制。n安全性安全性(Safety)(Safety)：如果有任意的：如果有任意的ServerServer将日志项回放将日志项回放到状态机中了，那么其他的到状态机中了，那么其他的ServerServer只会回放相同的只会回放相同的日志项。日志项。1.5.4 Raft算法简介算法简介43n领导者选举领导者选举(Leader Election)(Leader Election)：要开始一次选举过程，要开始一次选举过程，Follower Follower 会给当前会给当前termterm加加1 1并且转换成并且转换成CandidateCandidate状态，并行地状态，并行地向集群中的其他服务器节点
50、发送请求投票的消息来给自己投向集群中的其他服务器节点发送请求投票的消息来给自己投票。候选人的状态维持直到以下任何一个条件发生。票。候选人的状态维持直到以下任何一个条件发生。n(1)(1)自己赢得这次选举自己赢得这次选举。给所有其它节点发送这个信息，。给所有其它节点发送这个信息，这样所有节点都会转成这样所有节点都会转成FollowerFollower。n(2)(2)其他的服务器成为领导者其他的服务器成为领导者。如果。如果LeaderLeader的的termterm大于或等大于或等于自身的于自身的termterm，则该，则该Candidate Candidate 会转成会转成FollowerFol