一致性哈希算法的理解与实践

0. 概述

在维基百科中,是这么定义的

一致哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量, n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

1. 引出

我们在上文中已经介绍了一致性Hash算法的基本优势,我们看到了该算法主要解决的问题是:当slot数发生变化时,能够尽量少的移动数据。那么,我们思考一下,普通的Hash算法是如何实现?又存在什么问题呢?
那么我们引出一个问题:

假设有1000w个数据项,100个存储节点,请设计一种算法合理地将他们存储在这些节点上。

看一看普通Hash算法的原理:
normal_hash
算法的核心计算如下

1
2
3
4
5
6
for item in range(ITEMS):
k = md5(str(item)).digest()
h = unpack_from(">I", k)[0]
# 通过取余的方式进行映射
n = h % NODES
node_stat[n] += 1

具体的完整实现请参考normal_hash.py,输出是这样的:

Ave: 100000
Max: 100695 (0.69%)
Min: 99073 (0.93%)

从上述结果可以发现,普通的Hash算法均匀地将这些数据项打散到了这些节点上,并且分布最少和最多的存储节点数据项数目小于1%。之所以分布均匀,主要是依赖Hash算法(实现使用的MD5算法)能够比较随机的分布。

然而,我们看看存在一个问题,由于该算法使用节点数取余的方法,强依赖node的数目,因此,当是node数发生变化的时候,item所对应的node发生剧烈变化,而发生变化的成本就是我们需要在node数发生变化的时候,数据需要迁移,这对存储产品来说显然是不能忍的,我们观察一下增加node后,数据项移动的情况:

1
2
3
4
5
6
7
8
9
for item in range(ITEMS):
k = md5(str(item)).digest()
h = unpack_from(">I", k)[0]
# 原映射结果
n = h % NODES
# 现映射结果
n_new = h % NEW_NODES
if n_new != n:
change += 1

详细实现代码在normal_hash_add.py输出是这样的:

Change: 9900989 (99.01%)

翻译一下就是,如果有100个item,当增加一个node,之前99%的数据都需要重新移动

这显然是不能忍的,普通哈希算法的问题我们已经发现了,如何对其进行改进呢?没错,我们的一致性哈希算法闪亮登场。

2. 登场

我们上节介绍了普通Hash算法的劣势,即当node数发生变化(增加、移除)后,数据项会被重新“打散”,导致大部分数据项不能落到原来的节点上,从而导致大量数据需要迁移。

那么,一个亟待解决的问题就变成了:当node数发生变化时,如何保证尽量少引起迁移呢?即当增加或者删除节点时,对于大多数item,保证原来分配到的某个node,现在仍然应该分配到那个node,将数据迁移量的降到最低

一致性Hash算法的原理是这样的:
consist_hash

1
2
3
4
5
6
7
8
9
10
for n in range(NODES):
h = _hash(n)
ring.append(h)
ring.sort()
hash2node[h] = n

for item in range(ITEMS):
h = _hash(item)
n = bisect_left(ring, h) % NODES
node_stat[hash2node[ring[n]]] += 1

我们依然对其进行了实现consist_hash_add.py,并且观察了数据迁移的结果:

Change: 235603 (2.36%)

虽然一致性Hash算法解决了节点变化导致的数据迁移问题,但是,我们回过头来再看看数据项分布的均匀性,进行了一致性Hash算法的实现consist_hash.py

Ave: 100000
Max: 596413 (496.41%)
Min: 103 (99.90%)

这结果简直是简直了,确实非常结果差,分配的很不均匀。我们思考一下,一致性哈希算法分布不均匀的原因是什么?从最初的1000w个数据项经过一般的哈希算法的模拟来看,这些数据项“打散”后,是可以比较均匀分布的。但是引入一致性哈希算法后,为什么就不均匀呢?数据项本身的哈希值并未发生变化,变化的是判断数据项哈希应该落到哪个节点的算法变了。
consist_hash_1
因此,主要是因为这100个节点Hash后,在环上分布不均匀,导致了每个节点实际占据环上的区间大小不一造成的。

3. 改进-虚节点

当我们将node进行哈希后,这些值并没有均匀地落在环上,因此,最终会导致,这些节点所管辖的范围并不均匀,最终导致了数据分布的不均匀。
consist_hash_virtual

