分布式系统核心问题-数据分片的介绍.docx

分布式系统核心问题-数据分片的介绍  所谓分布式系统,就是利用多个独立的计算机来解决单个节点(计算机)无法处理的存储、计算问题,这是非常典型的分而治之的思想。每个节点只负责原问题(即整个系统需要完成的任务)的一个子集,那么原问题如何拆分到多个节点?在分布式存储系统中,任务的拆分即数据分片。何为数据分片(segment,fragment,shard,partition),就是按照一定的规则,将数据集划分成相互独立、正交的数据子集,然后将数据子集分布到不同的节点上。注意,这里提到,数据分片需要按照一定的规则,不同的分布式应用有不同的规则,但都遵循同样的原则:按照最主要、最频繁使用的访问方式来分片。本文主要介绍区块链分布式系统中的分片相关问题,包括三种分布方式:hash、一致性hash、rangebased,以及各自的优缺点。三种数据分片方式首先介绍三种分片方式:hash方式,一致性hash(consistenthash),按照数据范围(rangebased)。对于任何方式,都需要思考以下几个问题:具体如何划分原始数据集?当原问题的规模变大的时候,能否通过增加节点来动态适应?当某个节点故障的时候,能否将该节点上的任务均衡的分摊到其他节点?对于可修改的数据(比如数据库数据),如果某节点数据量变大,能否以及如何将部分数据迁移到其他负载较小的节点,及达到动态均衡的效果?元数据的管理(即数据与物理节点的对应关系)规模?元数据更新的频率以及复杂度? 为了后面分析不同的数据分片方式,假设有三个物理节点,编号为N0,N1,N2;有以下几条记录: R0:{id:95,name:'aa',tag:'older'} R1:{id:302,name:'bb',} R2:{id:759,name:'aa',} R3:{id:607,name:'dd',age:18} R4:{id:904,name:'ff',} R5:{id:246,name:'gg',} R6:{id:148,name:'ff',} R7:{id:533,name:'kk',}hash方式: 哈希表(散列表)是最为常见的数据结构,根据记录(或者对象)的关键值将记录映射到表中的一个槽(slot),便于快速访问。绝大多数编程语言都有对hash表的支持,如python中的dict,C++中的map,Java中的Hashtable,Lua中的table等等。在哈希表中,最为简单的散列函数是 modN(N为表的大小)。即首先将关键值计算出hash值(这里是一个整型),通过对N取余,余数即在表中的位置。数据分片的hash方式也是这个思想,即按照数据的某一特征(key)来计算哈希值,并将哈希值与系统中的节点建立映射关系,从而将哈希值不同的数据分布到不同的节点上。我们选择id作为数据分片的key,那么各个节点负责的数据如下: 由此可以看到,按照hash方式做数据分片,映射关系非常简单;需要管理的元数据也非常之少,只需要记录节点的数目以及hash方式就行了。但hash方式的缺点也非常明显:当加入或者删除一个节点的时候,大量的数据需要移动。比如在这里增加一个节点N3,因此hash方式变为了mod4,数据的迁移如下: 在这种方式下,是不满足单调性(Monotonicity)的:如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的