现在的位置: 首页 > 综合 > 正文

分布式系统的数据结构

2013年10月02日 ⁄ 综合 ⁄ 共 1837字 ⁄ 字号 评论关闭

本文链接地址: http://www.nosqlnotes.net/archives/134

常用的数据结构包括:数组,队列,堆栈,链表,树(平衡二叉树,B树,Trie树,堆),哈希表,图,后缀数组,等等。其中,堆,图结构,Trie树及后缀数组解决特定问题,其它数据结构解决通用的查找,新增,更新,删除操作。

查找,更新和删除操作一般是O(1),O(logN)或者O(N),通用的数据结果大致可分为如下三种:

1, 极端型;某些操作的算法复杂度为O(1),另外一些算法复杂度为O(N),比如有序链表查找复杂度为O(N),更新和删除为O(1);

2, 平衡型:主要操作的复杂度为O(logN),比如平衡二叉树及各种变种,B树的查找,更新和删除操作的复杂度都为O(logN);

3, 取巧型:主要指哈希表,最差情况下的算法复杂度虽然很高,但是只要hash函数计算hash值比较随机,插入、更新和删除操作都可以在常数时间内完成,当然,有所得必有所失,哈希数据结构牺牲的是范围查询功能;

 

虽然数
据结构很多,然后当数据量变大时,比如达到百万级别或者千万级别时,工程实践中常见的数据结构一般有两种:Hash表与平衡树,平衡树主要使用B树,这时
因为B树同时适应磁盘和内存。Hash数据结构实现简单,高效,可以高效地执行根据主键的插入、删除以及查找操作,当然,相比B树,Hash数据结构也有
一些弊端,比如不支持范围查询,不支持对整个数据数据执行瞬时的快照操作。分布式存储系统从本质上就是实现分布式Hash表或者分布式B+树。

普通的
Key-Value系统可以认为是一个分布式Hash表。Hash算法有两种,模N(N为机器数)Hash或者一致性Hash。其中,模N哈希的主要问题
在于机器上下线时机器数变化导致所有的数据都需要重新分布,而一致性Hash用来解决这个问题。先将数据通过Hash算法分成若干个桶,每台工作机服务这
些桶中的数据。由于采用Hash算法数据分布天然比较均匀,不需要考虑多个桶之间的数据动态调整,大大降低了系统设计的复杂度。假如采用一致性Hash分
桶,每个桶内使用Log-Structured Hash Table
存储数据,系统的数据结构如下:

1, Hash空间组织成一个环,环上相邻节点包含的数据构成一个桶;比如Hash空间为A, B, C,那么有(A, B], (B, C], 以及(C, A]三个桶;

2, 每个桶内的数据结构为Log-Structured Hash Table;当然,可根据需要修改每个桶的单机数据结构;

3, 桶是负载均衡和任务调度的基本单元;

4, 每个桶存放3个副本;

类似
Bigtable这种同时支持随机读取和顺序扫描的系统实现了分布式B+树数据结构。B+树按照顺序将数据划分为一个一个的桶(对应Bigtable的子
表),顺序划分可能分布不均匀,需要动态调整,这就是为什么Bigtable这样的系统往往有复杂的子表分裂和合并操作。Bigtable采用两级的B+
树结构组织,每个子表相当于B+树的一个叶子节点。数据结构如下:

1, 每个表按照主键(row key)组成一个B+树,主键是binary string;

2, 一个叶子节点包含表的一个前开后闭的主键范围(prev_end_key, end_key];

3, 每个叶子节点内部按照更小的主键范围划分为多个块(block)并内建块索引(block index);

4, 每个块的大小通常在8KB~64KB之间并内建行索引;

5, 数据压缩以块为单位,压缩算法由用户指定;

6, 叶子节点可能合并或者分裂;

7, 叶子节点是负载均衡和任务调度的基本单元;

8, 叶子节点存放3个副本;

总之,
大多数分布式存储系统要么实现一个分布式Hash表,要么实现分布式B+树,对应的存储引擎分别为前面博文中提到的随机读取存储引擎和Merge-
dump存储引擎。分布式Hash存储系统由于只支持随机读取,一般用选择相对较好的磁盘,分布式B+树存储系统同时支持随机读取和顺序扫描,当用来支持
使用模式主要为顺序扫描的应用时,可以选择相对较差的磁盘,比如SATA盘。

另外,
我们都知道,关系型数据库系统的存储引擎基本都是一颗B树结构,然而在NOSQL系统中存储引擎可能是Log-Structured Hash
Table或者Merge-dump存储引擎,很重要的一个原因是NOSQL系统的存储引擎只需要存储分布式Hash表的一个桶或者分布式B+树的一个叶
子,而每个桶或者每个叶子服务的数据量往往也只有百MB级别。

抱歉!评论已关闭.