3大经典分布式存储算法-创新互联
文章目录
网页标题:3大经典分布式存储算法-创新互联
标题路径:http://scyanting.com/article/cdcoih.html
- 1、背景
- 2、算法
- 2.1 分布存储之哈希取余算法
- 2.2 分布式存储之一致性哈希算法
- 2.3 分布式存储之哈希槽算法
一个经典的面试题目:1~2亿条数据需要缓存,请问如何设计这个方案?
回答:单台单机肯定不可能,需要使用分布存储
- 是什么?
一致性哈希算法背景是在1997年由麻省理工学院提出的,设计目标是为了解决分布式存储数据变动和映射问题,某个机器宕机了,分母数量改变了,自然取余数就不OK了。 - 能干嘛?
提出一致性hash算法解决方案目的就是当服务器个数发生变动时,尽量减少影响客户端到服务器的映射关系。 - 3大步骤⭐️
- 算法构建一致性哈希环
一致性hash算法必然有个hash函数并按照算法产生hash值,这个算法的所有可能哈希值会构成一个全量集,这个集合可以成为一个hash空间[0,2^32-1],这是一个线性空间,但是在算法中,我们通过适当的逻辑将它首尾相连,这样让他构成一个环形空间。它也是按照使用取模的方法,前面笔记介绍的节点取模法是对节点(服务器)的数量进行取模。而一致性Hash算法是对2^32取模,简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0~2^32-1(即哈希值是一个32位无符号整型),整个哈希环如下图:整个空间按顺时针方向组织,圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4…直到232-1,也就是0点左侧的第一个点代表232-1,0和232-1在零点中方向重合,我们把这个由232个点组成的圆环称为Hash环。
- 算法构建一致性哈希环
- 服务器IP节点映射
将集群中各个IP映射到环上的某一个某一位置。将各个服务器使用Hash进行一个哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,这样每一台机器就能确定其在哈希环上的位置。假如4个结点NodeA、B、C、D,经过IP地址的哈希函数计算(hash(ip)),使用IP地址哈希后在环空间的位置如下:
- 是什么?
哈希槽实质就是一个数组,数组[0,2^14-1]形成hash slot空间 - 能干什么?
解决均匀分配的问题,在数据和节点之间又加入了一层,把这层称为哈希槽(slot),用于管理数据和节点之间的关系,现在就相当于节点上放的是槽,槽里放的是数据。槽解决的是粒度问题,相当于把粒度变大,这样便于数据移动。哈希解决的是映射问题,使用key的哈希值来计算所在的槽,便于数据分配。 - 有多少个hash槽?
一个集群只能有16384个槽,编号0-16383。这些槽会分配给集群中的所有主节点,分配策略没有要求。可以指定哪些编号的槽分配给哪些主节点。集群会记录节点和槽的对应关系。解决了节点和槽的关系后,接下来就需要对key求哈希值,然后对16384取余,余数是几key就落入对应的槽里。slot=CRC16(key)%16384。以槽为单位移动数据,因为槽的数目是固定的,处理起来比较容器,这样数据移动问题就解决了。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页标题:3大经典分布式存储算法-创新互联
标题路径:http://scyanting.com/article/cdcoih.html