MapReduce 阅读纪要

paper: https://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf

MapReduce 指一个由 Google 提出的,用于在集群上使用并行、分布式算法处理大规模数据的编程模型,以及一系列相关实现。本文是我阅读 Google 原论文之后的一些纪要。

MapReduce 模型

在 lisp 以及许多其它函数式语言中,常常存在用于处理顺序表数据结构的 mapreduce 等原语。在本质上,它们是能够以一个顺序表及处理函数为参数的高阶函数

map 将一一以顺序表中的元素为参数调用这个处理函数,并以这些调用返回的结果作为元素形成一个新的顺序表。也就是说,这个处理函数将作用于原顺序表中的每一个元素。以 python 为例:

1
2
3
4
# square
>>> result = map(lambda x: x * x, [1, 2, 3, 4, 5])
>>> list(result)
[1, 4, 9, 16, 25]

reduce 同样将遍历顺序表,但它以前一次处理函数返回的结果,以及当前元素为参数递归的调用处理函数:

1
2
3
# sum
>>> reduce(lambda a, b: a + b, [1, 2, 3, 4, 5])
15

Google 受这些原语所启发,发现大多数现实世界的分布式作业拥有与其相似的特征。例如,我们可以以这样的方式来统计一大堆文档集合里的词频:

1
2
3
4
5
6
def map(key: string, value: string):
for word in value:
emit(word, "1")

def reduce(key: string, values: Iterator):
emit(string(len(values)))

在这里,map 常常接受文件名和内容作为参数,返回一系列键值对。reduce 以键名和其相关的一系列值为参数,返回最终的结果。在上面的例子中,map 将读取文档内容,然后返回形位 word: "1" 形式的键值对。MapReduce 实现会将键名相同的值集合在一起,传递给 reduce 函数。而 reduce 函数则简单统计了键对应值的数量。

在单处理器环境中以这种模型运行,不一定会获得比通常方式更高的效率。然而,正如文章开始所说的那样,MapReduce 应用于分布式计算。在实践中,这种受限的模型,能够让框架方便地将任务分布式化,并自动处理诸如数据划分、容错、负载均衡等任务。

MapReduce 模型中的 Map,是由用户指定的函数。Map 接收一个 key/value pair 值,并且产生一系列中间 key/value pair 值。MapReduce 库将拥有相同 key 值的 pair 聚合在一起并传给 Reduce 函数。

Reduce 同样由用户定义。它接受一个 key 以及一系列相关的 value,形成更小的 value 集合。典型地一个 Reduce 调用产生零个或一个 value 值。

通过将输入数据自动划分为 M 个片段,Map 在多台机器上被分布式地调用。通过将 Map 产生的结果划分为 R 份,Reduce 也能在多台机器上调用。R 的数量和划分函数通常是由用户指定的。

MapReduce 模型的典型执行流程如下:

  1. 一开始,用户程序中的 MapReduce 库将输入文件划分为 M 段。段的大小可配置,通常为 64M。然后,用户程序在集群机器中创建程序的副本。
  2. 其中一个副本被指定为 master。其余的都是由 master 分配任务的 workers。这里有 M 个 Map 任务,以及 R 个 Reduce 任务可以分配。 master 将选择一个空闲的 worker 分配任务。
  3. 被指定了 map 任务的 worker 将读取响应的输入的划分。它从输入中解析出 key/value pair,然后传递给用户定义的 Map 函数,将产生的中间 key/value pair 缓存在内存中。
  4. 缓存的数据周期性地写入本地磁盘,由划分函数划分为 R 个区域。这些区域地位置将发送给 master,以被 master 转发给 reduce work。
  5. 所有的 map 任务完成后,master 开始分配 reduce 任务。master 将对应的地址传送给 reduce worker。reduce worker 通过远程过程调用读取这些区域的内容。读取完之后,reduce work 通过键将这些内容排序。然后将拥有相同的 key 的 values 传递给用户定义的 Reduce 函数。Reduce 函数的输出将会被追加到分区对应的文件中。
  6. reduce 任务完成后,返回用户调用 MapReduce 过程的地方,继续执行用户接下来的程序。

容错处理

Worker 错误

master 会周期性地 ping 每一个 worker,如果在一段时间之内,一个 worker 都没有响应,那么 master 会认为这个 worker 发生了错误。如果这个 worker 执行的是 map 任务,那么这个 worker 执行过的所有任务都将被 master 安排在其它 worker 上重新执行。如果执行的是 reduce 任务,那么当前执行的任务会被安排在其它 worker 上重新执行。

之所以要重新执行失败 map worker 上的所有任务,是因为 map worker 产生的输出是保存在本地磁盘上的,一旦失败则无法读取。而 reduce worder 的输出保存在全局文件系统上,失败只需要重新执行当前任务即可。

Master 错误

周期地将 master 保存地数据结构保存为 checkpoint 存入磁盘。一旦 master 发生错误,就从最近保存的 checkpoint 中恢复。

失效处理机制

当用户定义的 Map 和 Reduce 是确定性的时,MapReduce 的输入输出和在程序串行、没有出现错误的情况下执行的输入输出是一致的。MapReduce 通过自身文件系统的原子性操作保证这一点成立。
值得注意的是,MapReduce 的错误处理都假设在 fail-stop 上,由于硬件或软件原因的结果错误无法处理。

优化

储存位置

网络容易成为整个系统的限制。因此,MapReduce 可以构建于一个分布式文件系统(例如: gfs)之上。在分配任务时,MapReduce 从文件系统之中读取各个文件储存的位置,然后让 map worker 读取最近的输入,从而降低对网络的要求。

任务细度

为了更好的负载均衡和容错策略,通常使 M 和 R 为 worker 数量的几倍。

备份任务

实践表明,大部分 worker 都执行完毕的情况下,仍然在执行的几个 worker 可能由于机器的软硬件因素仍然要执行很长时间。因此,MapReduce 会自动将最后几个任务备份到多个 worker 上执行。以先完成的为结果。

技巧

划分函数

默认情况下,通常通过哈希来划分输入。然而,如果用户有某些特别需求可以自定义划分函数。

保证排序

传递给 Reduce 函数的 values 是经过排序的。

合并函数

可以给 Map 提供一个合并函数。这个合并函数通常和 Reduce 函数一样,在 Map 完成之后本地调用,以减少最终需要网络传输的数据数量。

跳过坏任务

可能由于用户代码或某些第三方库的原因,一些任务的执行将始终失败。worker 在失败时会发送一条消息给 master。master 会记住任务失败的次数。如果次数太多,会跳过这个任务的执行。

Flask 源码的二三事

本文将基于 Flask 1.1.dev ( a74864 ),分析 Flask 源码之中一些有趣并且值得关注的部分,包括 路由机制、请求流程、上下文管理 等等。

路由机制

本节关注 Flask 的路由机制。首先还是先看下 Flask 的 hello world:

1
2
3
4
5
6
from flask import Flask
app = Flask(__name__)

@app.route("/")
def hello():
return "Hello World!"

跟进 route 方法:

1
2
3
4
5
6
def route(self, rule, **options):
def decorator(f):
endpoint = options.pop('endpoint', None)
self.add_url_rule(rule, endpoint, f, **options)
return f
return decorator

可见 route 方法实际上根据给定的参数另外调用了 add_url_rule:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def add_url_rule(self, rule, endpoint=None, view_func=None,
provide_automatic_options=None, **options):
if endpoint is None:
endpoint = view_func.__name__
options['endpoint'] = endpoint
methods = options.pop('methods', None)

...

rule = self.url_rule_class(rule, methods=methods, **options)