详细实现请见virtual_consist_hash.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for n in range(NODES):
for v in range(VNODES):
h = _hash(str(n) + str(v))
# 构造ring
ring.append(h)
# 记录hash所对应节点
hash2node[h] = n
ring.sort()

for item in range(ITEMS):
h = _hash(str(item))
# 搜索ring上最近的hash
n = bisect_left(ring, h) % (NODES*VNODES)
node_stat[hash2node[ring[n]]] += 1

输出结果是这样的:

Ave: 100000
Max: 116902 (16.90%)
Min: 9492 (90.51%)

因此,通过增加虚节点的方法,使得每个节点在环上所“管辖”更加均匀。这样就既保证了在节点变化时,尽可能小的影响数据分布的变化,而同时又保证了数据分布的均匀。也就是靠增加“节点数量”加强管辖区间的均匀。
同时,观察增加节点后数据变动情况,详细的代码请见virtual_consist_hash_add.py

1
2
3
4
5
6
for item in range(ITEMS):
h = _hash(str(item))
n = bisect_left(ring, h) % (NODES*VNODES)
n2 = bisect_left(ring2, h) % (NODES2*VNODES)
if hash2node[ring[n]] != hash2node2[ring2[n2]]:
change += 1

100000
101000
Change: 104871 (1.05%)

3. 另一种改进

然而,虚节点这种靠数量取胜的策略增加了存储这些虚节点信息所需要的空间。在OpenStack的Swift组件中,使用了一种比较特殊的方法来解决分布不均的问题,改进了这些数据分布的算法,将环上的空间均匀的映射到一个线性空间,这样,就保证分布的均匀性。
consist_hash_ring
代码实现见part_consist_hash.py

1
2
3
4
5
6
7
8
9
for part in range(2 ** LOG_NODE):
ring.append(part)
part2node[part] = part % NODES

for item in range(ITEMS):
h = _hash(item) >> PARTITION
part = bisect_left(ring, h)
n = part % NODES
node_stat[n] += 1

Ave: 100000
Max: 157298 (57.30%)
Min: 77405 (22.59%)

可以看到,数据分布是比较理想的。如果节点数刚好和分区数相等,理论上是可以均匀分布的。而观察下增加节点后的数据移动比例,代码实现见part_consist_hash.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

for part in range(2 ** LOG_NODE):
ring.append(part)
part2node[part] = part % NODES
part2node2[part] = part % NODES2

change = 0
for item in range(ITEMS):
h = _hash(item) >> PARTITION
p = bisect_left(ring, h)
p2 = bisect_left(ring, h)
n = part2node[p] % NODES
n2 = part2node2[p] % NODES2
if n2 != n:
change += 1

结果如下所示:

Change: 2190208 (21.90%)

可以看到,移动也是比较理想的。

参考链接:

深入云存储系统Swift核心组件:Ring实现原理剖析
Basic Hash Ring
Partition Ring vs. Hash Ring

理解Python中的“with”

1. 缘起

Python中,打开文件的操作是非常常见的,也是非常方便的,那么如何优雅的打开一个文件?大部分的同学会这样实现:

1
2
with open( "a.txt" ) as f :
# do something

大家都知道,这样写可以自动处理资源的释放、处理异常等,化简了我们打开文件的操作,那么,with到底做了什么呢?

从《Python学习手册》中是这么描述的:

简而言之,with/as语句的设计是作为常见try/finally用法模式的替代方案。就像try/finally语句,with/as语句也是用于定义必须执行的终止或“清理”行为,无论步骤中是否发生异常。不过,和try/finally不同的是,with语句支持更丰富的基于对象的协议,可以为代码块定义支持进入和离开动作。

也就是说对于代码:

1
2
with expression [as varible]:
with-block

with语句的实际工作方式:

1.计算表达式,所得到的对象是环境管理器,他必须有enterexit两个方法。
2.环境管理器的enter方法会被调用。如果as存在,enter的返回值赋值给as后面的变量,否则,被丢弃。
3.代码块中嵌套的代码(with-block)会执行。
4.如果with代码块会引发异常,exit(type,value,traceback)方法就会被调用。这些也是由sys.exec_info返回相同的值。如果此方法返回为假,则异常会重新引发。否则,异常会中止。正常情况下异常是应该被重新引发,这样的话传递到with语句外。
5.如果with代码块没有引发异常,exit方法依然会调用,其type、value以及traceback参数会以None传递。

