从HashMap的rehash到分布式KV数据库

2020-05-12 00:00:00 数据 节点 是一个 方案 扩容
作者 | imgaara
微信公众号 | 神夜月光
题图 | 新买两个键盘,有一个可以给娃当玩具拍拍,加一起我就有5把类似这样的键盘了
连接 | 从HashMap的rehash到分布式KV数据库


有一天,某个群里的Google大神提出一个问题:


来讨论一个问题,如何设计一个可以像STL std::vector 一样自动扩容的hashtable?如何做到在扩容的时候操作速度也不会明显变慢?


我们各种就讨论起来了。对于这个问题我还是略熟悉的,张口就说了Redis的方案。当然其他同学也各自提出了自己的想法。然后我突然意识到这个是一个很好的可扩展议题,所以就写成这一篇,供大家思考和讨论。


谈论的是HashMap(hashtable),所以基本上增删改查的时间效率都应该是O(1)。而TreeMap暂时不在讨论的范围中,因为树形结构天生就是易于做添加,所以没有rehash这样的问题存在。


另外一个是,我们先考虑它只是一个普通的数据结构,并不是一个小运行系统。也就是说先不考虑有多线程支撑,也暂时不包含内部的背景线程的情况,先从简单的结构搞起。


内存中的HashMap一般都是连续内存。

一般扩容的方法都是地址空间加倍,然后在rehash的时候拷贝数据。

这个在小内存中是没有太大问题的。但是在大内存的时候,rehash中重新拷贝数据地址的成本还是很高的。当占用的内存(比如64G以上)的时候,rehash的停顿时间是完全无法忽略的。而这一时间的停顿可能造成服务的短时间不可用,更严重的会造成整个系统的雪崩。


那么我们应该如何来做呢?其实多想了像,rehash可以认为在单机上rehash,可以认为是在local system 上rehash,也可以认为在一个分布式环境下rehash。

那么都有些什么方法呢?仔细整理了一下记忆,其实还有不少可以说的。


渐进式rehash


这个是Redis使用的方案。

顾名思义,rehash的过程不是一次做完,而是慢慢做。这个过程的驱动源是各种增删改查的请求,每来一次请求,则rehash一个已经存在的KV。


h[0] 为原hash表,当h[0]在装载数据到一定程度的时候触发扩容和rehash过程。


有人说会问,如果没有请求了怎么办?

  • 可以设计一个定时触发源。这个定时触发源发送一个NO_OP_REHASH的请求到你的HashMap上,HashMap提供maybeRehash()的方法,系统接收到NO_OP_REHASH的请求类型时,则触发一次rehash。


还有人会问,如果请求太快了,还没有rehash完就又要扩容了怎么办?

这是一个trade-off的问题,个人认为没有完美的方案:

  • 加速rehash过程:一次可以rehash多个数据,一次bulk的大小可以通过配置定义,也可以通过当前的系统性能动态调整。
  • STW(Stop The World):可以直接进入等待状态,让rehash过程走完再做下面的事情。
  • 如果是还有比较充足的空间:可以生成h[2], h[3]等,rehash的过程我认为可以类似。但是也是要有限制,这一招只能用来对付一时的快速增长。并且也要设置一个上限,超过上限,依然要STW。

前缀匹配分区


这是群里另外一个百度的大神的想法,主要还是分治思想。我沿着思路继续想了想,觉得也能做。


前面说的都是一整块内存作为hash表。整块的数据是比较大,rehash的重定位会比较慢。那么如果我的hash表不是连续的,是分层的呢?


一般设计为两层。层根据前缀匹配找到对应的SubTable。

然后再到SubTable里面进行hash查找。

以下是一个示意图:


首先认为key是均匀分布的。如果不是均匀分布,请考虑添加一个SaltPrefix到你的key里面,再来存储到HashMap里面来。


每个前缀开辟新的SubTable,可以定死前缀所占Bit的长度。

