开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第四课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/15860
第四课（三）
内容介绍
一、CAP 定理
二、CAP 定理的起源
三、CAP 定理：鱼和熊掌不可兼得
四、CAP 定理：示例
五、CAP 定理：选择放弃
六、服务器一致性
七、一致性哈希
六、服务器一致性：
概念
N：节点个数 N＝5即有5个节点
W：更新数据时需要确认已经被更新的节点个数，比如写操作，写数等于3。
R：读数据时需要读取的节点个数
如果W+R>N，那么分布式系统就会提供强一致性的保证，即操作要求所有的读的数目和写操作写的数目，这两个数目加起来比 N 大，比如 N 是5，和是6或7，那么就保持强一致性，如果小于 N，就不能保持强一致性。读只读一个，写只写一个，那么在5个机器里随便找一个机器便可以，那么便无法保持一致性，他俩便无交集了。如果相加超过5，那么他俩一定有交集。一但有交集，写和读时就会保持强一致性。因为，读取数据节点和被写入的节点是有重叠的。
在一个 RDBMS 的复制模型中(Master/Slave)，假如N=2，W=2，R=1，写要把两台服务器都写，此时是一种强一致性，但是这样造成的问题就是可用性的减低，因为要想写操作成功，必须要等2个节点都完成以后才可以。一致性高，可用性会降低。强调一致性，一定会牺牲可用性，反之也一样。做系统设计时，相当于一个平衡高手，需要在这两个中间平衡起来，平衡的不好便会摔跤。
在分布式系统中，一般都要有容错性，因此一般 N 都大于3，此时根据 CAP 理论，一致性， 可用性和分区容错性最多只能满足两个，因此我们需要在一致性和分区容错性之间做一个平衡。
如果要高的一致性，那么就配置为 W=N， R=1，这个时候可用性就会大大降低。读只要读一个节点，写必须所有节点都写，就会保证写完内容都一样，如果有5个节点，只写1个，肯定不一致。写完后，再把这个节点传播到其他节点，就会延迟，就会不一致。
如果想要高的可用性，那么此时就需要放松一致性的要求，此时可以配置 W=1，这样使得写操作延迟最低。写只写一个，比如有3台机器，只在一台机器上写，所以一致性降低。
当存储系统保证最终一致性时，存储系统的配置--般是W+R<= N，此时读取和写入操作是不重叠的。
不一致窗口就依赖存储系统的异步实现方式，不一致窗口大小也就等于从更新开始到所有节点都异步更新完成之间的时间。
N，R，W的例子
(N，R，W)的值典型设置为(3，2，2)，有三台机器，读二写二，兼顾性能与可用性
W=1，R=N，对写操作要求高性能\高可用。
R=1,W=N,对读操作要求高性能\高可用，比如类似 cache之类业务。
W=Q, R=Q where Q=N/2 + 1适用一般应用，读写性能之间取得平衡。如N=3，W=2，R=2
Base 性质
Base 跟 ACID（酸的，刻薄的） 相对，Base 意思是 碱性的。
BASE(Basically Available 基本可用，Soft state 软状态，Eventually consistent 最终一致)是对 CAP 中的 C&A 的衍生。
在单机环境或集中环境，传统数据库强调数据的属性是 ACID
而在分布式环境中，数据的属性就是 BASE
BASE 是为了解决关系数据库强一致性引起的问题而引起的可用性降低而提出的解决方案。
BASE 模型不同于 ACID 模型，它通过牺牲高一致性，获得可用性和可靠性。
现在 NOSQL 运动丰富了拓展了 BASE思想，可按照具体情况定制特别方案，比如忽视一致性，获得高可用性等等，NOSQL 应该有下面两个流派。
1. key-value 存储，如 Amaze Dynamo 等，可根据 CAP 三原则灵活选择不同倾向的数据库产品。
2.领域模型+分布式缓存+存储，可根据 CAP 三原则结合自己项目定制灵活的分布式方案，难度高。
共同点:
都是关系数据库 SQL 以外的可选方案，逻辑随着数据分布，任何模型都可以自己持久化，将数据处理和数据存储分离，将读和写分离，存储可以是异步或同步，取决于对一致性的要求程度。
ACID vs. BASE
ACID 强调强一致性，BASE 强调弱一致性；ACID 事务要隔离，BASE 不要求隔离；ACID 关注如何提交，BASE 关注可用性；BASE 强调最佳效果和近似答案，不要求绝对准确，所以牺牲一致性；ACID 相对保守悲观，认为世界到处充满陷阱，每一步都谨小慎微，BASE 乐观积极进取；ACID 复杂，BASE 简单；ACID 更难演化，BASE 更容易演化。
七、一致性哈希
一致性哈希(Consistent Hash)是1997年由 MIT 提出的一种分布式哈希表(DHT)实现算法，设计目标是解决分布式缓存中的热点(Hotspot)问题。
一致性哈希作为分布式存储领域的一个重要算法，解决了以 P2P 为代表的存储环境中一个关键的问题——如何在动态的网络拓扑中对数据进行分发和选择路由。哈希还可以指加密指纹，比如通过256算法把任意数据变成256位长的二进制数据。这一段数据便是指纹，只要里面发生任何变化，重新算出来就跟原来不一样了，只要一改马上就能发现。
一致性哈希是一种哈希算法，简单地说在移除或者添加一个服务器时，此算法能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系，并尽可能满足单调性要求，从而使得分布式哈希(DHT)可以在 P2P 环境中得到应用。P2P 网络环境特点为，服务器处于动态变化中，可能随时会离开，一会儿又加入新的，此时原来放在服务器里的内容，找内容时要找服务器。
具体的说，在一致性哈希所构成的存储拓扑中， 每个存储节点仅需维护少量相邻节点的信息，并且在新/旧节点加入/退出系统时，仅有相关的少量节点参与到拓扑的维护中，这使得一致性哈希算法成为一个具有实用意义的 DHT(DistributedHash Table 分布式哈希表)算法。
在动态变化的 Cache 环境中，判定哈希算法好坏的4个性质：
平衡性(Balance)
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。大多数哈希算法都能够满足这一条件。
单调性（Monotonicity )
单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中，则哈希的结果应能够保证：原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。比如有三台机器 A、B、C，内容放到 A、B、C，现在增加 D，则原来的内容增加了新空间，原来的内容需要搬家，原来已有的不会从 A 搬到 B，B 搬到 C，单调性不折腾。
单调性（ Monotonicity )——续
简单哈希算法往往不能满足单调性的要求，如最简单的线性哈希：
×( ax + b ) mod ( N )
在上式中，N 表示全部缓冲的数目。不难看出，当缓冲大小发生变化时（从N1到N2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在 P2P 系统内，缓冲的变化等价 Peer 加入或退出系统，这一情况在 P2P 系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够避免这一情况的发生。如果简单地用 mon 的方法是完成不了的，因为服务器的数目有 N 台服务器，算出来的值一定是一到 N，此时如果用 mon 显然满足不了要求。比如原来是三台机器，现在变成四，重新一 mon，原来在 A 的可能会跑到 B 或 C 里。同样 B 里的内容可能跑到 C 里。
分散性(Spread)
在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
负载(Load)问题
负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
从表面上看，一致性哈希针对的是分布式缓冲的问题，但是如果将缓冲看作 P2P 系统中的 Peer，将映射的内容看作各种共享的资源(数据，文件，媒体流等)，就会发现两者实际上是在描述同一问题。
分布式缓存
图片
浏览器通过应用服务器查看内容时，有两种，一种从库里进，首次访问时从数据库里拿，拿完后放到缓存里，以后再去拿同样内容时就从缓存里拿。
一致性哈希：例
hash模余算法:
根据 hash(key)% N 的结果决定存储到哪个节点(key：数据的关键字键值，N：服务器个数)，此计算方法简单，数据的分散性也相当优秀。其缺点是当添加或移除服务器时，缓存重组的代价巨大。添加/删除服务器后(或者是某台服务器出现故障之后)，余数就会产生巨变，这样就无法保证获取时计算的服务器节点与保存时相同，从而影响缓存的命中率造成原有的缓存数据大规模失效。
一致性哈希方法
采用了一种新的方式来解决问题，处理服务器的选择不再仅仅依赖 key 的 hash 本身而是将服务实例(节点)的配置也进行 hash 运算。
首先，求出每个服务节点的 hash，并将其配置到一个0～“232-1的圆环区间(cont inuum).上。
其次，使用同样的方法求出所需要存储的 key 的 hash，也将其配置到这个圆环区间 (cont inuum) 上。
然后，从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务节点上。如果超过二的三十二次方减一仍然找不到服务节点，就会保存到第一个服务节点上。
不再依赖于服务器本身，哈希环配置原则为把关键字也哈希，哈希后配置到环上。
一致性哈希：示意图
哈希环像钟表一样，0／二的二十三次方是周期性的，0和二的三十二次方模出来的值是一样的。
现在图中有四个节点，哈希环实现起来很容易，哈希环有什么用？比如插入一个节点，比如节点5，这个节点原来的内容，关键值都需要重新分配，在二和四之间有几个分到五，插入的节点不受影响，如果四号节点坏了，把四号节点删掉，删掉后原来的内容会分配到三号节点，P2P 网络需用哈希环数据来做。
一致性哈希的改进：虚拟节点
一致性哈希具有随机性，当节点数量较少时节点在环_上分布不够均匀，对于节点可能存在的性能差异也没有考虑。有的节点和节点之间特别远，哈希环特别长。
为解决这个问题，以 Dynamo 为代表，提出了基于虚拟节点的改进算法，其核心思路是引入虚拟节点，每个虚拟节点都有一个对应的物理节点，而每个物理节点可以对应若干个虚拟节点。比如现在有5个物理节点，每个物理节点对应四个虚拟节点，对应十个便变成五十个虚拟节点。五十个虚拟节点分布在哈希环上，物理节点重新换的话，需按照哈希环临界的。
Dynamo 将圆环划分成了 M 等分，若加入物理节点为 N 个(N
当有物理节点离线时，由于该节点对应的虚拟节点均匀地分布在环上，其附近的节点将会均匀地分担这个节点的原有负载，当有新节点加入时，同理，其他节点的负担也将均匀转移到其上。
虚拟节点的 hash
算到 V1 存这儿，算到 V2 存这儿。
一致性哈希的改进：其他
此外，依据物理节点的实际性能为权值分配环上的虚拟节点数目给物理节点，可以解决存储节点性能差异的问题。服务器可能不同的机器性能不一样，有的机器性能高，存储量大，可以加一个能力系数，比如有100个虚拟节点，有5台机器，能力弱的可以给30个虚拟节点，可以反映物理的处理能力。
为解决数据迁移带来的效率降低问题，可以将新增节点完成的数据迁移分布在每一次的查询任务中去，相当于每-次查询都可以迁移一-小部分数据，此外，还可以在系统闲暇时间进行数据迁移，这样可以有效地提高效率。
优点：发生单点故障时负载会均衡分散到其他所有节点，程序实现也比较优雅。
一致性哈希的应用：路由算法
为了构建查询所需的路由，一致性哈希要求每个节点存储其_上行节点(ID 值大于自身的节点中最小的)和下行节点(ID 值小于自身的节点中最大的)的位置信息(IP 地址)。当节点需要查找内容时，就可以根据内容的键值决定向上行或下行节点发起查询请求。收到查询请求的节点如果发现自己拥有被请求的目标，可以直接向发起查询请求的节点返回确认;
如果发现不属于自身的范围，可以转发请求到自己的上行/下行节点。查一个东西，查到了就告诉查到了，
为了维护上述路由信息，在节点加入/退出系统时，相邻的节点必须及时更新路由信息。
这就要求节点不仅存储直接相连的下行节点位置信息，还要知道一定深度(n 跳) 的间接下行节点信息，并且动态地维护节点列表。
当节点退出系统时，它的上行节点将尝试直接连接到最近的下行节点，连接成功后，从新的下行节点获得下行节点列表并更新自身的节点列表。
同样的，当新的节点加入到系统中时，首先根据自身的 ID 找到下行节点并获得下行节点列表，然后要求上行节点修改其下行节点列表，这样就恢复了路由关系。
一致性哈希的应用：分布式哈希表（DHT）
分布式哈希表技术(Distributed Hash Table, DHT)是一种分
在不需要服务器的情况下，每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个 DHT 网络的寻址和存储。
DHT 具体步骤
将内容索引抽象为对
K是内容关键字的 Hash 摘要|
K = Hash(key)
V 是存放内容的实际位置，例如节点IP地址等
所有的对组成一- 张大的Hash表，因此该表存储了所有内容的信息
每个节点都随机生成一个标识(ID)，把 Hash 表分割成许多小块，按特定规则(即K和节点 ID 之间的映射关系)分布到网络中，节点按这个规则在应用层.上形成一个结构化的重叠网络(Overlay)
给定查询内容的 K 值，可以根据 K 和节点 ID 之间的映射关系在重叠网络上找到相应的 V 值，从而获得存储文件的节点IP地址
DHT 的具体体现，索引发布和内容定位
定位(Locating)
节点 ID 和其存放的对中的 K 存在着映射关系，因此可以由 K 获得存放该对的节点 ID
路由(Routing)
在重叠网上根据节点 ID 进行路由，将查询消息最终发送到目的节点。每个节点需要有到其邻近节点的路由信息，包括节点 ID、IP 等
网络拓扑
拓扑结构由节点 ID 和其存放的对中的 K 之间的映射关系决定
拓扑动态变化，需要处理节点加入/退出/失效的情况在重叠网上节点始终由节点 ID 标识，并且根据 ID 进行路由。
Paxos 算法
Leslie Lamport 最先提出的一种基于消息传递(MessagesPassing)的一致性算法， 用于解决分布式系统中的一致性问题。
分布式系统一致性问题一就是如何保证系统中初始状态相同的各个节点在执行相同的操作序列时，看到的指令序列是一致的，并且最终得到一致的结果
一个最简单的方案
在分布式系统中设置一个专门节点，在每次需要进行操作之前，系统的各个部分向它发出请求，告诉该节点接下来系统要做什么。该节点接受第一-个到达的请求内容作为接下来的操作，这样就能够保证系统只有一个唯一的操作序列。
Paxos 算法：背景
Paxos 算法是莱斯利.兰伯特(Leslie Lamport，就是 LaTeX 中的“La”，现在在微软研究院)于1990年提出的一种基于消息传递的致性算法。由于该算法难以理解，起初并没有引起人们的重视。Lamport 在八年后重新发表到 TOCS 上，即便如此 paxos 算法还是没有得到重视。
2001年 Lamport 用可读性比较强的叙述性语言给出算法描述，可见 Lamport 对 paxos 算法情有独钟。
近几年 Paxos 算法的普遍使用证明它在分布式一致性算法中的重要地位。2006年 Google 的三篇论文初现“云”的端倪，其中的局 chubby 锁服务使用 paxos 作为 chubby cell 中的一致性算法，Paxos 的人气从此路狂飙。
Paxos 算法：取名2021-11-2
Paxos 算法是莱斯利兰伯特(Leslie Lamport,就是LaTeX中的“La”，现在在微软研究院)于1990年提出的一种基于消息传递的一致性算法。
由于该算法难以理解，起初并没有引起人们的重视。