with/as语句的设计,是为了让必须在程序代码块周围发生的启动和终止活动一定会发生。和try/finally语句(无论异常是否发生其离开动作都会执行)类似,但是with/as有更丰富的对象协议,可以定义进入和离开的动作。

2. 设计的初衷

with/as语句的设计的初衷,在PEP343中是这么描述的:

This PEP adds a new statement “with” to the Python language to make it possible to factor out standard uses of try/finally statements.
In this PEP, context managers provide enter() and exit() methods that are invoked on entry to and exit from the body of the with statement.

对于下面的操作:

1
2
with EXPR as VAR:
BLOCK

等价于

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
mgr = (EXPR)
exit = type(mgr).__exit__ # Not calling it yet
value = type(mgr).__enter__(mgr)
exc = True
try:
try:
# 将__enter__函数调用的返回值返回给VAR
VAR = value # Only if "as VAR" is present
# 执行BLOCK
BLOCK
except:
# 异常处理,The exceptional case is handled here
exc = False
if not exit(mgr, *sys.exc_info()):
raise
# The exception is swallowed if exit() returns true
finally:
# 清理,The normal and non-local-goto cases are handled here
if exc:
exit(mgr, None, None, None)

我们可以看到上述代码完整的处理了初始化及异常/正常场景的清理操作,这便是with的设计思想,化简了冗余的代码,把那些重复的工作以及异常处理操作交给写“EXPR”源码(比如open操作)的同学。

3. 更深入的学习

我们继续深入的看下Python3enterexit的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
class IOBase(metaclass=abc.ABCMeta):
# ... ...

### Context manager ###

def __enter__(self): # That's a forward reference
"""Context management protocol. Returns self (an instance of IOBase)."""
self._checkClosed()
return self

def __exit__(self, *args):
"""Context management protocol. Calls close()"""
self.close()

和我们预期的一致,在enter中返回了这个IO对象,然后在exit中,进行了清理。

参考资料

  1. 《Python学习手册》
  2. Understanding Python’s “with” statement
  3. PEP 343 — The “with” Statement
  4. Catching an exception while using a Python ‘with’ statement
  5. 理解Python中的with…as…语法
  6. PEP 3116 — New I/O
  7. Python 3.5.0 Code

存储数据包的一生

最近认认真真学习了一个叫《Life of a Storage Packet》讲座,借助这个讲座将整个存储的过程理解了下,不放过任何一个有疑问的点。这篇文章算是对讲座的理解和自己收获的总结,同时也为那些对存储系统不够了解又想要了解的初学者,展现一个存储数据包的“生命”。这个演讲主要聚焦在“整体的存储”,强调存储系统中各个基本元素的关系,并且尽可能简单、清楚地用一种不同的方式可视化一些存储的概念。

先上一张大图,可以说这篇文章目的就是解释这个图:
12

OpenStack源码分析-挂载卷流程

1. 挂卷流程

volume attach
当Nova volume-attach server volume执行后,主要经过以下几步:
a. Nova Client解析指令,通过RESTFUL接口访问nova-api;
b. Nova API解析响应请求获取虚拟机的基本信息,然后向cinder-api发出请求保留,并向nova-compute发送RPC异步调用请求卷挂载;
c. Nova-compute向cinder-api初始化信息,并根据初始化连接调用Libvirt的接口完成挂卷流程;
d. 进而调用cinder-volume获取连接,获取了连接后,通过RESTFUL请求cinder-api进行数据库更新操作。

优雅地调试OpenStack

恩,题目首先要起的高逼格一些。2333。

在前面学习代码的过程中,主要通过源码来学习,开始学起来确实有点费劲,因为欠缺对OpenStack的整体的意识,于是搭建OpenStack开发环境对OpenStack的运行环境和使用有了初步认知。也看到了启动OpenStack后的一些相关进程,那么这些进程是如何与源码对应起来的呢?如何去调试OpenStack呢?本篇文章就讲下我的探索。

OpenStack源码分析-Cinder删除卷流程

1. Cinder删除卷整体流程

delete