self.url_map.add(rule)
# self.view_functions = {}
self.view_functions[endpoint] = view_func

添加路由的逻辑最终由 add_url_rule 这个方法实现。它的参数里 rule 就是要匹配 url 的模式,endpoint 是这个视图的端点名,view_func 是我们定义的函数。默认情况下,endpoint 为函数的名字。我们根据这些信息调用了 self.url_rule_class 方法,并用其返回值作为参数调用了 self.url_map.add。最后,将 endpoint 作为键,我们定义的函数作为值,添加进了 self.view_functions 字典。

这里 self.url_rule_class 和 self.url_map 是什么呢?

1
2
3
4
5
6
7
8
from werkzeug.routing import Map, Rule

class Flask:
url_rule_class = Rule

def __init__(...):
self.url_map = Map()
...

可见,Flask 路由机制的核心是 Map 和 Rule 类,而这两个类都来自 Flask 高度依赖的 werkzeug 包。因此,想要明白 Flask 路由的原理,首先我们必须对 werkzeug 有一定了解。这里我们先看下 Map 和 Rule 的简单用法:

1
2
3
4
5
6
7
8
9
10
11
12
13
# 来自 werkzeug docs
url_map = Map()
url_map.add(
Rule('/<id>', endpoint='user')
)

def dispatch_request(self, request):
adapter = self.url_map.bind_to_environ(request.environ)
try:
endpoint, values = adapter.match()
return getattr(self, 'on_' + endpoint)(request, **values)
except HTTPException, e:
return e

这里的 request.environ 中的 evniron 是 wsgi 应用中传入 __call__ 方法的一个参数。

调用 Map.bind_to_environ,根据给定请求的 environ 字典,生成了一个 URLAdapter。然后,调用 adapter 上的 match 方法,就能够得到此次请求对应的端点名和对应 url 的参数。比如说,如果此次请求是 http://localhost:5000/foo,那么返回的 endpoint 和 values 就为:

1
2
endpoint == 'user'
values == {"id": "foo"}

可见,这里 Rule 对应的是每一条之后需要匹配的 url 规则,Map 将这些规则收集起来,对应这些规则的映射。之后,当有请求来的时候,就绑定 environ 生成 adapter,并调用 match 得到匹配的端点和参数。

现在我们返回 Flask。前面我们在 Flask 应用的初始化过程中生成了 Map 的一个实例。之后的每一次使用 route,在默认情况下把函数名作为 endpoint,生成一个新的 Rule 对象。并将它添加进 Map 实例中。最后将 endpoint 和函数本身作为键值添加进字典。

Map 是通过遍历 Rule,并一一匹配正则表达式来匹配路由的。这点目前不详细叙述,日后在另一篇文章中讲下吧。

用户方面添加路由的流程大致是这样了。下面我们从处理请求的流程中看路由机制的另一个方面。

请求流程

本节关注 Flask wsgi 应用的实现。我们查看 Flask 类的 __call__ 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Flask:
def __call__(self, environ, start_response):
return self.wsgi_app(environ, start_response)

def wsgi_app(self, environ, start_response):
...
# 生成请求上下文
ctx = self.request_context(environ)
try:
try:
# 推入上下文栈
ctx.push()
# 分发路由
response = self.full_dispatch_request()
except Exception as e:
error = e
# 处理异常
response = self.handle_exception(e)
# 最终得到包含了返回信息的 werkzeug Response 实例,调用它完成请求。
return response(environ, start_response)
finally:
# 这里 finally 语句会在 return 之前执行
# 弹出请求上下文对象
ctx.auto_pop(error)
...

这里 __call__ 方法仅仅将逻辑交给了 wsig_app 方法。这样做的一个好处在于,如果之后要为整个应用添加中间件,就不用处理整个 Flask 实例,直接替换 wsgi_app 方法即可,不用担心实例中的大量配置被丢失或覆盖:

1
2
3
4
5
6
from . import middleware, app

# 我们可以这样用:
app.wsgi_app = middleware(app.wsgi_app)
# 而不是:
app = middleware(app)

回到 wsgi_app 方法,可以看到 response 由 self.full_dispatch_request 生成:

1
2
3
4
5
6
7
def full_dispatch_request(self):
try:
rv = self.dispatch_request()
except Exception as e:
rv = self.handle_user_exception(e)
# 将视图函数返回的值转换为合法的 response
return self.finalize_request(rv)

跟进 slef.dispatch_request:

1
2
3
4
5
def dispatch_request(self):
# 得到请求上下文栈顶的 request 对象
req = _request_ctx_stack.top.request
rule = req.url_rule
return self.view_functions[rule.endpoint](**req.view_args)

注意到这里出现了上一节里面的 self.view_functions,它的键是视图的端点名,值是视图对应的函数。这里我们通过 rule.endpoint 和 req.view_args 调用了视图函数,说明此时我们已经通过请求相关的信息(environ),匹配到了对应的 url 和参数。

调用我们储存在 self.view_functions 里的视图函数得到请求的返回值以后,就将它传给了 self.finalize_request,将之转化为一个合法的响应对象后返回。

然而,这里的问题是,我们明明没有显示调用 self.url_map.bind_to_environ 与 adapter.match,是怎样从 _request_ctx_stack.top.request 里得到正确信息的呢?实际上,奥秘隐藏在 Flask 的请求上下文机制里。

请求上下文Ⅰ

用过 Flask 的同学一定对其 request 对象映像深刻。不像 django 等框架,在每个视图函数里,都需要传入一个 request 参数,在 Flask 中,可以直接使用从全局导入的 request 对象:

1
2
3
4
5
6
7
8
from flask import request

from . import app

@app.route('/show')
def show():
print(request.environ)
return 'ok'

request 自动适配每一个来到的请求。我们看看 request 的真面目:

1
2
3
4
5
6
7
8
9
10
11
from functools import partial
from werkzeug.local import LocalStack, LocalProxy

def _lookup_req_object(name):
top = _request_ctx_stack.top
if top is None:
raise RuntimeError(_request_ctx_err_msg)
return getattr(top, name)

_request_ctx_stack = LocalStack()
request = LocalProxy(partial(_lookup_req_object, 'request'))

这里一时间让我们不明所以。我们看到 _request_ctx_stack 原来是 werkzeug 中 LocalStack 的实例(注意 _request_ctx_stack 在上一节 dispatch_request 中出现过),request 是 LocalProxy 的实例。

LocalStack

为了理解这一段代码,我们需要先了解 LocalStack 的用法。简单来说,这里的 LocalStack 类似于 线程本地变量,在一个的线程中修改它的值,对于其它线程来说是透明的。更具体的说,这里的 LocalStack 是一个 线程本地栈,在一个线程中给这个栈推入或弹出值,并不会影响其它线程中的 LocalStack。

LocalStack 的实现依赖于 werkzeug 中的 Local 类,我们先查看 Local 类的源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from thread import get_ident

class Local(object):
# 实例中只能修改 __storage__ 和 __ident_func__ 这两个属性
# 节省内存空间
__slots__ = ('__storage__', '__ident_func__')

def __init__(self):
# 因为本类已经有了 __setattr__ 方法,为了避免循环调用
# 直接从 object.__setattr__ 给它的属性设置值
object.__setattr__(self, '__storage__', {})
# get_ident 得到每个线程的唯一 id
object.__setattr__(self, '__ident_func__', get_ident)

def __release_local__(self):
# 释放线程本地变量
self.__storage__.pop(self.__ident_func__(), None)

