一致性hash应用到redis

理解分布式存储的本质

有一个经典的实践经验:

数(值)据大了, 什么都是问题!
  • 如果要求128B或更大数值计算, 哪么四则运算会是个大问题!
  • 如果要求128T或更大日志存储, 哪么文件存储会是个大问题!
  • 如果要求128W或更大并发操作, 哪么内存管理会是个大问题!

等等....."墨菲定律", 凡有如果就会发生, Redis缓存数据就是一例! 单机128G内存都无法满足,咋办? 最简单的答案就是大学"数据结构与算法分析"的经常考点:"分而治之"策略. 何谓"分而治之", 就是用餐盒打包饭菜, 一个不够就二个, 二个不够就三个...很少人会去考虑其中蕴含的逻辑哲理.

实现分布式存储的关键

分布式存储的关键:

咋分?

一般都是在三个"方便"中权衡:

  • 方便加速读的性能.
  • 方便加速写的性能.
  • 方便扩展维护,故障恢复.

    结合日常需求, 很容易明白这些"方便"的意义.

为了满足上述需求, 很多"聪明人士"抽象了"虚拟结点", 再想出了"二层映射"思路(算法):

  1. 先将数据主键映射到虚拟(存储)结点.
  2. 再将虚拟结点映射到物理(存储)结点.

步骤1要求尽可能离散,尽可能均衡, 才能分摊读写的瓶颈. 这涉及"离散空间中的一般均衡理论". 说白了, 就是选择算法实现的优劣.

步骤2要求总够的灵活度, 才能实现扩展维护, 故障恢复. 说白了, 就是*组合.

基于这种思路的生产算法:

  1. 一致性HASH算法:
  • 数据主键映射到虚拟结点:
HASH(key): unsigned int

结果介于0~2^32-1 (JAVA是-2^16 ~ 2^16-1). 为什么是2^32? 因为32位OS最直接的支持就是unsigned int.

  • 虚拟结点映射到物理结点:
switch(HASH(key)){
case (L0, H0]: Node0;
case (L1, H1]: Node1;
...
default: Node0;
}

(Li, Hi]->Nodei是由业务维护的一张映射关系表. 可变!

  1. ceph的CRUSH算法
  • 数据主键映射到虚拟结点:
hash(oid) & mask -> pgid
  • 虚拟结点映射到物理结点:
clustermap(pgid) -> osds

一般hash与一致性hash的优劣

一般hash与致性hash都可以实现将数据分布

  • 一般hash实现及优劣:
    HASH(key)%N
  1. 优点: 够简单, 我喜欢! 先hash, 再模N.
  2. 缺点: N变化波及整个离散空间.
  • 一致性hash实现及优劣:
switch(HASH(key)){
case (L0, H0]: Node0;
case (L1, H1]: Node1;
...
default: Node0;
}
  1. 优点:
  2. 缺点: 计算复杂了点.

相关算法实现

  • 数据主键映射到虚拟结点: MD5, MurmurHash.

    • MD5是16Byte, 映射到4Byte的int.
    • MurmurHash算法:高运算性能,低碰撞率,由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年Appleby被Google雇佣,随后Google推出其变种的CityHash算法.

      官方网站:https://sites.google.com/site/murmurhash/
  • 虚拟结点映射到物理结点: 红黑树

    参考资料:http://blog.csdn.net/yuhk231/article/details/51218244

上一篇:IT兄弟连 HTML5教程 设置IE9以下版本浏览器支持HTML5


下一篇:FreeBSD 安装axel提高ports的安装速度