ROWA协议是强加单副本一致性的协议，它把一个逻辑读变成对任意一个副本的读操作，把一个逻辑写变成对所有副本的写操作，从而让所有副本有同一个值。ROWA协议简单优雅，但有一个致命缺陷：只要有一个副本不能用，更新事务就不能终止。实际上已经提出了这个协议的不少变种，有一个协议称为可用副本协议。因此，协调者在提交前需进行验证。ROWA-A协议比简单ROWA协议更能抗故障，包括网络分割。另一类严格副本控制协议是基于选举的。......
2023-10-28
分布式数据库技术：树状结构与Kademlia协议
【摘要】：如果启动中的节点还不是网络的一部分，则会计算一个尚未指定给其他节点的随机ID编号。最高层的子树由整棵树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整棵树。Kademlia协议确保每个节点知道其各子树的至少一个节点，只要这些子树非空。Kademlia为节点和键使用160比特的ID。例如，令x=010101，y=110001，则这两个节点的距离为100100（二进制），即十进制为32+4=36。
Kademlia是由Petar Maymounkov与David Mazières所设计的P2P覆盖网络传输协议，用以构建分布式的P2P计算机网络。它是一个基于“异或”运算的P2P信息系统，制定了网络的结构及规范了节点间通信和交换资讯的方式。
Kademlia节点间的通信使用UDP协议。Kademlia节点利用DHT储存资料索引。
想要加入网络的节点，需要先经过启动过程。在这个阶段，该节点需要知道另一个已经在Kademlia网络中注册的节点的IP地址（通过另一个使用者或储存的清单获取）。如果启动中的节点还不是网络的一部分，则会计算一个尚未指定给其他节点的随机ID（160比特）编号。这个ID是由节点的对外IP地址跟端口号通过SHA-1之后得到的。这个ID会一直用到离开网络为止。
简单来说，拥有要分享的文件网络节点，会先处理文件的内容，并从内容中计算出一组数字（哈希值），这组数字将会在文件分享网络中辨识这个文件。哈希值与节点ID的长度相同。接着会查找几个ID与哈希值相近且节点内储存着自己IP地址的节点。搜索的用户会使用Kademlia来搜索网络上节点的ID离自己最近的节点来获取文件的哈希值，再获取该节点上的路由清单。当节点联入和联出时，这份存储在网络上的路由清单也将保持不变。因为内嵌的冗余存储算法、路由清单将复制在多个节点上。
在Kademlia网络中，所有节点都被当成一棵二叉树的叶子，并且每个节点的位置都由其ID值的最短前缀唯一确定。
对于任意一个节点，都可以把这棵二叉树分解为一系列连续的、不包含自己的子树。最高层的子树由整棵树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整棵树。(www.chuimin.cn)
Kademlia协议确保每个节点知道其各子树的至少一个节点，只要这些子树非空。在这个前提下，每个节点都可以通过ID值来找到任意一个节点。这个路由的过程是通过所谓的XOR（异或）距离得到的。
Kademlia为节点和键使用160比特的ID。节点上存放键/值对。Kademlia网络中，每个节点都有一个160比特的ID值作为标识符，key也是一个160比特的标识符，每个加入Kademlia网络的计算机都会在160比特的key空间分配一个节点ID（node ID）值（可以认为ID是随机产生的），〈key，value〉对的数据就存放在ID值“最”接近key值的节点上。
判断两个节点x、y的距离远近是基于数学上的异或的二进制运算，d（x，y）=x XOR y，即对应位相同时结果为0，不同时结果为1。例如，令x=010101，y=110001，则
这两个节点的距离为100100（二进制），即十进制为32+4=36。
显然，（二进制）高位上数值的差异对结果的影响更大。
有关分布式数据库技术的文章
- 详细阅读
-
两阶段提交协议-分布式数据库技术详细阅读
下面讨论一个典型的提交协议，即两阶段提交协议。这种模式用到分布式事务管理就是两阶段提交协议。参与方接收到prepare消息后，就会检查自己能否提交。图10.132PC协议时协调者和参与者的状态转换图由图10.13可知：第一，2PC协议允许参与者单边夭折一个事务，直到它决定加入肯定选择前，它都是自由的。图10.14集中式2PC协议的通信结构实现时，2PC协议可以使用许多种不同的通信方式。图10.15线形2PC协议的通信结构协调者发送″prepare″消息给参与者2。......
2023-10-28
-
协议转换：连接不同协议网络的DTE级结构详细阅读
协议转换用来连接具有不同协议的网络，是网络对网络的DTE级结构。图8-11用IP互联LAN图8-12用标准协议转换器互联局域网对于网间通信，如A站至C站，则首先建立A站到协议转换器1的连接；然后协议转换器1使用转送层协议、IP和协议转换器2建立一个可靠的连接；最后协议转换器2和C站建立一个局域网的连接。......
2023-06-27
-
分布式数据库技术-基于选举的协议实现详细阅读
基于法定人数选举法可以作为一个副本控制方法，也可作为提交方法在网络分割时保证事务的原子性。事务提交前，必须获得提交法定选举人数Vc的通过。后两条规则说明选举的两条规则。在协调者从PRECOMMIT状态移到COMMIT状态和发送″global-commit″命令时，协调者必须获得提交选举人数参与者的同意，这是为了满足规则。图10.193PC协议在选举人方案中的状态转换基于选举人提交算法，有两点是很重要的。......
2023-10-28
-
分布式数据库技术：确保可靠性的协议详细阅读
分布式数据库系统的可靠性技术主要由协议构成，包括提交、终止和恢复协议。终止协议是分布式数据库系统中独有的。如果故障是网络分割，终止协议则会采取必要的措施去终止其他分割片上执行的仍然在活跃的事务。我们也希望分布式恢复协议是独立的。这样协议的存在可以大大减少恢复期间的消息交换。......
2023-10-28
-
三阶段提交协议在分布式数据库技术中的应用详细阅读
三阶段提交协议是为无阻塞协议而设计的。因此有必要对2PC协议进行修改。因为从INITIAL状态到COMMIT状态间有三个状态转换，所以我们称为三阶段提交协议。图10.173PC协议的状态转换图1.终止协议下面分析3PC协议每个状态在超时时的情况。协调者单边决定夭折该事务。因此它将abort记录写入日志，并发送″global-abort″消息给所有已经选择提交事务的参与者。3PC协议如图10.18所示。参与者可能处于INITIAL、READY、ABORT、PRECOMMIT状态。因此协调者将全局提交该事务，发送″global-commit″消息。......
2023-10-28
-
懒副本协议在分布式数据库技术中的应用详细阅读
懒副本协议也是一种变异，它并不试图在更新数据项的事务上下文中涉及的数据项的所有副本上实施写操作，而是将更新实施在一个或几个副本上，随后将改变传递给其他副本。拥有关系参数用于定义更新副本拷贝的许可。基于这四个参数，可以将懒副本协议分为两类。第一类由懒副本协议方法构成，所有副本都是可更新的。这种情况下，副本上存在群组关系。为这种模式实现的公共传播策略是延迟立即。刷新期间所有接收到的刷新事务都要执行。......
2023-10-28
-
分布式数据库技术：日志记录和logwrite详细阅读
大家熟知的航海记录和飞机的黑匣子记录等都是日志。这里，日志记录应当包含以下几方面。当然，事务在启动、提交或夭折时，需要往日志里写入begin-transaction、commit或abort记录。数据库更新的写操作和相应的日志写操作是两个不同的操作，因此，有可能会在这两个操作执行期间发生故障。为了避免出现这种现象，我们要求先写日志记录再更新数据库，称为log write-ahead协议。该协议有两个基本规则。......
2023-10-28
相关推荐