def __getattr__(self, name):
try:
# self.__ident__func 获取线程 id
# 得到 __storage__ 字典里对应本线程字典中键为 name 的值
return self.__storage__[self.__ident_func__()][name]
except KeyError:
raise AttributeError(name)

def __setattr__(self, name, value):
"""
在这个实例上设置属性,会将它储存在本线程对应的字典里
"""
# 线程 id
ident = self.__ident_func__()
storage = self.__storage__
try:
storage[ident][name] = value
except KeyError:
storage[ident] = {name: value}

def __delattr__(self, name):
"""
删除一个属性,删除本线程对应字典里的值
"""
try:
del self.__storage__[self.__ident_func__()][name]
except KeyError:
raise AttributeError(name)

Local 类的实例是一个线程本地变量。它在内部维护了一个 __storage__ 字典,这个字典的键为各线程的 id,值为字典,储存对应线程上设置的值。它通过 __setattr__ 等特殊方法,将属性访问转发给内部的 __storage__ 字典。这样,对于不同的线程,Local 的实例上储存的值是不同的。

注意到 Local 类中有一个 __slots__ 属性。这是一个特殊属性,拥有它的类的实例上不会有 __dict__ 字典,从而节省了内存空间。文档中说:

The __slots__ declaration takes a sequence of instance variables and reserves just enough space in each instance to hold a value for each variable. Space is saved because __dict__ is not created for each instance.

相应的,拥有 __slots__ 的类,其实例也不被允许赋予 __slots__ 中规定外的属性。

还是让我们继续看 LocalStack 的源码吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class LocalStack(object):
def __init__(self):
# 保存了上面 Local 的实例,一个线程本地变量。
self._local = Local()

def __release_local__(self):
# 释放内部的线程本地变量
self._local.__release_local__()

def push(self, obj):
"""Pushes a new item to the stack"""
rv = getattr(self._local, 'stack', None)
if rv is None:
# self._local 是线程本地变量。储存在它上面的属性会储存在其内部的 __storage__ 字典中
# 这样,对于不同的线程来说,self._local.stack 这个栈也是不同的
self._local.stack = rv = []
rv.append(obj)
return rv

def pop(self):
"""Removes the topmost item from the stack, will return the
old value or `None` if the stack was already empty.
"""
stack = getattr(self._local, 'stack', None)
if stack is None:
return None
elif len(stack) == 1:
# 如果 stack 只剩最后一个,为节省内存,将内部的字典释放
self.__release_local__()
return stack[-1]
else:
# 否则弹出栈顶
return stack.pop()

@property
def top(self):
"""The topmost item on the stack. If the stack is empty,
`None` is returned.
"""
try:
return self._local.stack[-1]
except (AttributeError, IndexError):
# 如果栈中还没有元素,不报错而是返回 None
return None

结合前面的 LocalStack 看,Local 的用法就很明显了。它使用前面的线程本地变量,模仿了一个线程本地栈。与实际的栈不同的地方还在于,当栈为空时,不弹出异常,而是返回 None。同时,当弹出栈最后一个元素时,线程本地变量中维护的本地的字典将会被提前释放以节省内存空间。

现在我们了解 LocalStack 了,我们可以发现 _request_ctx_stack 实际上就是 LocalStack 的实例,一个线程本地栈。实际上,_request_ctx_stack 就是 Flask 中至关重要的请求上下文栈。当然,现在它仍然空空如也,只有当有也新的请求进入时,服务器会新建一个线程,然后使用上一节中的ctx.push()推入新的请求上下文。

LocalProxy

然而我们这里仍然没触及到我们最感兴趣的 request,它还与 LocalProxy 类相关:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class LocalProxy(object):
# 节省内存
__slots__ = ('__local', '__dict__', '__name__', '__wrapped__')

def __init__(self, local, name=None):
# 它本身有 __setattr__,避免循环调用
object.__setattr__(self, '_LocalProxy__local', local)
object.__setattr__(self, '__name__', name)

def _get_current_object(self):
if not hasattr(self.__local, '__release_local__'):
# 如果不是线程本地变量,作为函数调用并返回。
# 例如,前面的 request ,传入的参数就不是直接的线程本地变量,而是一个
# partial 了的函数
return self.__local()
try:
return getattr(self.__local, self.__name__)
except AttributeError:
raise RuntimeError('no object bound to %s' % self.__name__)

@property
def __dict__(self):
try:
# 转发给它代理的线程本地变量
return self._get_current_object().__dict__
except RuntimeError:
raise AttributeError('__dict__')

def __bool__(self):
try:
# 转发给它代理的线程本地变量
return bool(self._get_current_object())
except RuntimeError:
return False

# 它还有许多与上面两个方法相似的代理
...

LocalProxy 是一个有意思的类,结合前面我们给出的 request = LocalProxy(partial(_lookup_req_object, 'request')) 语句就会更有意思。它接受一个线程本地变量,然后将对它的实例的几乎所有访问,都会转发给那个线程本地变量上的指定属性。并且在那个属性不存在时弹出 RuntimeError 异常。

注意到它的 __init__ 方法中的 object.__setattr__(self, '_LocalProxy__local', local)语句。这里使用 object.__setattr__ 是为了避免循环调用,因为它自己也实现了 __setattr__ 方法(并将它转发给线程本地变量上的属性)。这里使用了 _LocalProxy__local 这个名称,然而在之后却直接以 __local 访问。这是因为 __local 是一个双下划线方法,在自身以外的类访问时,会被重命名。

前面我们提到过,__slots__ 特殊属性会删除实例的 __dict__ 字典,并以恒定空间储存实例属性,以节省内存。然而这里在 __slots__ 中,又加回了 __dict__ 方法。本来因为 __slots__ 的原因,将要删除的字典,这里又额外添加进来,这是不是有几分做无用功的意味?

实际上,这也是为了节省内存而做的努力。这里必须存在 __dict__ 原因,是因为 LocalProxy 也会将对自身的属性访问转发给其代理的对象,因此必须允许对 __dict__ 的访问。我们已经为了节省内存,在 __slots__ 中设定了 __local、__name__ 等属性,这样,这些属性将会被存放在固定的空间中而非 __dict__。然而,没有 __dict__,尝试对实例其它属性赋值时,就会直接引起 AttributeError,使得我们无法对其作转发。因此,我们为其添加 __dict__ 属性以重新允许对实例属性的赋值。当然,此时所有属性的赋值实际会被转发给其代理对象。

值得注意的是,即使重新规定了 __dict__,当对实例属性赋值时,规定在 __slots__ 中的其它属性,仍会被储存在固定空间而非 __dict__ 字典,从而 LocalProxy 实例上的 __dict__ 字典实际会一直为空。对线程本地变量的代理,以及 __slots__ 属性的优先级,两者一起使得实例虽然有 __dict__ 属性,却不会浪费使 __slots__ 失效的更多空间。

好,关于它的 __slots__ 的问题到此为止。我们需要知道这个类会将访问转发给线程本地变量上的一个属性。对于我们的 request 而言,我们传入了 partial(_lookup_req_object, 'request') 作为参数生成它。这里我们回顾一下 _lookup_req_object 的源码:

1
2
3
4
5
def _lookup_req_object(name):
top = _request_ctx_stack.top
if top is None:
raise RuntimeError(_request_ctx_err_msg)
return getattr(top, name)

它会查看栈顶是否有请求上下文,如果有,就返回想要的属性,否则弹出异常。结合 LocalProxy ,可以看出,实际上,request一直是请求上下文栈顶的对象的”request”属性。并且这个 request 对于各个请求来说是独立的。当请求上下文为空时,会弹出 RuntimeError。