删除卷流程比较简单,主要就是cinder-api解析Cilent的指令,并响应,发送RPC调用cinder-volume的delete操作,详细流程如下:
a. Client发送删除指令,通过RESTful接口访问cinder-api;
b. Cinder-api解析响应请求,通过RPC调用cinder-volume;
c. Cinder-volume通过调用Driver的delete函数进行删除。

2. 源码详解

cinder delete

2.1 Cinder API

(1) Cinder\api\v2\volumes.py
VolumeController的delete函数响应请求,首先从API获取Volume对象信息,然后,调用API的delete对对象进行删除;
(2) Cinder\volume\api.py
API.delete的对卷的状态进行检查,并更新状态为“deleting”,然后调用rpcapi的delete_volume函数

2.2 Cinder Volume

(1) Cinder\volume\rpcapi.py
VolumeAPI函数投递一个远程消息,通过消息队列远程调用cinder volume的delete_volume函数。
(2) Cinder\volume\manager
最终通过VolumeManager调用dirver的delete_volume对卷进行删除。

OpenStack源码分析-Cinder创建卷流程

1. Cinder创卷整体流程

create

如整体架构图所示,创建卷涉及的答题步骤主要有以下几步:
a. Client发送请求,通过RESTFUL接口访问cinder-api。
b. Api解析响应请求,api解析由Client发送来的请求,并通过rpc进一步调用cinder-scheduler。
c. Scheduler对资源进行调度,scheduler选择合适的节点进行。
d. Volume调用Driver创建卷,volume通过指定Driver进行卷的创建。

2. 源码详解

代码的整体流程如下所示:
cinder seq
从上图可以看出,整体处理流程包括三大部分,分别是API、Scheduler、Volume三部分。

2.1 Cinder API部分

create_api

(1) cinder\api\v2\volumes.py
VolumeController. create函数对创建请求进行响应,首先函数对volume_type、metadata、snapshot等信息进行检查,然后调用Volume API的create进行创建。
(2) cinder\volume\api.py
API.create函数对source_volume、volume_type等参数进行进一步检查,并调用cinder.volume.flows.api.get_flow来创建。
(3) cinder\volume\flows\api\create_volume.py
get_flow函数检查Quata,最后创建EntryCreateTask及VolumeCastTask等任务,
其中EntryCreateTask会将卷的创建过程写入数据库,此时卷的状态为”creating”。
VolumeCastTask.excute函数会调用VoumeCastTask._cast_create_volume
VolumeCastTask._cast_create_volume函数,如果未传入host,则会经过调度进行创建卷,通过scheduler_rpcapi.create_volume创建卷;如果未传入host则直接交由Volume Manager去创建卷。

至此为止,Cinder API部分完成了自己的工作。

2.2 Cinder Scheduler

create_sche

(1) cinder\scheduler\rpcapi.py(此步还属于cinder-api)
SchedulerAPI.create_volume函数会通过消息异步调用SchedulerManager.create_volume函数。
(2) cinder\scheduler\manager.py
SchedulerManager.create_volume函数,使用自己的flow来创建volume,其中还传入了Driver。
(3) cinder\scheduler\flows\create_volume.py
get_flow函数,创建ScheduleCreateVolumeTask
ScheduleCreateVolumeTask.execute函数,会调用driver_api.schedule_create_volume
(4) cinder\scheduler\filter_scheduler.py
FilterScheduler. schedule_create_volume函数,更新数据库,最后通过消息队列请求调用volume_rpcapi.create_volume。

2.3 Cinder Volume

create_volume
(1) /cinder/volume/rpcapi.py(此步还属于cinder-scheduler)
VolumeAPI.create_volume会通过消息队列远程调用VolumeManager.create_volume
(2) /cinder/volume/manager.py
VolumeManager函数也使用flow来创建volume,执行CreateVolumeFromSpecTask这个任务
(3) /cinder/volume/flows/manager/create_volume.py
CreateVolumeFromSpecTask.excute,这个函数会根据创建的不同类别,去创建卷,例如调用create_raw_volume,最终会调用具体的driver进行卷的创建。
在完成创卷后,CreateVolumeOnFinishTask这个任务,启动更新数据库,将卷更新为available状态。

我们可以看到在创建卷的过程中盘的状态会从“creating”状态变为“available”状态。