但是每个前缀后面的table可以从比较小的size生长起来。每个SubTable大小可以单独变化。每个SubTable可以单独生长。


由于key已经是均分分布了,则不会有特殊的情况导致某些table特别大。所以每个SubTable都是比较小的,可以通过一次处理把一个SubTable下所有的key全部rehash一遍,并且这样的耗时不会太长。


如果某个SubTable在比较大的情况下,则需要退化到单个大的Table处理的情况了。但是从整体上来看,总体rehash的停顿时间是比较小的。


一种节省move的操作方法


参考美团的这篇文章:tech.meituan.com/java_h

一般,每个SubTable在扩容的时候,需要重新计算每个Key的slot index。

如果每次扩容时2倍扩容的时候(table的size始终得是2的次方),可以取个巧使得rehash的过程变得稍微快一点:

  • 同样是取模,但是需要修改为后缀计算,而不是前缀
  • 对每个key,计算SurfixBit的前一位
  • 如果是0,则数据的index不变
  • 如果是1,则数据的index=之前的index + 原table的size
  • 这样所有的数据就会在新的table中分散开来。而且slot的计算是准确的。
  • 要正确计算bit,就需要正确的计算BitMask
  • 01的分布,如果数据的hash做得好,也是可以让数据均匀分布到新的SubTable上的,这样可以降低冲突概率

多阶hash列表


这个方法是我在腾讯的时候用到过的。在腾讯,是大量使用这种表,解决高并发的访问问题。如果不出意外的话,我认为直到现今,这个方法还大量在使用中。并且一些Java程序在DirectMemory使用的基础下,在使用这样的结构(好处读者可以思考以下)


hash需要解决冲突的问题。当发生冲突,一般有Open Link法(俗称开链),Open RBTree法(我叫:开树法,开链的变种),或者Open Address法(俗称开放地址)。