请求上下文Ⅱ

现在我们了解到 request 是 _request_ctx_stack 这个请求上下文栈的栈顶对象里面的 “request” 属性,但实际上虽然我们知晓了请求上下文栈的存在,却还不了解具体在这个上下文栈中储存了什么对象,因而不能理解它的实质。为了了解 request 的实质,我们回顾前面的请求流程。

前面提到过,Flask 也以 wsgi 的应用呈现。最后,Flask 的 app 实例会暴露出一个 __call__ 方法,给应用服务器访问。应用服务器会给 __call__ 方法传入代表请求上下文信息的 environ 字典,以及一个设置 response header 和 status 的 start_response 回调函数。

Flask 将 __call__ 方法转发给 wsgi_app 方法。注意到 wsig_app 方法中的 ctx = self.request_context(environ) 语句,以及之后的 ctx.push() 和最后的 ctx.auto_pop(error) 语句。实际上,就是这些语句将我们需要的对象都推入到了请求上下文栈中。

我们查看 self.request_context 的源码:

1
2
3
4
from .ctx import RequestContext

def request_context(self, environ):
return RequestContext(self, environ)

跟进 RequestContext:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class RequestContext(object):
def __init__(self, app, environ, request=None, session=None):
self.app = app
if request is None:
request = app.request_class(environ)
self.request = request
self.url_adapter = None
self.url_adapter = app.create_url_adapter(self.request)

...

if self.url_adapter is not None:
self.match_request()
...

默认情况下,又回调了 app 实例中的 app.request_class 和 app.create_url_adapter 。先看 app.request_class:

1
2
3
4
from .wrappers import Request

class Flask:
request_class = Request

这里的 Request 对象主要是 Flask 对于 werkzeug 里面 RequestBase 对象的封装。它接受一个 environ 字典,将储存在 environ 字典中的原始信息以各种方式封装后方便用户访问。

更重要的是 app.create_url_adapter:

1
2
3
4
def create_url_adapter(self, request):
...
return self.url_map.bind_to_environ(
request.environ)

饶了一个大圈子之后这里我们终于又回到了第一节路由机制里面的 self.url_map 对象。它是 werkzeug 里 Map 类的实例。根据我们前面介绍过的用法,这里绑定 environ 信息后会返回一个 adapter,调用 adapter 的 match 方法就能够得到匹配的端点名和参数。我们将 adapter 储存在了 RequestContext 的 url_adapter 属性中。

接下来看 RequestContext.match_request:

1
2
3
4
def match_request(self):
url_rule, self.request.view_args = \
self.url_adapter.match(return_rule=True)
self.request.url_rule = url_rule

这里终于调用了 self.url_adapter 的 match 函数。调用之后,我们就已经匹配到了分发这次请求需要的信息了。将它们储存在了 self.request.url_rule 和 self.request.view_args 中。

现在 RequestContext 已经初始化完毕了。之后在正式处理请求的 response = self.full_dispatch_request() 语句前,先调用了 ctx.push()

1
2
3
def push(self):
...
_request_ctx_stack.push(self)

这里再次出现了 _request_ctx_stack,前面分析过的线程本地栈。我们将 RequestContext 的实例推入了栈。在请求结束之后,我们又会调用 ctx.auto_pop 把这个实例弹出栈。

现在我们能够了解我们从全局导入的 reqeust 对象的实质了。它就是 Flask.wrappers 中 Request 类的实例,绑定在 RequestContext 的实例上。在每一次请求中,都会新建一个请求上下文对象 RequestContext,在它的初始化过程中,会调用绑定在 app 上的 werkzeug 里的 Map 实例 url_map 匹配 url,得到参数,将它们作为 request 的 url_rule 和 view_args 属性。然后将这个请求上下文推入请求上下文栈。我们访问到的 request 对象,就是对这个请求上下文栈顶的请求上下文里面的那个 request 的代理。这样,对于每个不同的线程而言,这个 request 对象也就自动包含了相应的请求信息。

比如说,前面的 dispatch_request 中出现过这样的语句 return self.view_functions[rule.endpoint](**req.view_args),这里的 rule.endpoint 和 req.view_args 就是从绑定完毕后的 request 对象里面获取的。

关于请求上下文,还有一点值得琢磨。每一次请求都会新建一个线程,这样,在一次请求的整个流程中,明明只需要将这个线程对应的请求上下文推入一次即可,为什么要用栈来实现请求上下文呢?这一点 Flask 的源码中曾经提到过:

Because the contexts are stacks, other contexts may be pushed to change the proxies during a request. While this is not a common pattern, it can be used in advanced applications to, for example, do internal redirects or chain different applications together.

这样做是为了能够在多个不同的应用之间做内部重定向。虽然如此,Flask 尚没有提供与此相关的 api,可能为了以后保留的。在绝大多数的开发中,实际上请求上下文栈一直只会有最多一个上下文对象。

应用上下文

除了请求上下文之外,Flask 还存在应用上下文的概念。应用上下文随线程中第一次请求上下文的推入而创建,在前面的 ctx.push 方法中:

1
2
3
4
5
6
7
def push(self):
...
app_ctx = _app_ctx_stack.top
if app_ctx is None or app_ctx.app != self.app:
app_ctx = self.app.app_context()
app_ctx.push()
...

这里的 _app_ctx_stack,应用上下文栈,原理和请求上下文栈别无二致:

1
_app_ctx_stack = LocalStack()

app_ctx.push 中,推入的是 AppContext 类的实例。这个类封装了应用的一些信息,不详细叙述了。

这里值得关注的是,为什么 Flask 除了请求上下文以外,还需要一个应用上下文的概念?在一次请求中,不是可以直接调用 RequestContext 上的 app 属性获得应用相关的信息吗?要理解这一点,需要先理解 Flask 多应用的存在。

我们可以通过 Flask 中的蓝图,将一个大的应用划分为几个子板块。但有时,这样还不够,我们需要几个子板块都拥有自己的配置信息与逻辑,成为几个单独的子系统。Flask 允许这一点,比如说,可以这样使用:

1
2
3
4
5
6
7
8
# 来自 stackoverflow
from werkzeug.wsgi import DispatcherMiddleware
from frontend_app import application as frontend
from backend_app import application as backend

application = DispatcherMiddleware(frontend, {
'/backend': backend
})

这样,在一次请求对应的一个解释器线程中,可能会同时存在多个逻辑上分割的 Flask 应用。而 Flask 请求还恰恰赋予了我们使用 url_for 这样的全局函数直接获取一个应用中端点名对应的 url,这就需要保持每个应用的上下文,需要时从应用上下文栈中获取。

Flask 就借助于应用上下文实现了 current_app 这样的全局对象,帮助我们获取此次请求对应的应用信息:

1
2
3
4
5
6
7
8
def _find_app():
top = _app_ctx_stack.top
if top is None:
raise RuntimeError(_app_ctx_err_msg)
return top.app

_app_ctx_stack = LocalStack()
current_app = LocalProxy(_find_app)

可以发现和 request 非常相似。

cpython3.7 dict 对象的内在原理

众所周知,python 中有一个应用得极其广泛内建对象——dict(字典)。cpython 解释器本身,以及大量的 python 程序,都依赖于 dict 对象。因此,dict 对象在 python 中设计得极其高效,其插入、删除、查询等操作的时间复杂度都是O(1)。

dict 对象可以这样使用:

1
2
3
4
5
6
7
8
>>> scores = {'Mike': 90, 'Jack': 100}
>>> scores['Ariana'] = 0
>>> scores['Jack']
100
>>> scores['Tim']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'Tim'

