• Email:

      微信公众号:

      qrcode_for_timyang_small
  • 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来寻址。从实用的角度来看,这样似乎程序更简单。

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

    42 Comments  »

    1. ssp says:

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

    2. sky says:

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

    3. dashuibin says:

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

    4. raymond says:

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

    5. kafka0102 says:

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

    6. gilbert says:

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

    7. Tim says:

      gibert:

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

    8. csh says:

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

    9. Tim says:

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

    10. csh says:

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

    11. Tim says:

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

    12. csh says:

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

    13. Tim says:

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

    14. csh says:

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

    15. Tim says:

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

    16. csh says:

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

    17. gilbert says:

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

    18. fcicq says:

      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 says:

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

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

    20. crackcell says:

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

    21. bright says:

      是对buddy replication的改进思路吗?

    22. Tim says:

      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 says:

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

    24. Alex says:

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

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

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

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

    25. nick says:

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

    26. 换个角度考虑 says:

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

    27. 珠海大壮 says:

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

    28. assad says:

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

    29. Wesley says:

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

    30. banq says:

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

    31. lisafang says:

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

    32. 玉面飞龙 says:

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

    33. Bruce says:

      Hi Tim,

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

    34. moheng says:

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

    35. yob says:

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

    36. tianxiao says:

      使用一致性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了,使用取摸的方式会更加简单一些。

    RSS feed for comments on this post, TrackBack URI

    Leave a Comment