但是前人开发出了一种更有效的开放地址方法:多阶再hash法。(其实也可以叫做开Hash法


提供一个二维数组(或者是N个hash链到一个hash list里面),每一层数组的大容量是一个质数,然后每一层质数都要比上一层小

(为什么,专家证明过,这个存储效率高,冲突率小,应该有论文,有兴趣可以自己去找找。)


结构大概如下:

我只是粗略的介绍一下这个结构,有兴趣的可以详细看下面两个链接,它们会告诉你这是个什么玩意,它的性能如何:

cnblogs.com/glacierh/p/

分布式存储系统设计(3)-- 存储结构www.cnblogs.com

cnblogs.com/glacierh/p/

codinginet.com/articles


主要不是介绍这个结构,我只是说,这个方法也间接的把一个大的HashMap拆成了一个二维结构,那么每一个hash的表都不是那么的大,每个小表都可以独立的进行rehash扩容。而rehash也可以考虑为一次rehash完,或者渐进式rehash。

一种高性能多阶哈希表实现www.codinginet.com

主要不是介绍这个结构,我只是说,这个方法也间接的把一个大的HashMap拆成了一个二维结构,那么每一个hash的表都不是那么的大,每个小表都可以独立的进行rehash扩容。而rehash也可以考虑为一次rehash完,或者渐进式rehash。


个人觉得这种扩容方式有两种方向,一个是横向,一个是纵向。

  • 横向
    从高阶往上扫描,找到个填充因子偏高的子表,进行扩容。
    但是需要注意一个问题,每个子表的生长速度可能不一样,也可能一样。并且在向下一阶溢出的时候,需要考虑什么时候要把当前这一层扩容,或者是优先把下一阶扩容,都需要重新权衡。


  • 纵向
    从高阶往下扫描,当每一层的填充引子都大于某个值的时候,则动态加入新一阶子表。这个过程应该也有一个上限,一般阶数不超过100层。所以整个内存增长的容量规划需要好好考虑。不然平均访问阶数变高,性能下降不少。


像上面引用的第二篇文章,就介绍一种大小变化方式,使得数据尽量集中在低阶的表上,这样的平均查询速度会更快。不过这样的话,写的时候也会遭遇问题,需要根据读写需求具体场景具体分析。


LSMTree - In Memory Compaction


我们现在放宽条件。

如果,它不是一个单一的数据结构,而是允许有背景线程处理的话,我们是否还有其他的办法?


这个思路来源于LSMTree(leveldb,rocksdb,HBase等等是这个的一种实现),只是将磁盘的文件的操作全部在内存当中来做罢了。


实际上这个方法也已经有了,在HBase 2.0当中已经引入了In Memory Compaction,通过内存的合并减少写放大,加快读。


一篇介绍的文章,有兴趣的话可以在后面在展开阅读以下:

blogs.apache.org/hbase/


写的时候,永远只写到一个MutableMemTable。

如果超过一定大小,则“snapshot”为一个Immutable的MemTable,依次标号0,1,2,…… 每个MemTable都有附属的生成时间(或者版本号吧)。


读的时候,按照时间或者版本先后顺序(这里可能会比较复杂,需要对MemTable的时间顺序有了解,并且MemTable之间的时间顺序是不应该有交叠的,如果时间是交叠的怎么做我暂时还没想清楚),检查每个MemTable,如果有数据可以直接返回。


我们可以看到,写是非常快的。但是读就比较慢了,每次要读所有的MemTable(如果不命中的话)。所以为了加速读,需要对MemTable进行合并(Compaction),或者还需要BloomFilter


可以设定一些阈值:ImmutableMemTable的个数。

当个数超过限度后,背景线程开始运作,慢慢合并小的MemTable为一个整体。整个过程也是可以是渐进式的。由于合并的都是Immutable的数据,整个过程没有一致性问题。合并完成之后,丢弃老的MemTable即可。

并且合并的时候也可以采取一些策略,每次选择某一部分的MemTable进行合并。保证每次合并的资源消耗不是太大(Minor Compaction)。

也可以为了保证更高的读性能,定时的或者人为的触发对所有ImmutableMemTable的合并(Major Compaction)。


以上这些均和HBase的设计一致,由于只需要支持快速的hash查找,不需要支持顺序查找,只是使用的ConcurrentHashMap,并不是SkipListMap(Java的ConcurrentSkipListMap),所以整个写入读取效率仍然可以视为O(1)。


本地数据存储


数据不再完全分布到内存中了。而是要扩展到系统文件中,并且每个Value的Size还可能比较大。

上述的方法我认为是仍然适用的。因为数据分配,数据寻址,数据重新rehash的过程是一样的。


有几种可以考虑的方案:

  • LSMTree (参考rocksdb,badgar中,HashIndex部分的实现
  • B+Tree,Fractal Tree(这个实际打破了O(1)查找的,成为了O(K*N),K是树的高度,N是每个节点包含数据的个数)
  • Hash Fractal Tree(自创,个人认为可以做成Fractal Tree那样,但是性能已经不是O(1),而是O(K), K是树的高度)

只是作为整个系统需要考虑IO的问题(特别是在普通磁盘的情况下hash查找是比较慢的):

  • 直接大块文件的方法肯定是不可取的了,即使是用这个方法也要做内部数据的仔细切分。
  • 分块存储,有一级索引,二级索引成为了必须(前缀匹配方法,两层地址查找)
  • 或者干脆做成一个树形结构,Hash Tree方法。通过前缀hash
  • 数据地址映射区,和数据区域需要分离
  • 对于数据做Cache,对于索引区和数据区域需要分别做缓存,并且索引区域应该常驻内存
  • 当然对写入更优化的方法,还是采取LSMTree的方法


有一种想法,可以类似Hash Tree,或者Hash List,或者B+Tree:

  • 设计一种分层按照Hash来导航的树形结构,树限制一定的大高度
  • 每一层包含的字节点数目不超过K(可以设计总空间N,K=N*loadFactor),每一层独立建立hash空间
  • 分裂的时即是rehash的时候(或者还有合并操作),因为每个节点并不大,rehash的时候一次完成即可。
  • 如果节点数目超过K,则分裂为两个hash表,每个表大小还是N
  • 但是由于是hash数据分散写到各个文件,并不适合普通Hard Disk,只能适合SSD。而且每个节点都需要带上各自的buffer,合并写入才会提高效率。同样读取的时候也需要带上buffer。(这里就会比较像分型树/Fractal Tree,请参考TokuDB,但是它只是一个hash版本)


这样做的时候,表热点的部分会裂变出很多表出来,导致Tree的层数变高,读和写的性能都会下降。如何平衡的话,和Fractal Tree一样,感觉会是一个比较艰深的话题。


无论是LSMTree模式,还是Tractal Tree模式,还是我说的这一种,都是有内存数据的,需要WAL来进行崩溃恢复。

不过外来的存储方案都是在进步的,个人觉得3~5年之内,AEP(Inter Apache Pass,一种Persistent Memory)的普及,会让WAL消失,以后的design就可以不用考虑WAL,而设计的更细致灵活了。


到这里,关于单机Map的话题就结束了。现在我们来把这个话题拓展到一个集群。

分布式数据库又如何?


我们就是这样奇怪的创造者,创建了一个又一个庞大的怪物应用。使得我们需要不定期的追加机器,去扩容,去再平衡我们的数据。


当然也缔造了在这个上面生根发芽的怪物用户,他们会创造很多关联(加好友,发文章,转发,你都可以认为是发生了关联)。

怪物用户的数据往往造成了极大的存储消耗,无法对这些数据就行良好的分布的话,你总会发现某些机器,或者某些存储单元(比如HBase里面,这个该鸟叫做Region,或者是Store)容易被撑爆。


所以,这时你的这个Map不会光在一台机器上了,可能在一个Cluster上。

整个Cluster形成了一个巨大的Map。这个时候如果这个Map是个HashMap(可以想象,它是一个Redis集群),那这个rehash的扩容问题怎么解决呢?我们还能保证全局都是O (1)的效率访问到数据么?


整体比较简单,其实如果不考虑一致性问题,高可用性,方案都是比较固定而且是明显的。分层解决问题,划分总是解决分布式下scalability问题的一剂良药。由于每个节点hash的rehash和扩容问题都已经有解决方案。剩下的是需要解决请求对于数据在哪个节点的定位问题。


先说结论

  • 从实用的小规模来说,有O(1)时间效率的方案。稍微浪费点空间
  • 更大规模的,还是只能采取O(lg(aK))的方案。K是节点数目,a是一个常数,后面说。且K肯定是远小于整个数据量的大小的。
  • 还有一个方案,是固定路由方案,也是O(lg(R))方案。R是Key的空间切分数目,或者也是partition数目。

保证O(1)的方案:


方案的关键在2倍扩容。

而具体如何路由,可以用hash表,可以用数组取模,都不是问题。

  • 其实我原来在腾讯,有时就会用简单的方案,就是取模,简单有效。
  • 比如Kafka,就会默认用Murmur Hash的partition方法,把数据固定的打到固定partition。虽然Kafka不是数据库,但是它也可以在某种意义上被视为流式存储。可别忘了我刚讲过Kafka Streams的一些东西,Kafka Streams附带Local State Store开启Queryable Interface RPC的时候,那就是一个分布式数据库。

数组的二倍扩容就好说了。二倍扩容的数据不是在前半的老节点上,就是会在新加的一半节点上。所以Mod 2N不会使路由错乱。

Hash的rehash问题我上面已经说了。所以也不是问题。

只是在移动数据的时候,也可以采取渐进式rehash(migrate),或者是一次性完成migrate后再对接新的流量。


另外一个问题就是,由于这种路由是不能容错的。所以一旦节点down机,这个partiton的数据要么是不可用状态,要么需要有Replicate Follower。当然如何做Replicate 保证高可用和一致性,是另外的问题,这回不涉及。


一致性hash方案


这个就是O(log(aK))的方案。

具体做法和基础结构和方法我这里不展开,也比较简单,可以参考下面的链接。

zhuanlan.zhihu.com/p/24

而在今天的主题上,我们聊点其他的。

为什么是叫一致性hash,它跟普通的hash方法或者取模方案的区别,就是解决了两个问题:

  • 实现了N+1扩容,避免了2倍扩容消耗
  • 在N+1扩容的同时,保证了数据分布的均匀性,也保证了极少量的数据发生迁移。


这个方案的本质是:以邻为壑

一旦发生节点退出,邻居就要肩负起它的责任。所以默认的实现是有缺陷的,如果节点的load已经超过本身负载上限的50%,则会发生雪崩。

为了防止雪崩,引入了虚拟节点的概念,使得数据空间被随机打的更散。一台机器有a个虚拟空间,所以一台机器的邻居在概率上就变成了a个。

这个a就是那个公式的a,所以本质成为了顺序空间的索引定位问题。它的下限是lgK。但是虚拟节点个数是aK个,那么整体性能就是O(lg(aK))


所以问题就来了,a一般取200个,越多数据空间可以打的约散。K如果大集群下,可以有几千台或者几万台服务器。如果是3000台机器,每次查找次数就大概是20次,并且这个虚拟节点内存的消耗随之会增长也是一个问题,如果节点频繁的进入退出(p2p网络),会造成巨大的消耗。


默认的有名的实现是Ketama算法,是割环算法的一个标准实现,也比较简单。

除了默认的割环算法,还有几个算法可以参考一下,具体我就不展开了,有兴趣可以多了解一下:

  • rendezvous hashing: 解决了访问热点的问题。
  • jump hash:来自谷歌研发的算法,可以参考下面的论文链接。几乎0内存消耗,logK的效率解决了(可以认为a=1),数据分布均匀,也热点问题也解决的很好。

参考

en.wikipedia.org/wiki/R

GitHub新负载均衡系统的设计历程

stackoverflow.com/quest

colobu.com/2016/03/22/j

xiaoyue26.github.io/201

arxiv.org/ftp/arxiv/pap


固定路由方案


这个方案也叫做空间预分配方案。也是比较多的分布式数据库会使用的方案,如:MongoDB,HBase,Redis 3.0,以及类HBase的其他分布式数据库等等。


和一致性hash一样,是有一个KeySpace的。

一致性hash的KeySpace是0~2^64-1,是整数值域。

但是固定路由的话,KeySpace则不一定。它可以是任意数据的分布空间,所以一般定义的KeySpace=bytes[Start, End]。预分配,则会先创建R个partition(或者叫shard,region,range,都可以)。partition=bytes[Start, End]。


partition分为R个左闭右开区间,将整个KeySpace完整切分。然后R个区间映射到K台机器上。在R个区间里面定位也是O(logR)的性能。从R定位机器是O(1)。


所以这也是一个两层切分的思路。但是两层之间的映射是灵活的,为数据的迁移,HA,以及负载均衡提供了基础,并且可以在上面施加不同灵活程度的控制算法。


partition的分裂,或者partition的迁移,就可以视为一个片段的rehash过程。不过注意的问题不一样:

  • 分裂的点在bytes[Start, End]中的选择。需要避开热点问题。一般Start,End都会只用一个KeyPrefix。如果某些数据过于集中(怪物用户)存在,则这个中点的分裂需要考虑增大KeyPrefix长度。不然分裂会失败,热点无法完好消除。
  • 分裂之后,partition的迁移,有时候需要根据每个partiton的size分布来决定,有时候需要根据当前访问的load决定。这涉及到一些均衡算法。如何选取是一个权衡过程。这里也不展开了,后面后机会再介绍一下。

到此,大概讲了讲如何做一个可以灵活扩容的Map了,而且这个Map可以做的很大:)

希望会对你有点启发。也欢迎来知乎上讨论。知乎搜索:imgaara 可以找到我。


谢谢你读到这里!

相关文章