本文将从 cpython3.7 源码的角度出发,探讨 dict 对象的内部原理。主要将探讨以下几个内容:

  • dict 对象的结构、组成
  • dict 解决哈希冲突的方式
  • cpython 对 dict 的内部优化,如缓冲池、split table
  • 遍历 dict 保持插入顺序的原理

本文的剖析基于 https://github.com/python/cpython/blob/bb86bf4c4eaa30b1f5192dab9f389ce0bb61114d/Objects/dictobject.c 这份源码。

哈希表简述

cpython 采用哈希表来实现 dict(与之不同的是,c++ 采用红黑树来实现 map)。因此,想要了解 cpython 的 dict 实现,需要先对哈希表这个数据结构有所了解。

哈希表是一种实现了关联数组抽象数据类型的,键值形式的数据结构。哈希表通常利用一个哈希函数,将一个给定的键映射为一个值,这个值反映了与键对应的数据的储存位置。例如,将一个数组作为数据的储存位置,那么,哈希函数就将键映射为这个数组中键对应数据的下标。以后想要查找这个数据时,就不用从头遍历数组,而是直接哈希键取得下标,使得查询的时间由O(n)缩短到O(1)。

由于我们最终会将数据储存在一个确定大小的空间内,而待哈希的值又是源源不断的。因此,我们难以避免有多个不同的数据被哈希函数哈希到同一个数据地址的情况,这种情况就叫做发生了冲突)。衡量哈希表的冲突率的一个指标是哈希表的负载因子,它等于哈希表已使用的空间除以哈希表的总空间。直观上来说,它反映了哈希表中的一个位置平均储存的数据个数。当负载因子的值大于 2/3 时,哈希发生冲突的概率就将大大增加。因此,后面我们会看到,当 dict 中的哈希表负载因子大于 2/3 时,解释器会重新分配哈希表的大小使其负载因子小于 2/3。

我们通常使用链地址法开放寻址法来解决哈希冲突。因为链地址法会带来分配链表的开销,而 cpython 中 dict 又运用得极其普遍,因此 dict 采用开放寻址法来实现哈希表(与之不同的是,go 使用链地址法解决哈希冲突)。dict 原本的注释说:

Open addressing is preferred over chaining since the link overhead for
chaining would be substantial (100% with typical malloc overhead)

当发生哈希冲突时,dict 中的开放寻址法将会依赖哈希值使用二次探查函数生成一段探查序列,这个探查序列覆盖了整个哈希表的下标取值。

对于开放寻址法来说,当插入值发生哈希冲突时,会依照探查序列将值和键一起储存在之后的某个空位置上。当查找某个发生冲突的值时,顺着探查序列查看储存的键是否和待查找的键相同,如果最后查找到一个储存了 null 的槽,就意味着对应的键不存在于表中,指示查找结束。当删除某个发生冲突的键时,不能直接将那个槽置为 null,因为 null 指示了结束查找。因此,在删除一个值后,通常将这个槽设为 dummy,指示查找算法应该继续查找下去直到遇到一个 null。

值得注意的是,当哈希函数选择不当时,哈希值可能堆积在一起从而产生一次聚集或二次聚集的现象。这会使落在这个聚集区间内的哈希值总要探查多次才能找到正确的位置,从而极大的降低哈希的效率,特别是对于开放寻址法来说。可见,哈希函数的选择对哈希表至关重要。虽然如此,cpython 中的哈希算法独立于哈希表实现,本文将精力聚焦在 dict 实现本身上,对哈希算法暂不做更多关注。

关于哈希表的更多信息可以参阅 Hash Table

dict 的结构

PyDictKeyEntry

首先分析 dict 的数据结构。前面说过,dict 会将数据储存在一个哈希表中。这个哈希表中的元素类型,就是 PyDictKeyEntry 了:

