{技术}某分布式应用实践一致性哈希的一些问题
TimYang
最近项目中一个分布式应用碰到一些设计问题，听过上次技术沙龙key value store漫谈的同学可能会比较容易理解以下说明。
场景
假定一个有状态的服务，可以理解成web或者socket服务器，每个用户在这个服务上登录后是有状态的，我们把它的状态连同其他加载到内存的用户数据
统称用户session。由于session数据实时会变化，加上程序访问session频率大，几乎所有的操作都跟session数据相关，因此不适
合放在远程memcached中
第一阶段
考虑到单服务器不能承载，因此使用了分布式架构，最初的算法为 hash() mod n, hash()通常取用户ID，n为节点数。此方法容易实现
且能够满足运营要求。缺点是当单点发生故障时，系统无法自动恢复。
figure1 http://timyang.net/blog/wp-content/uploads/2009/09/figure1.png
第二阶段
为了解决单点故障，使用 hash() mod (n/2), 这样任意一个用户都有2个服务器备选，可由client随机选取。由于不同服务器之间的
用户需要彼此交互，所以所有的服务器需要确切的知道用户所在的位置。因此用户位置被保存到memcached中。
当一台发生故障，client可以自动切换到对应backup，由于切换前另外1台没有用户的session，因此需要client自行重新登录。
figure2 http://timyang.net/blog/wp-content/uploads/2009/09/figure2.png
这个阶段的设计存在以下问题
* 负载不均衡，尤其是单台发生故障后剩下一台会压力过大。
* 不能动态增删节点
* 节点发生故障时需要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 http://timyang.net/blog/wp-content/uploads/2009/09/figure3.png
优点：发生单点故障时负载会均衡分散到其他所有节点，程序实现也比较优雅。
应用一致性哈希分布后若干问题
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来寻址。从实用的角
度来看，这样似乎程序更简单。
因此，一致性哈希分布对于这个场景来说是无用的？
jingmi
载。
受限于当时的工期时间，也是采用了多个 memcached 来做小 session 的存储（我的应用环境和规模可能算比较大的，所以这里只是用于存
储各个业务系统的公共 session 数据，这些数据规模比较小，放入 memcached）。
On Sep 8, 5:54 pm, TimYang <iso1...@gmail.com> wrote:
> (在blog上刚发过，在TL再发，希望能够得到更多指点)
>
> 最近项目中一个分布式应用碰到一些设计问题，听过上次技术沙龙key value store漫谈的同学可能会比较容易理解以下说明。
>
> 场景
> 假定一个有状态的服务，可以理解成web或者socket服务器，每个用户在这个服务上登录后是有状态的，我们把它的状态连同其他加载到内存的用户数据
> 统称用户session。由于session数据实时会变化，加上程序访问session频率大，几乎所有的操作都跟session数据相关，因此不适
> 合放在远程memcached中
其实放在远程 memcached 没有什么问题，网络连接的主要开销在建立连接，使用长连接后在同机房内的传输开销并不高，这需要 index
server 的介入，index server 介入后可以很好的实现各种错误的检查已经负载均衡，在一台 memcached down 机后或加
入新机器时完成后端数据的重新分布。
>
> 应用一致性哈希分布后若干问题
> 1.如何解决单点故障时候的session迁移？是否所有session都像Dynamo那样写入到多个节点(或双写)？如果双写所有的服务器需要消耗
> 2倍的内存及更多CPU资源，所以优先不考虑双写方案。
没必要都写到内存，可以分发到多机，写入队列再定期写入磁盘。这里需要权衡，我觉得这样的系统， Consistency 更加重要，所以有必要花些功
夫在这里，这里面的问题都是实现细节了。
>
> 2.如果不双写，则发生故障切换时，即使服务器内部自动帮用户切换节点不重新登录，都需要牵涉到大量session重建，会引起集群震荡。当然这里可以
> 稍微优化，比如session按需建立，IDLE的用户可以先不重建。
>
> 3.当故障节点恢复时候如何处理？Dynamo的策略是故障期间所有的数据都属于hinted handoff, 就是备用机起业务代理作用，一旦故障
> 机恢复就立即把所有临时数据从备用机拉回去，然后整个集群恢复正常流程。但由于本场景session数据比较笨重，而且牵涉到复制时存在并发变更，如果
> 直接借鉴Dynamo的话则感觉切换成本过高，大部分开发人员倾向于继续用备用机处理该用户业务。如果恢复正常后不切换，则存在用户位置的不确定性，使
> 用一致性哈希算出来的结果和用户实际所在的节点不同。需要顺着圆环往下找用户,效率很低。因此就有提议把所有用户所在的当前节点位置写入
> memcached。
>
> 5. 假如需要将位置写入memcached,那似乎一致性哈希算法又成了花瓶，完全可以由client在create session时候随机选取一
> 个没有故障的节点, 然后把位置写入memcached, 某个节点发生故障时，client再另外选一个随机的，并把新的位置写入
> memcached, 所有用户所在节点的位置都通过memcached来存储，服务器之间实时的通讯也通过查询memcached来寻址。从实用的角
> 度来看，这样似乎程序更简单。
这就是一台 index server 了，大型的分布式系统都离不开 index server 。
>
> 因此，一致性哈希分布对于这个场景来说是无用的？
我觉得如果要求很高的话，不是很实用。
lijie
应用一致性哈希分布后若干问题
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来寻址。从实用的角
度来看，这样似乎程序更简单。
因此，一致性哈希分布对于这个场景来说是无用的？
lijie
TimYang
> > 假定一个有状态的服务，可以理解成web或者socket服务器，每个用户在这个服务上登录后是有状态的，我们把它的状态连同其他加载到内存的用户数据
> > 统称用户session。由于session数据实时会变化，加上程序访问session频率大，几乎所有的操作都跟session数据相关，因此不适
> > 合放在远程memcached中
>
> 其实放在远程 memcached 没有什么问题，网络连接的主要开销在建立连接，使用长连接后在同机房内的传输开销并不高，这需要 index
> server 的介入，index server 介入后可以很好的实现各种错误的检查已经负载均衡，在一台 memcached down 机后或加
> 入新机器时完成后端数据的重新分布。
>
>
>
> > 应用一致性哈希分布后若干问题
> > 1.如何解决单点故障时候的session迁移？是否所有session都像Dynamo那样写入到多个节点(或双写)？如果双写所有的服务器需要消耗
> > 2倍的内存及更多CPU资源，所以优先不考虑双写方案。
>
> 没必要都写到内存，可以分发到多机，写入队列再定期写入磁盘。这里需要权衡，我觉得这样的系统， Consistency 更加重要，所以有必要花些功
> 夫在这里，这里面的问题都是实现细节了。
分布式service场景session数据变化快，写到磁盘不太实用，可能你的场景是做分布式storage吧
ma josh
> > 场景index server也有故障的可能，无法去中心化，整个体系会依赖某台机，当然mc故障率其实并不高。
> > 假定一个有状态的服务，可以理解成web或者socket服务器，每个用户在这个服务上登录后是有状态的，我们把它的状态连同其他加载到内存的用户数据
> > 统称用户session。由于session数据实时会变化，加上程序访问session频率大，几乎所有的操作都跟session数据相关，因此不适
> > 合放在远程memcached中
>
> 其实放在远程 memcached 没有什么问题，网络连接的主要开销在建立连接，使用长连接后在同机房内的传输开销并不高，这需要 index
> server 的介入，index server 介入后可以很好的实现各种错误的检查已经负载均衡，在一台 memcached down 机后或加
> 入新机器时完成后端数据的重新分布。
jingmi
jingmi
On Sep 10, 10:53 am, TimYang <iso1...@gmail.com> wrote:
> > > 场景
> > > 假定一个有状态的服务，可以理解成web或者socket服务器，每个用户在这个服务上登录后是有状态的，我们把它的状态连同其他加载到内存的用户数据
> > > 统称用户session。由于session数据实时会变化，加上程序访问session频率大，几乎所有的操作都跟session数据相关，因此不适
> > > 合放在远程memcached中
>
> > 其实放在远程 memcached 没有什么问题，网络连接的主要开销在建立连接，使用长连接后在同机房内的传输开销并不高，这需要 index
> > server 的介入，index server 介入后可以很好的实现各种错误的检查已经负载均衡，在一台 memcached down 机后或加
> > 入新机器时完成后端数据的重新分布。
>
> index server也有故障的可能，无法去中心化，整个体系会依赖某台机，当然mc故障率其实并不高。
index server 不只一台，简单的解决办法可以在应用端进行选择，如果服务彻底挂掉，判断 connection refused 是很快
的，做分布式，这种模块应该是很基础的；另外复杂点也是我采用的方法，实现选举和 ip 漂移，保证服务的稳定，这里面如果单纯通过 tcp/ip 的
心跳包做健康检查会有一些麻烦，比如机器在不同机架，连接瞬断这些异常情况，总之实现上要很细心。事实上，因为 index server 基本可以认
为是无状态的，所以实现起来并不是很麻烦。
> > 没必要都写到内存，可以分发到多机，写入队列再定期写入磁盘。这里需要权衡，我觉得这样的系统， Consistency 更加重要，所以有必要花些功
> > 夫在这里，这里面的问题都是实现细节了。
>
> 分布式service场景session数据变化快，写到磁盘不太实用，可能你的场景是做分布式storage吧
写磁盘不是直接写的，可以在 a 机器上写内存，然后 forward 到 b 机器，b 机器将待写数据以日志形式追加到内存 buffer，这就算
完成一次请求了，定期回放 buffer 中的日志到磁盘，用于实现持久化，而普通的查询都在 a 上进行。有机会的话，你可以学习一下 GFS 这样
的大型 DFS 采用的写入策略。
raymond
On 9月8日, 下午5时54分, TimYang <iso1...@gmail.com> wrote:
> (在blog上刚发过，在TL再发，希望能够得到更多指点)
>
> 最近项目中一个分布式应用碰到一些设计问题，听过上次技术沙龙key value store漫谈的同学可能会比较容易理解以下说明。
>
> 场景
> 假定一个有状态的服务，可以理解成web或者socket服务器，每个用户在这个服务上登录后是有状态的，我们把它的状态连同其他加载到内存的用户数据
> 统称用户session。由于session数据实时会变化，加上程序访问session频率大，几乎所有的操作都跟session数据相关，因此不适
> 合放在远程memcached中
>
> 第一阶段
> 考虑到单服务器不能承载，因此使用了分布式架构，最初的算法为 hash() mod n, hash()通常取用户ID，n为节点数。此方法容易实现
> 且能够满足运营要求。缺点是当单点发生故障时，系统无法自动恢复。
>
> figure1http://timyang.net/blog/wp-content/uploads/2009/09/figure1.png
>
> 第二阶段
> 为了解决单点故障，使用 hash() mod (n/2), 这样任意一个用户都有2个服务器备选，可由client随机选取。由于不同服务器之间的
> 用户需要彼此交互，所以所有的服务器需要确切的知道用户所在的位置。因此用户位置被保存到memcached中。
>
> 当一台发生故障，client可以自动切换到对应backup，由于切换前另外1台没有用户的session，因此需要client自行重新登录。
>
> figure2http://timyang.net/blog/wp-content/uploads/2009/09/figure2.png
>
> 这个阶段的设计存在以下问题
>
> * 负载不均衡，尤其是单台发生故障后剩下一台会压力过大。
> * 不能动态增删节点
> * 节点发生故障时需要client重新登录
>
> 第三阶段
> 打算去掉硬编码的hash() mod n 算法，改用一致性哈希(consistent hashing)分布
> 假如采用Dynamo中的strategy 1(可参看Dynamo: Amazon's Highly Available Key-value
> Store, PDF, P216)
> 我们把每台server分成v个虚拟节点，再把所有虚拟节点(n*v)随机分配到一致性哈希的圆环上，这样所有的用户从自己圆环上的位置顺时针往下取到
> 第一个vnode就是自己所属节点。当此节点存在故障时，再顺时针取下一个作为替代节点。
>
> figure3http://timyang.net/blog/wp-content/uploads/2009/09/figure3.png
>
> 优点：发生单点故障时负载会均衡分散到其他所有节点，程序实现也比较优雅。
>
> 应用一致性哈希分布后若干问题
> 1.如何解决单点故障时候的session迁移？是否所有session都像Dynamo那样写入到多个节点(或双写)？如果双写所有的服务器需要消耗
> 2倍的内存及更多CPU资源，所以优先不考虑双写方案。
>
目前来看，backup是要求恢复到原状的唯一方法（除非你有明确的函数从输入计算输出，而这对苯session来说是不存在的）。所以，如果容忍，就
让用户relogin，否则就必须备份。或者采用一些折中的策略，比如备份那些非常重要的内容。
> 2.如果不双写，则发生故障切换时，即使服务器内部自动帮用户切换节点不重新登录，都需要牵涉到大量session重建，会引起集群震荡。当然这里可以
> 稍微优化，比如session按需建立，IDLE的用户可以先不重建。
这是显然的，因为发生故障了，如果发生了故障而没有任何代价，那就不叫故障
>
> 3.当故障节点恢复时候如何处理？Dynamo的策略是故障期间所有的数据都属于hinted handoff, 就是备用机起业务代理作用，一旦故障
> 机恢复就立即把所有临时数据从备用机拉回去，然后整个集群恢复正常流程。但由于本场景session数据比较笨重，而且牵涉到复制时存在并发变更，如果
> 直接借鉴Dynamo的话则感觉切换成本过高，大部分开发人员倾向于继续用备用机处理该用户业务。如果恢复正常后不切换，则存在用户位置的不确定性，使
> 用一致性哈希算出来的结果和用户实际所在的节点不同。需要顺着圆环往下找用户,效率很低。因此就有提议把所有用户所在的当前节点位置写入
> memcached。
>
consistent hash的提出是解决机器变动大规模数据迁移的问题，他只保证单台机器坏掉，不会过多的影响其他机器的数据。你的问题基本上有两
个子问题：
第一，数据原来存在哪里，某台服务器发生故障后，数据又存在哪里。这是consistent hash 要解决的。
第二，在任何时候，client如何知道数据在哪里？这需要另外的机制来提供，这不是consistent hash需要解决的问题。这里你使用
hashmap，indext tree。。。。
我没有看过memcache的代码，但是看到有人说，memcache似乎实现了consistent hash的。如果这样，你的这个case似乎可
以直接用memcache实现了。
> 5. 假如需要将位置写入memcached,那似乎一致性哈希算法又成了花瓶，完全可以由client在create session时候随机选取一
> 个没有故障的节点, 然后把位置写入memcached, 某个节点发生故障时，client再另外选一个随机的，并把新的位置写入
> memcached, 所有用户所在节点的位置都通过memcached来存储，服务器之间实时的通讯也通过查询memcached来寻址。从实用的角
> 度来看，这样似乎程序更简单。
>
> 因此，一致性哈希分布对于这个场景来说是无用的？
consistent hash解决了机器故障引起的大规模数据变更问题，是这个场景中的一个部分，不是说，consistent hash就能完全解
决这个问题。
采用mamcache，如果你觉得一个maste不保险，就用两个，三个，四个。。。，用PAXOS（chubby的用法）算法保证这些master中
的一个当掉后，其他master能够继续充当master的角色，而且能够基本保持状态的一致性。