• Feeds

  • 某分布式应用实践一致性哈希的一些问题

    最近项目中一个分布式应用碰到一些设计问题,听过上次技术沙龙key value store漫谈的同学可能会比较容易理解以下说明。

    场景
    假定一个有状态的服务,可以理解成web或者socket服务器,每个用户在这个服务上登录后是有状态的,我们把它的状态连同其他加载到内存的用户数据统称用户session。由于session数据实时会变化,加上程序访问session频率大,几乎所有的操作都跟session数据相关,因此不适合放在远程memcached中

    第一阶段
    考虑到单服务器不能承载,因此使用了分布式架构,最初的算法为 hash() mod n, hash()通常取用户ID,n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发生故障时,系统无法自动恢复。

    figure1

    第二阶段
    为了解决单点故障,使用 hash() mod (n/2), 这样任意一个用户都有2个服务器备选,可由client随机选取。由于不同服务器之间的用户需要彼此交互,所以所有的服务器需要确切的知道用户所在的位置。因此用户位置被保存到memcached中。

    当一台发生故障,client可以自动切换到对应backup,由于切换前另外1台没有用户的session,因此需要client自行重新登录。

    figure2

    这个阶段的设计存在以下问题

    • 负载不均衡,尤其是单台发生故障后剩下一台会压力过大。
    • 不能动态增删节点
    • 节点发生故障时需要client重新登录

    第三阶段
    打算去掉硬编码的hash() mod n 算法,改用一致性哈希(consistent hashing)分布
    假如采用Dynamo中的strategy 1(可参看Dynamo: Amazon’s Highly Available Key-value Store, PDF, P216)
    我们把每台server分成v个虚拟节点,再把所有虚拟节点(n*v)随机分配到一致性哈希的圆环上,这样所有的用户从自己圆环上的位置顺时针往下取到第一个vnode就是自己所属节点。当此节点存在故障时,再顺时针取下一个作为替代节点。

    figure3

    优点:发生单点故障时负载会均衡分散到其他所有节点,程序实现也比较优雅。

    应用一致性哈希分布后若干问题
    1.如何解决单点故障时候的session迁移?是否所有session都像Dynamo那样写入到多个节点(或双写)?如果双写所有的服务器需要消耗2倍的内存及更多CPU资源,所以优先不考虑双写方案。

    2.如果不双写,则发生故障切换时,即使服务器内部自动帮用户切换节点不重新登录,都需要牵涉到大量session重建,会引起集群震荡。当然这里可以稍微优化,比如session按需建立,IDLE的用户可以先不重建。

    3.当故障节点恢复时候如何处理?Dynamo的策略是故障期间所有的数据都属于hinted handoff, 就是备用机起业务代理作用,一旦故障机恢复就立即把所有临时数据从备用机拉回去,然后整个集群恢复正常流程。但由于本场景session数据比较笨重,而且牵涉到复制时存在并发变更,如果直接借鉴Dynamo的话则感觉切换成本过高,大部分开发人员倾向于继续用备用机处理该用户业务。如果恢复正常后不切换,则存在用户位置的不确定性,使用一致性哈希算出来的结果和用户实际所在的节点不同。需要顺着圆环往下找用户,效率很低。因此就有提议把所有用户所在的当前节点位置写入memcached。

    5. 假如需要将位置写入memcached,那似乎一致性哈希算法又成了花瓶,完全可以由client在create session时候随机选取一个没有故障的节点, 然后把位置写入memcached, 某个节点发生故障时,client再另外选一个随机的,并把新的位置写入memcached, 所有用户所在节点的位置都通过memcached来存储,服务器之间实时的通讯也通过查询memcached来寻址。从实用的角度来看,这样似乎程序更简单。

    因此,一致性哈希分布对于这个场景来说是无用的?

    如想及时阅读Tim Yang的文章,可通过页面右上方扫码订阅最新更新。

    « | »

    47 Comments  »

    1. ssp

      一致性哈希只是解决少量增减服务器导致的大量震荡问题,要保持会话的延续不是他可以解决的。

    2. sky

      mc只是缓存而已。session应该落地,用mc挡一层。

    3. dashuibin

      如果4、5中的保存位置的memcached不幸挂了,那岂不是所有人都不能用了,又回到了一个单点问题了

    4. raymond

      用mc存储位置关系,这是正解,我们也是这样实现的。

    5. kafka0102

      如果使用memcached存储session节点位置,应该是有memcached备机(复制)来在单点失败时切换。但session节点的失败随机选一台可能不会平衡session机器的负载。
      像session信息不存多份的情况,使用一致性hash有些大了。不过也可以做的更完备,就是虚拟节点和物理节点的关系表以及机器的状态大家共享,当某个节点down掉,由大家投票选出一个该虚拟节点对应的物理节点接管session。如果机器恢复,可以再次更新关系表,但可以不必切回状态。

    6. 其实,你在文章的一开始就已经给出了这个场景不适用DHT的原因:
      1、每个用户在这个服务上登录后是有状态的,我们把它的状态连同其他加载到内存的用户数据统称用户session。(数据关系复杂,不再是简单的NOSQL数据)
      2、由于session数据实时会变化,加上程序访问session频率大,几乎所有的操作都跟session数据相关。(实时更新,而且对数据一致性要求较高,而且你要求session都是内存数据,不进行固化,因此也不适合DHT)

    7. Tim

      gibert:

      1. session就是key value, key: username, value: map
      2. 关键问题是node failure之后session如何在backup restore, 如果内存数据无法根据db restore, 则更改的时候需要多机修改保持一致,能从db restore的话更简单,backup直接接管。特别是使用了virtual node之后,流量分开到多处,过渡很轻松。

    8. csh

      你这里的session是持久化的还是保持在内存中的,看上去似乎需要的是一个能够保持一致性的分布式内存服务,但不想浪费内存在多备份上,似乎是想解决这么个问题?

    9. Tim

      我的场景细节可能不具有通用性,简单描述如下,供参考。
      session数据是db的一个cache, 比如类似好友列表这样的数据,可以从db/memcached恢复。但是如果节点失效时候,备份节点简单的从db恢复会造成db压力过大,即使用memcached恢复也会导致网络风暴。我们希望能够有一个平滑的过渡,因此使用了virtual node及lazy load的方法。

    10. csh

      那session数据为什么不能放在memcached里?因为eviction?

    11. Tim

      因为cache离cpu越近越好。
      另外一种说法就是访问越频繁的数据需要离cpu约近。

    12. csh

      您的意思是您当前的方案中本机的cpu处理的session都是来源于本机上的virtual node?

    13. Tim

      是的,vnode概念和dynamo是相似的,1台物理机上有多个vnode, session数据通常要放在本地。

    14. csh

      那您这里vnode和cpu业务层交换数据走的还是进程间通信吗? 节省的是网络通信的开销。我的理解是:您这里session储存的机器上不像dynamo那样简单的提供一个数据存储的功能,而且上面会有与session数据处理相关的逻辑,例如修改好友列表,批量写入数据库等逻辑,是吗?

    15. Tim

      如果按你所说多进程的方式的话是需要加业务逻辑。
      不过我的是单进程多线程,session只是一个数据结构,比如好友列表/黑名单/隐私设置等业务数据,当然由于多线程访问需要加同步锁保护才能访问,不过这些就说远了。
      另外如果多进程我觉得用share memory方式更方便,用erlang轻量级进程语言的话用ets(memory db)也比用message传递要好。

    16. csh

      我是不是可以这么理解,您的这个管session的进程其实相当于 memcached+session操作逻辑,也就是原本在使用memcached场景中,远程业务层的操作逻辑放到这个管session的进程中,并且在session的分布上使用了vnode?

    17. 我感觉你这个需求如果想解决,最终还是要进行多种方案的tradeoff,而tradeoff的根据就是尽量支持优先级高的需求,例如稳定性,或者性能。由于这些涉及到很多细节,估计讨论很难深入下去了~~~

    18. fcicq

      Replication with Consistent Hash Rotation.

      Example:
      node 0 replicate to node 5, 1 to 6 … f to 4.
      in CRC32, just add 0xffffffff / 3 = 0x55555555 to the hash & you got the slave node.
      (Why / 3 not / 2 ?)

      you know (2 nodes) Tokyo Cabinet, memory(master) -> db file(slave, compressed?).
      Just Need Some Hacking. haha.

    19. Tim

      上面这篇文章相关consistent hashing问题实际已经解决了,在实际环境运行得还不错,至少上线之后几乎不用为单点故障担心了。相关细节也在前几篇comments里面差不多都有表达。由于后续实践解决思路相比dynamo思想也无新的建树,所以就没专门写文描述了。

      fcicq: 你的方案实际跟我的第二阶段相似,存在发生单点故障时候,(1)备份节点负载过大的问题,另外(2)如果node0和node5都crash了系统就会部分(20%)用户服务不可用。而用consistent hashing则不存在上述2个缺陷。

    20. crackcell

      兄台能否透露下最后的解决方案,我也遇到了类似的问题,希望能借鉴一下前人的经验。

    21. bright

      是对buddy replication的改进思路吗?

    22. Tim

      AFAIK, buddy replication只是一个jboss中一个术语 https://www.redhat.com/docs/manuals/jboss/jboss-eap-4.3/doc/cache/Tree_Cache_Guide/Clustered_Cache___Using_Replication-Buddy_Replication.html 意思是用户session数据可以只复制到少数几台机,和本文并没有直接可比性。

    23. faryang

      存用户位置的MEMCACHE挂掉怎么办?

    24. Alex

      从上面了解到讨论的是consistent hashing基础上解决Session分布问题,至于一性Hash在这里是不是无用,有下面两个思路。

      1.consistent hashing 是为了解决机器单点故障以及增减机器时减少数据损失的方案。对于解决session迁移是不适合的。

      因为出故障总是会出现数据损失的情况,如果要解决场景问题,就是解决数据损失问题。解决数据损失问题,我们很容易想到双写备份的方法,问题是这样又会出现服务器需要消耗2倍的内存及更多CPU资源,不用这个解决方案呢,又有降低用户
      体现(重新登录)和Session重建问题。

      2.通过1的描述,这个场景问题其实就是Session的持久的问题,关于Session的问题,WEB服务器其实也是用复制备份的方法解决的,我们把Session抽出来进行分布集群只是想让复制减少,速度更快。我们做双写也是复制备份方法。至于consistent hashing在这里的作用只是分布集群上的作用,对于Session迁移来说并不能直接解决问题。

    25. nick

      感觉你的这些需求,coherence已经解决得很完美了,为什么还要自己做呢?

    26. 换个角度考虑

      down机的几率有多少,一年几次,还是几十次?如果是几次,那么用户重新登录一下又何妨呢,不能因噎废食。如果说就因为一次重新登录而导致用户再也不来了,那这用户脑袋绝对有问题。而只为了做到所谓完美,想各种办法解决,耗费大量财力,如果是在实验室搞研究,无可厚非,用在实际中,感觉也是没有必要的

    27. 珠海大壮

      第三阶段,倒是挺满足我的需求。
      但有一点,负载均衡没有解决吧,如果所有请求都集中到某个服务器上怎么办?

    28. 看有些评论太可怕了,要是所有的节点都挂了,连Web server也挂了,那么就什么都不用了

    29. Wesley

      Hi Tim,
      ” 我们希望能够有一个平滑的过渡,因此使用了virtual node及lazy load的方法。”
      请教lazy load 使用的是write behind 还是 write through的方式?应该是异步的write behind方式吧。

    30. 使用Cassandra实现用户相关数据,自己做可使用Gossip

    31. lisafang

      很同意换个角度考虑的看法,强的系统只做系统本分事,有很多东西看起来是没有必要的

    32. 后台加几个数据库,按照session_user_id hash, load分散到多台机器上,SSD+large memory,capacity说不定也够用啊

    33. Bruce

      Hi Tim,

      实际是采用后台data replica把数据同步到hash环的第N+1节点吗?

    34. moheng

      hash最关键在于hash分布一定要均衡。
      你如果使用memcache存储节点位置,当某个节点crash掉的时候,再随机选取另一个节点,写入memcache。这会出现什么结果呢?新加入的session根据你的hash算法可能是均衡分布的,但是整个集群是均衡分布的么?不是的。如果想让整个集群均衡分布,需要移动整个集群的session,根据最新的节点数量重新hash。这样势必会导致集群间大量数据移动,及集群震荡。
      然而一致性hash就是为解决动态新增和删除机器节点而生的。当机器节点数变化时,只是移动少量节点数据。

    35. yob

      对于数据库就不一样了。你总不能把所有的key放在哪都存在mc里吧?

    36. tianxiao

      使用一致性hash在服务器故障及恢复,增加机器,减少机器时,会大大减少对memcached的写入量以及session重建量。

      1.在出现服务器故障时,采用一致性hash,只有k/n的用户需要更新位置信息和重建session(k是用户数,n是服务器数),如果是mod的方式,会有k/n+x的用户需要更新位置信息和重建session(x是指故障期间session失效的用户,这些用户必须要重新建立连接,由于服务器数量发生了变化,导致这些用户会被分不到其他机器,从而需要更新位置信息。)
      2.故障恢复时候的情况与发生故障时候的情况是一样的,当用户的session失效需要重建的时候,使用一致性hash只会有k/n的用户需要更新位置信息和创建session,取摸的方式下,则会有k/n+x的用户需要更新位置信息和创建session(x是指在故障期间发生了session迁移的那些用户)。
      3.添加服务器时,如果使用一致性hash,那么会有k/n+1的用户需要更新位置信息和创建session(n原来服务器的数量,n+1表示增加了一台服务器),如果是mod的方式,那么几乎所有用户都需要更新位置信息和创建session
      4.减少服务器的时候,如果使用一致性hash,那么会有k/n-1的用户需要更新位置信息和创建session(n是原来服务器的数量,n-1表示减少了一台服务器),如果是mod的方式,那么几乎所有的用户都需要更新位置信息和创建session。

      根据上面的分析,在用户数量庞大的场景下,一致性hash还是能够起到很好的降低系统开销的效果的,如果用户数量不大,那么确实没有必要使用一致性hash了,使用取摸的方式会更加简单一些。

    37. 可以考虑阶段二和阶段三进行结合,即节点构成一致性hash,每个节点又是主从同步,同时使用sentinel做主从自动切换。 [高可用分布式缓存系统](http://blog.arganzheng.me/posts/redis-ha.html)

    38. What you learn from playing Poptropica is the same thing that you can learn while playing Blood 2. It is essentially a carbon copy of the game. Even though they spruced it up a bit with new graphics and a brand new soundtrack, the gameplay is still the exact same. I am not saying that you don’t need to play it because you have already played the original version, the new one is still fun to play and it takes you back to the good old days when you played the first game. If you really want a new game to play, you can try here https://chrome.google.com/webstore/detail/among-us-online/nhklobelplcndebifbcmideenegaikgm

    39. Peter

      Wow. The script worked on my project. Can you enlighten me what is the difference between drywall and sheetrock? Thanks in advance.

    Leave a Comment