1
2
3
4
5
6
typedef struct {
// 缓存的 key 的 hash
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictKeyEntry;

每一次向 dict 中插入一个数据,实际上就会向哈希表中插入一个 PyDictKeyEntry。PyDictKeyEntry 中不单储存了指向插入数据的指针(PyObject *me_value),还储存了这个数据对应的键(PyObject *me_key),以及键所对应的哈希(Py_hash_t me_hash)。

那么,这里的 Py_hash_t 类型是什么呢?

1
2
typedef ssize_t Py_ssize_t;
typedef Py_ssize_t Py_hash_t;

可见,Py_hash_t 实际上是 ssize_t 类型。ssize_t 类型的简介可以在这里看到。简单来说,就是一个可以为 -1 的 size_t 类型。

PyDictKeysObject

PyDictKeysObject 是 dict 中储存哈希表的结构,它的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct _dictkeysobject {
// 对这个 PyDictKeysObject 的引用
// 对于 split table,引用必须为1
Py_ssize_t dk_refcnt;

// 实际哈希表(dk_indices)的大小,其值必须为 2 的幂
Py_ssize_t dk_size;

/* typedef Py_ssize_t (*dict_lookup_func)
(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr);
*/
// Function to lookup in the hash table (dk_indices)
dict_lookup_func dk_lookup;

// dk_entries 中可用条目的数目。
// 每次插入值,dk_usable 都会减少,删除不会增加(删除使一个槽变为 dummy)
// 当 dk_usable 减少到 0,会引发哈希表内存空间的重新分配,删除其中所有 dummy
/* Number of usable entries in dk_entries. */
Py_ssize_t dk_usable;

// 每次插入,其值增加
/* Number of used entries in dk_entries. */
Py_ssize_t dk_nentries;

// 实际的哈希表,类型随哈希表的大小而变
/* Actual hash table of dk_size entries. It holds indices in dk_entries,
or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).

Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).

The size in bytes of an indice depends on dk_size:

- 1 byte if dk_size <= 0xff (char*)
- 2 bytes if dk_size <= 0xffff (int16_t*)
- 4 bytes if dk_size <= 0xffffffff (int32_t*)
- 8 bytes otherwise (int64_t*)

Dynamically sized, SIZEOF_VOID_P is minimum. */
char dk_indices[]; /* char is required to avoid strict aliasing. */

// dk_entries 不显示存在于定义里,新建 PyDictKeysObject,会分配与之对应的内存空间
/* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
see the DK_ENTRIES() macro */
};
typedef struct _dictkeysobject PyDictKeysObject;

令人疑惑的是,前面说过,PyDictKeysObject 中储存了实际的哈希表,PyDictKeyEntry 是哈希表储存数据的元素类型,然而在这里的定义里面,为什么没有见到对应的 PyDictKeyEntry 数组作为哈希表,却说char dk_indices[]是实际的哈希表呢?

这是因为,在 cpython3.7 的实现里面,对 dict 中的键值做了两重映射。cpython3.6 以前,PyDictKeysObject 储存的哈希表就是 PyDictKeyEntry* 数组,键的哈希值直接代表了数据在哈希表中的位置。从 cpython3.6 开始,PyDictKeysObject 中储存哈希表的实际类型变成了 char dk_indices[],另外用 PyDictKeyEntry 数组储存数据。dk_indices 里面储存的值不是真实数据 PyDictKeyEntry,而是它在 PyDictKeyEntry 数组里面的位置。

在 cpython3.6 以前,哈希表就是 PyDictKeyEntry 数组类型,因此每个键的哈希都映射了这个数组的位置。这样当遍历 dict 时,实际是遍历这个 PyDictKeyEntry* 哈希表,当然无法保持有序。cpython3.6 以后,每插入一个值时,实际是顺序将值插入这个额外的 PyDictKeyEntry* 数组,然后将这个值的位置储存在哈希表 dk_indices 里。这样,遍历 dict,遍历的不是哈希表 dk_indices,而是这个 PyDictKeyEntry*,而 PyDictKeyEntry* 中的数据已经是有序的。这里的 PyDictKeyEntry* 就是注释中所说的 PyDictKeyEntry dk_entries[dk_usable]。这就是 cpython3.6 以后遍历 dict 保持键插入顺序的原理。

那么为什么在 PyDictKeysObject 里面找不到对应的 dk_entries 字段呢?

首先考察 dk_indices。dk_indices 中储存的是数据的位置,因此我们必须为 dk_indices 分配足以容下这个数量的值的内存空间。考虑到实际使用中 dict 可以有不同数量的键,有时数量差距极大。因此这里使 dk_indices 的类型随哈希表的大小而变化以节约内存空间。这是解释器级别对于 dict 的优化。

dk_indices 和 dk_entries 都是可变大小的,而 c 结构体中变长的数组只能放于结构体的最后一个元素,因此这里结构体的定义中只列出了 dk_indices,实际的 dk_entries 的内存空间直接在新建时一起分配。

下面我们考察注释里面提到的 DK_ENTRIES:

1
2
3
4
5
6
7
8
9
10
11
12
#define DK_SIZE(dk) ((dk)->dk_size)

// 根据哈希表的大小,判断哈希表每个元素占据的字节大小
#define DK_IXSIZE(dk) \
(DK_SIZE(dk) <= 0xff ? \
1 : DK_SIZE(dk) <= 0xffff ? \
2 : sizeof(int32_t))

// 将 dk_indices 指针转换为int8_t,每个元素一字节。这样 DK_SIZE(dk) * DK_IXSIZE(dk)
// 就恰是 dk_entreis 相对于 dk_indices 的偏移地址
#define DK_ENTRIES(dk) \
((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))

这里 DK_SIZE 是 PyDictKeysObject 中哈希表 dk_indices 的元素个数,DK_IXSIZE 是每个元素占有的字节数(注意到这里占有的字节数随哈希表大小而变化)。现在,我们终于明白了,dk_entries 在 PyDictKeysObject 紧紧跟在 dk_indices 后面。DK_ENTRIES 宏就根据这一点动态计算出 dk_entries 的内存地址,转换类型供我们使用。

PyDictObject

最终,暴露给解释器的对象是 PyDictObject:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct {
PyObject_HEAD

// 字典中的元素个数,插入加一,删除减一
// len 即依赖这个字段
/* Number of items in the dictionary */
Py_ssize_t ma_used;

/* Dictionary version: globally unique, value change each time
the dictionary is modified */
uint64_t ma_version_tag;

PyDictKeysObject *ma_keys;

// 储存 split table 的数据
PyObject **ma_values;
} PyDictObject;

PyDictObject 有 PyObject_HEAD 宏使其可以作为 cpython 对象而使用。此外还有一个PyObject **ma_values,这个字段是为了实现 split table,共用键对象,关于这一点我们之后再做剖析。

操作哈希表

下面我们考察 dict 中是如何直接操作哈希表的。暴露给用户的 api 都是对这些直接操作哈希表的函数的封装。

读取、置位哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* lookup indices.  returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
static inline Py_ssize_t
dk_get_index(PyDictKeysObject *keys, Py_ssize_t i)
{
Py_ssize_t s = DK_SIZE(keys);
Py_ssize_t ix;

// 根据哈希表的大小,将 dk_indices 指针转换为不同类型的指针,得到其储存的数据
if (s <= 0xff) {
int8_t *indices = (int8_t*)(keys->dk_indices);
ix = indices[i];
}
else if (s <= 0xffff) {
int16_t *indices = (int16_t*)(keys->dk_indices);
ix = indices[i];
}
else {
int32_t *indices = (int32_t*)(keys->dk_indices);
ix = indices[i];
}
assert(ix >= DKIX_DUMMY);
return ix;
}

前面说过,dk_indices 是实际的哈希表,可见,dk_get_index 就是得到位置为哈希表中下标为 i 处储存的位置。

还有一个与之相关的函数:

1
2
static inline void
dk_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix)

将哈希表下标为 i 的元素设置为 ix。

查询哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#define DK_MASK(dk) (((dk)->dk_size)-1)
#define PERTURB_SHIFT 5

static Py_ssize_t
lookdict(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
{
size_t i, mask, perturb;
PyDictKeysObject *dk;
PyDictKeyEntry *ep0;

top:
dk = mp->ma_keys;
// ep0: 实际储存数据的数组
ep0 = DK_ENTRIES(dk);
// 掩码,使哈希值落入合理范围内
mask = DK_MASK(dk);
// perturb: 用于哈希冲突下的二次探查
perturb = hash;
// 初始探查位置
i = (size_t)hash & mask;

for (;;) {
Py_ssize_t ix = dk_get_index(dk, i);
if (ix == DKIX_EMPTY) {
// 对应位置没有值,指示探查结束
*value_addr = NULL;
return ix;
}
if (ix >= 0) {
// 获得 ix 位置处储存的数据
PyDictKeyEntry *ep = &ep0[ix];
assert(ep->me_key != NULL);
if (ep->me_key == key) {
// 正是此次要寻找的数据
*value_addr = ep->me_value;
return ix;
}
if (ep->me_hash == hash) {
// 键不直接相等,但哈希相等,可能是因为键是 python 对象,用 python 的比较方法
PyObject *startkey = ep->me_key;
Py_INCREF(startkey);
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp < 0) {
// 如果 cmp 小于0,表示比较过程中发生错误
*value_addr = NULL;
return DKIX_ERROR;
}
if (dk == mp->ma_keys && ep->me_key == startkey) {
// PyObject_RichCompareBool 可能会调用用户定义的特殊方法(__lt__ 之类的),这些方法可能会改变字典
// 这里通过检查 key 来判断要操作的元素是否在比较过程中被改变
if (cmp > 0) {
*value_addr = ep->me_value;
return ix;
}
}
else {
/* The dict was mutated, restart */
goto top;
}
}
}
// 冲突,查看探查序列下一个位置
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
}
Py_UNREACHABLE();
}

lookdict 是实际查找哈希表的函数,使用这个函数,需要先计算出 key 对应的哈希。若查找到,返回值会被储存在 value_addr,否则其为 NULL。

它会根据给定的哈希生成一串探查序列,然后一次查找这些探查序列对应位置的数据,如果储存的 key 和 hash 和我们要查找的 key 和 hash 相等,就把数据储存在传入的 value_addr 指针里面,否则储存 null。

可见 lookdict 在 key 不直接相等时调用了 PyObject_RichCompareBool 函数,这会带来额外的开销。cpython 为预先知道 key 只能为 unicode object 的情况下提供了 lookdict_unicode 函数,去除了对 PyObject_RichCompareBool 的调用,使用更高效的 unicode_eq 函数。

当新建一个 dict 时,cpython 会将默认的查询函数设置为 lookdict_unicode,当插入一个非 unicode object 的键时,就会使查询函数退化为 lookdict。

除此之外,cpython 还提供了 lookdict_unicode_nodummy 函数,逻辑与 lookdict_unicode 一样,只是添加了 ix 不为 dummy 的 assert。当调用 dictresize 时,会删除 dict 中的 dummy,并将查找函数设置为它。之后当插入非 unicode object 时,就会退化为 lookdict。

插入哈希表

直接插入哈希表的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
static uint64_t pydict_global_version = 0;
#define DICT_NEXT_VERSION() (++pydict_global_version)

