`

【转】Merkle Tree算法详解

 
阅读更多

Merkle Tree 是Dynamo中用来同步数据一致性的算法,Merkle Tree是基于数据HASH构建的一个树。它具有以下几个特点:

1、数据结构是一个树,可以是二叉树,也可以是多叉树(本BLOG以二叉树来分析)

2、Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。

3、Merke Tree非叶子节点value是其所有子节点value的HASH值。

为了更好的理解,我们假设有A和B两台机器,A需要与B相同目录下有8个文件,文件分别是f1 f2 f3 ....f8。这个时候我们就可以通过Merkle Tree来进行快速比较。假设我们在文件创建的时候每个机器都构建了一个Merkle Tree。具体如下图:

上图可得知,叶子节点node7的value = hash(f1),是f1文件的HASH;而其父亲节点node3的value = hash(v7, v8),也就是其子节点node7 node8的值得HASH。就是这样表示一个层级运算关系。root节点的value其实是所有叶子节点的value的唯一特征。

假如A上的文件5与B上的不一样。我们怎么通过两个机器的merkle treee信息找到不相同的文件? 这个比较检索过程如下:

1、首先比较v0是否相同,如果不同,检索其孩子node1和node2.

2、v1 相同,v2不同。检索node2的孩子node5 node6;

3、v5不同,v6相同,检索比较node5的孩子node 11 和node 12

4、v11不同,v12相同。node 11为叶子节点,获取其目录信息。

以上过程的理论复杂度是Log(N)。实际过程是大于这个复杂度的,因为不同value的节点需要每个子节点进行比较。过程描述图如下:

从上图可以得知真个过程可以很快的找到对应的不相同的文件。

如果A机器的目录下增加了一个文件f9。整个merkle tree就会变成这样的:

其中红色字体是需要进行运算的步骤,整个过程是从叶子节点发起的,直接回溯到root节点为止。

假如目录下的f1被删除。整树的运算变化图如下:

红色字体是需要进行的运算。

从上可以得知,merkle tree在大数据集合校验可以提高校验的效率的。从Dynamo论文中可以看出,大量使用merkle tree来同步分布式节点的文件和写操作,尤其是在服务节点异常后的情况,具体细节可以参看Dynamo论文中的描述。

 

转自:http://www.tuicool.com/articles/B7fM7j

分享到:
评论

相关推荐

    merkletree.rar

    java 实现 merkle tree while (true) { Event event = receiveEvent(); String hash = computeHash(event); // ...... sendToDownstreamQueue(hash, event);... MerkleTree mtree = new MerkleTree

    1_merkle-tree-master.rar

    merkle tree merkle tree merkle tree merkle tree merkle tree merkle tree merkle tree merkle tree merkle tree

    merkle-tree:Kotlin中的Merkle Tree和Merkle证明实现

    Kotlin中的Merkle Tree和Merkle证明实现MerkleTree是使用Kotlin kotlin-platform-common插件在Kotlin中实现的,该插件可将代码编译为JavaScript。 实现的方法: MerkleTree (input : List , hash : ( ByteArray ) ->...

    c++实现merkle_tree

    c++代码实现merkle_tree树..............

    基于改进Merkle-Tree认证方法的可验证多关键词搜索方案.docx

    2. 在认证阶段,利用改进的Merkle-Tree认证方法构造搜索方案的验证及动态更新算法,实现高效认证和动态更新;与经典的MHT相比,计算成本从O(n)降低到O(log n)。 本文还对所提方案的正确性、安全性和性能进行了详细...

    Merkle Tree构造及存在性证明,QT实现UI

    采用qt编写,适用于区块链初学者学习参考

    开源项目-keybase-go-merkle-tree.zip

    《深入解析开源项目 Keybase Go-Merkle-Tree》 在信息技术领域,开源项目一直扮演着推动创新和技术进步的重要角色。Keybase 是一个知名的开源安全平台,它提供了一种安全的方式来管理和验证数字身份。其中,`...

    solidity-mt-vs-mmr:比较Merkle Tree和Merkle Mountain Range树木气体使用量的Solidity示例

    团结默克尔树vs默克尔山脉树 比较Merkle Tree和树的气体使用量的Solidity示例。 建造 npm run build 测试 npm test 输出: ... ✓ MerkleTree (2279ms) append gas used: 0 161462 append gas use

    merkle, 实现Merkle树算法的node.js 模块.zip

    merkle, 实现Merkle树算法的node.js 模块 使用 sha512,sha256,ripemd160,漩涡,sha1,md5或者无算法构建Merkle树。用法构建Merkle树var merkle = require('merkle');var abcde

    Merkle tree

    merkle tree是一种区块链的基础数据结构,本文是整理的网上资料

    timber:从以太坊日志构建Merkle Tree数据库

    根据以太坊日志构建Merkle Tree数据库。 发起人: 启动配置 docker-compose.<...>.yml选项 CONTRACT_ORIGIN default remote mongodb compile HASH_TYPE 配置 contracts treeId TREE_HEIGHT 原料药 ...

    PyPI 官网下载 | merkle-tree-stream-0.0.1a4.tar.gz

    标题中的“PyPI 官网下载 | merkle-tree-stream-0.0.1a4.tar.gz”表明这是一个从Python Package Index(PyPI)官方下载的软件包,名为“merkle-tree-stream”,版本号为0.0.1a4,其打包格式是tar.gz。PyPI是Python...

    MerkleTree:使用c ++二进制Merkle树

    制作简单的MerkleTree 例如)string item =“ Hello”; string * arr =新字符串; arr = MakeTree(item); PrintAll(arr); 结果)您好-> 30efdfb52ff67f80dab7cb89dcfe0eec8412966cfe58324993674b4616d6bd11-> ...

    merkle_tree:纯Elixir中的Merkle Tree实现

    **Merkle Tree**,又称为哈希树或默克尔树,是一种数据结构,尤其在区块链、分布式存储和网络安全领域中广泛应用。它通过将数据的哈希值组织成树形结构,使得数据的完整性检查变得高效且可靠。Elixir 是一种基于 ...

    MerkleTree.dev:MerkleTree.dev网站

    MerkleTree.dev 网站

    merkletreejs::seedling:构造Merkle树并在JavaScript中验证证明

    MerkleTree.js 构造并使用JavaScript验证证明。 内容 安装 从 : npm install merkletreejs CDN 在 CDN上可用: < script src =" https://cdn.jsdelivr.net/npm/merkletreejs@latest/merkletree.js " > &...

    PHP中的Merkle树的实现-PHP开发

    将以下内容放入您的package.json中:{“ require”:{“ pleonasm / merkle-tree”:“ *”}}然后运行composer install。 固定大小树的用法散列树的用法要求用户提供一个散列函数,每个节点都将使用该函数进行散列。...

    前端开源库-merkle-tree-stream.zip

    "前端开源库-merkle-tree-stream.zip" 提供了一个用于前端开发的开源库,专注于处理Merkle Tree和Stream数据结构。这个压缩包可能包含了实现这一功能的源代码、文档和示例。 **Merkle Tree** 是一种哈希树数据结构...

    merkle:Go中的Merkle Tree实现

    默克尔 通过自己的作品, ,用法package mainimport ("crypto/sha256""log""os""github.com/wilfreddenton/merkle")func main() {// create a hash function// it's ok to resuse this in merkle calls because it ...

    python-merkle-tree

    python-merkle-tree

Global site tag (gtag.js) - Google Analytics