云存储方案中,产生了2大流派:元数据和sharding模型。sharding模型中,一致性哈希最为流行。一致性hash本身很难直接用作实际使用,进而产生了很多衍生方案,其中包括著名的“Dynamo”.这里的一致性hash方案是指代基于一致性hash的设计。
元数据方案是对象级别的key->pos映射。也就是一个会无休止的增长的”map”,每多一个对象,就会多一条元数据,通常会将元数据保存在一组数据库中,方便检索和查询。元数据的核心是元数据存储部分,其设计的好坏,关系到系统整体的特性。
标准的一致性hash模型,是对hash进行hash算法,然后投射到一个环形的数值空间上,与此同时,对节点(存储服务器)进行编码。然后也做hash运算,并投射到hash环上。理论上,只要hash算法合适,节点可以均匀的分布在hash环上。节点根据自身在hash换上的位置,占据一个hash值区间。比如从本节点到下一节点间的区间,所有落入这个区间的key。都会保存在该节点上。
在这个模型中。key到数据存储的逻辑位置的映射不通过存储,而是通过算法直接得到,但是逻辑位置(hash环上的位置)到物理位置(节点)的转换无法直接得到。标准的做法是任选一个节点,然后顺序寻找目标节点,或者采用二分法在节点之间跳转查找。这种查找方式在实际的存储系统中是服务忍受的。所以采用的存储系统往往是一个混合模型:系统维护一个hash区间->节点的映射表。这个映射的本质也是一种元数据,不过它是大粒度的元数据,更新一个路由表。由于粒度大,变化少,用文本文件既可以存储。这个映射表也需要多分存储,通常是放在入口服务器上,也可以分散到所有的存储节点上,关键是保持一致性。
一致性hash模型解决了hash表改变大小时,需要重新计算,并且迁移所有数据的问题,只需迁移被新加节点占据的hash区间所包含的数据。但是随着新节点的加入,数据量的分布会变的不均匀,为了解决这个问题。包括dynamo在内的诸多模型,都采用了虚拟节点的方案:将一个节点分成若干虚拟节点。当节点加入系统时,把虚拟节点分散到hash环上。如此可以更加均匀的添加一个节点。