/* 在知道有对应 hash 的空位的情况下,返回哈希表中那个空位的位置
* hash 代表了哈希表的下标,为什么不直接只用呢?因为可能发生哈希冲突。
*/
static Py_ssize_t
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
{
assert(keys != NULL);

const size_t mask = DK_MASK(keys);
size_t i = hash & mask;
Py_ssize_t ix = dk_get_index(keys, i);
for (size_t perturb = hash; ix >= 0;) {
// 直到 ix 小于 0 时终止,也就是说为 empty 或 dummy
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
ix = dk_get_index(keys, i);
}
return i;
}

static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
PyObject *old_value;
PyDictKeyEntry *ep;

// split table,稍后解释
if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
// 调整哈希表大小,使 split table 转化为 combined table
if (insertion_resize(mp) < 0)
goto Fail;
}

Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
goto Fail;

if (ix == DKIX_EMPTY) {
/* Insert into new slot. */
assert(old_value == NULL);
if (mp->ma_keys->dk_usable <= 0) {
/* Need to resize. */
// insertion_resize: 调整哈希表大小使其符合 2/3 的装载率
if (insertion_resize(mp) < 0)
goto Fail;
}
// hashpos 哈希表中待插入位置的下标
Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
// dk_nentries: dk_entries 中已使用元素的个数
// 这里获得下一个元素,实现顺序插入
// 稍后会看到 cpython 在调用 insertion_resize时,会清除 dk_entries 中的空元素
ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
ep->me_key = key;
ep->me_hash = hash;
if (mp->ma_values) {
// split table
assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
mp->ma_values[mp->ma_keys->dk_nentries] = value;
}
else {
ep->me_value = value;
}
// 新插入元素调整各项大小,删除元素不再调整,从而使 ix 为 dummy 时的操作
// 和 ix 已经有元素的操作一致
mp->ma_used++;
mp->ma_version_tag = DICT_NEXT_VERSION();
mp->ma_keys->dk_usable--;
mp->ma_keys->dk_nentries++;
return 0;
}

// 为 dummy 或 已经存在的元素,直接设置值
if (_PyDict_HasSplitTable(mp)) {
// split table
mp->ma_values[ix] = value;
if (old_value == NULL) {
/* pending state */
assert(ix == mp->ma_used);
mp->ma_used++;
}
}
else {
assert(old_value != NULL);
DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
}

mp->ma_version_tag = DICT_NEXT_VERSION();
return 0;

Fail:
Py_DECREF(value);
Py_DECREF(key);
return -1;
}

insertdict 调用 lookdict 查看对应的键和哈希是否已经有值,如果没有就获取 dk_entries 中的下一个待插入条目并赋值,调用 dk_set_index 将它的位置设置到哈希表里。除此之外,同步更新了 ma_used、ma_version_tag 等的数据。

insertdict 是直接插入 dict 中哈希表的内部函数,许多其它暴露出来的 api 都会调用它。

删除键值

最内部的函数是 delitem_common,它的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// lookdict_index 获取在 dk_entries 中哈希为 hash,位置为 index 处的数据
// 对应在哈希表 dk_indices 中的位置
static Py_ssize_t
lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
{
size_t mask = DK_MASK(k);
size_t perturb = (size_t)hash;
size_t i = (size_t)hash & mask;

for (;;) {
Py_ssize_t ix = dk_get_index(k, i);
if (ix == index) {
return i;
}
if (ix == DKIX_EMPTY) {
return DKIX_EMPTY;
}
perturb >>= PERTURB_SHIFT;
i = mask & (i*5 + perturb + 1);
}
Py_UNREACHABLE();
}


// hash: 待删除元素的 hash; ix: 待删除元素位于 dk_entries 中的位置
static int
delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
PyObject *old_value)
{
PyObject *old_key;
PyDictKeyEntry *ep;

// hashpos: 待删除数据在哈希表中的下标
Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
assert(hashpos >= 0);

mp->ma_used--;
mp->ma_version_tag = DICT_NEXT_VERSION();
ep = &DK_ENTRIES(mp->ma_keys)[ix];
// 设置对应位置为 dummy,不改变 dk_nentreis,不调整 dk_usable
dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
old_key = ep->me_key;
ep->me_key = NULL;
ep->me_value = NULL;
Py_DECREF(old_key);
Py_DECREF(old_value);
return 0;
}

暴露给用户的 PyDict_DelItem 函数先计算出给定键的哈希,然后调用 lookdict 查看对应的键是否存在于哈希表中,如果存在,才会调用 delitem_common 真正删除其值。

调整哈希表

前面看到,当插入元素时如果空间不够,会调整哈希表大小:

1
2
3
4
5
6
7
8
// 使负载因子在 2/3 附近,需要调整的大小
#define GROWTH_RATE(d) ((d)->ma_used*3)

static int
insertion_resize(PyDictObject *mp)
{
return dictresize(mp, GROWTH_RATE(mp));
}

dictresize 里面有这样一个代码片段:

1
2
3
4
5
6
PyDictKeyEntry *ep = oldentries;
for (Py_ssize_t i = 0; i < numentries; i++) {
while (ep->me_value == NULL)
ep++;
newentries[i] = *ep++;
}

这里while (ep->me_value == NULL) ep++;使得调整后的 dk_entries 是连续的,其中不含 dummy。设置完 dk_entries 后,dictresize 会根据 dk_entries 中储存的键值,通过 lookdict 查找 dk_indices 的空位,然后使用 dk_set_index 反向设置哈希表中的值。从而重新建立对应关系。

dictresize 中还有其它一些细碎逻辑,就不一一剖析了。

相关API

提供给用户的 API 函数大体上都是对于几个直接操作哈希表的函数的封装。本处将列举几个相关的常用API。

PyDict_GetItem

源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
PyObject *
PyDict_GetItem(PyObject *op, PyObject *key)
{
Py_hash_t hash;
Py_ssize_t ix;
PyDictObject *mp = (PyDictObject *)op;
PyThreadState *tstate;
PyObject *value;

if (!PyDict_Check(op))
return NULL;
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1)
{
// 如果不是 unicode,或者是 unicode 但其内部没有缓存的 hash,就重新计算
hash = PyObject_Hash(key);
if (hash == -1) {
PyErr_Clear();
return NULL;
}
}

// dk_lookup 默认为 lookdict_unicode
// 如果 key 不是unicode,就会退化到 lookdict
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
if (ix < 0) {
PyErr_Clear();
return NULL;
}
return value;
}

可见,提供的 PyDict_GetItem 使用了 lookdict 及其相关函数。

PyDict_DelItem

源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int
PyDict_DelItem(PyObject *op, PyObject *key)
{
Py_hash_t hash;
assert(key);
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1) {
// 获得 hash 值
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}

return _PyDict_DelItem_KnownHash(op, key, hash);
}

int
_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
{
Py_ssize_t ix;
PyDictObject *mp;
PyObject *old_value;

if (!PyDict_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
assert(key);
assert(hash != -1);
mp = (PyDictObject *)op;
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
return -1;
if (ix == DKIX_EMPTY || old_value == NULL) {
// 删除不存在的元素会抛出错误
_PyErr_SetKeyError(key);
return -1;
}

// Split table doesn't allow deletion. Combine it.
if (_PyDict_HasSplitTable(mp)) {
// 从 split table 中删除元素会使它转换为 combine table
if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
return -1;
}
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
assert(ix >= 0);
}

return delitem_common(mp, hash, ix, old_value);
}

PyDict_DelItem 是在计算出给定键的哈希值并寻找到对应数据储存在 dk_entreis 下标后,调用 delitem_common 实现删除操作的。

PyDict_Contains

PyDict_Contains 函数的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int
PyDict_Contains(PyObject *op, PyObject *key)
{
Py_hash_t hash;
Py_ssize_t ix;
PyDictObject *mp = (PyDictObject *)op;
PyObject *value;

if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value);
if (ix == DKIX_ERROR)
return -1;
return (ix != DKIX_EMPTY && value != NULL);
}

简单的调用了 dk_lookup 函数,默认就是 lookdict_unicode 函数。

内部优化

dict 缓存池

为了避免频繁申请、释放内存,导致过多的系统调用,在 cpython 中,很多内建对象都有自己的缓存池。例如,整数有针对小整数的缓存池,字符串有针对短字符串的缓存池,同样,dict 也有自己的缓存池:

1
2
3
4
5
6
#define PyDict_MAXFREELIST 80

static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;
static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
static int numfreekeys = 0;

可见,dict 使用数组实现缓存池,并且 PyDictObject 和 PyDictKeysObject 各有一个数组。

我们可以在新建 PyDictKeysObject 的函数 new_keys_object 中看到这样的代码片段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (size == PyDict_MINSIZE && numfreekeys > 0) {
// 如果 size 符合 PyDict_MINSIZE,且 numfreekeys 有剩余,就直接使用缓存池中的对象
dk = keys_free_list[--numfreekeys];
}
else {
// 如果不能从缓存池中获取,就分配一段新内存。
// 这里分配的大小是根据要哈希表的大小动态计算的
dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
+ es * size
+ sizeof(PyDictKeyEntry) * usable);
if (dk == NULL) {
PyErr_NoMemory();
return NULL;
}
}

其中,PyDict_MINSIZE 默认情况下为 8,size 为新建的 PyDictKeysObject 里的哈希表大小。

当然,新建时能够从缓存池中获取,在销毁时也能归于缓存池。在销毁 PyDictKeysObject 的函数可以见到:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void
free_keys_object(PyDictKeysObject *keys)
{
PyDictKeyEntry *entries = DK_ENTRIES(keys);
Py_ssize_t i, n;
for (i = 0, n = keys->dk_nentries; i < n; i++) {
// 一一减少储存数据的引用计数
// 当引用计数为0,会触发各自的 delloc 函数
Py_XDECREF(entries[i].me_key);
Py_XDECREF(entries[i].me_value);
}
if (keys->dk_size == PyDict_MINSIZE && numfreekeys < PyDict_MAXFREELIST) {
keys_free_list[numfreekeys++] = keys;
return;
}
PyObject_FREE(keys);
}

如果符合条件,使用keys_free_list[numfreekeys++] = keys;使对象回到缓存池。否则才调用 PyObject_FREE 销毁 keys。

split table

前面说过,PyDictKeysObject 中的 dk_indices 是实际的哈希表,而 dk_entries 是实际储存数据的区域。这样的构造使得每个 dict 内都各有一个 PyDictKeysObject 对象用来记录键值。然而,在解释器内部使用到了许多键是 unicode object 且插入顺序相同的 dict 对象,它们之间只有值不同。cpython 为这种情况设计了一种键值分开储存的 split table dict。split table 能够在唯有值不同的多个 dict 中共享 PyDictKeysObject 对象。

回想起前面的 PyDictObject 对象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct {
PyObject_HEAD

/* Number of items in the dictionary */
Py_ssize_t ma_used;

/* Dictionary version: globally unique, value change each time
the dictionary is modified */
uint64_t ma_version_tag;

PyDictKeysObject *ma_keys;

PyObject **ma_values;
} PyDictObject;

其中有一个未曾被我们注意的字段 PyObject **ma_values;,这是一个指向 PyObject* 的指针,实际就是在 split table dict 里面用来存放 dk_entries 的字段。

可以使用 make_keys_shard 将 combined table 转换为 split table:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#define USABLE_FRACTION(n) (((n) << 1)/3)
#define new_values(size) PyMem_NEW(PyObject *, size)

static PyDictKeysObject *
make_keys_shared(PyObject *op)
{
Py_ssize_t i;
Py_ssize_t size;
PyDictObject *mp = (PyDictObject *)op;

if (!PyDict_CheckExact(op))
return NULL;
if (!_PyDict_HasSplitTable(mp)) {
PyDictKeyEntry *ep0;
PyObject **values;
if (mp->ma_keys->dk_lookup == lookdict) {
// 新建 dict 时默认的查询函数是 lookdict_unicode
// 如果查询函数是 lookdict,说明插入了非 unicode object 键,使 lookdict_unicode 退化为它
// 而 split table 的键只能是 unicode object
return NULL;
}
else if (mp->ma_keys->dk_lookup == lookdict_unicode) {
/* Remove dummy keys */
// dictresize 会删除 dk_indices 和 dk_entreis 中的 dummy
// 同时将 dk_lookup 设置为 lookdict_unicode_nodummy
if (dictresize(mp, DK_SIZE(mp->ma_keys)))
return NULL;
}
assert(mp->ma_keys->dk_lookup == lookdict_unicode_nodummy);
/* Copy values into a new array */
ep0 = DK_ENTRIES(mp->ma_keys);
// 一个 dict 的负载因子总会小于 2/3,因此这里使用 USABLE_FRACTION 来获得新 dict 的最大大小
size = USABLE_FRACTION(DK_SIZE(mp->ma_keys));
values = new_values(size);
if (values == NULL) {
PyErr_SetString(PyExc_MemoryError,
"Not enough memory to allocate new values array");
return NULL;
}
for (i = 0; i < size; i++) {
values[i] = ep0[i].me_value;
ep0[i].me_value = NULL;
}
// lookdict_split 其实和 lookdict_unicode_nodummy 的逻辑一样
// 只是最后数据从 ma_values 里面拿
mp->ma_keys->dk_lookup = lookdict_split;
mp->ma_values = values;
}
DK_INCREF(mp->ma_keys);
return mp->ma_keys;
}

当我们拥有一个 split table dict 对象之后,就可以用 new_dict_with_shared_keys 函数建立另一个共享了这个对象 keys 对象的 dict 对象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// new_dict 使用给定的 keys 对象新建一个 dict 对象,并且将 ma_values 设置为 values
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
PyDictObject *mp;
assert(keys != NULL);
if (numfree) {
// 直接从缓存池从拿一个对象
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
}
else {
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL) {
DK_DECREF(keys);
free_values(values);
return NULL;
}
}
mp->ma_keys = keys;
mp->ma_values = values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
assert(_PyDict_CheckConsistency(mp));
return (PyObject *)mp;
}

/* Consumes a reference to the keys object */
static PyObject *
new_dict_with_shared_keys(PyDictKeysObject *keys)
{
PyObject **values;
Py_ssize_t i, size;

// 获得新 dict 的最小大小
size = USABLE_FRACTION(DK_SIZE(keys));
values = new_values(size);
if (values == NULL) {
DK_DECREF(keys);
return PyErr_NoMemory();
}
for (i = 0; i < size; i++) {
// 初始化指针为 NULL
values[i] = NULL;
}
return new_dict(keys, values);
}

可以用 lookdict_split 函数从 split table 中查询值。它的逻辑大体和 lookdict_unicode_nodummy 相同,只是在读取值是从 ma_values 里面读取:

1
2
3
4
5
if (ep->me_key == key ||
(ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
*value_addr = mp->ma_values[ix];
return ix;
}

除此之外,有一个帮助我们判断一个 dict 是否是 split table 的宏:

1
#define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL)

结束

先就这样吧

girl