POND：高效的 Python 通用对象池技术

Qin -

已经开源在 GitHub：

GitHub - T-baby/pondpond: Pond is a high performance object-pooling library for Python
Pond is a high performance object-pooling library for Python - GitHub - T-baby/pondpond: Pond is a high performance object-pooling library for Python
GitHubT-baby

介绍

程序设计中，创建物体模块主要是通过生成对象来实现， 当对象使用结束后，则会成为不再需要的模块进行销毁。而在 系统进行对象的生成与销毁过程中会大量的增加内存的消耗， 同时对象的销毁往往会留下残留的信息，这样将会伴随内存泄 露的问题存在。实际的程序开发过程中，往往需要生成和销毁 大量重复的对象，这就使得内存泄漏产生的信息过多而无法被 系统回收，从而占用系统更多的内存，而且生成物体过多时无 法确定被什么模块实例化实现，对系统造成负担，不利于管理 及后续操作，长此以往最终将导致程序变慢甚至崩溃。

对象池，是存放了一批已经创建好的对象的池，它是一个 用来维护对象的结构。当程序需要使用对象的时候，可以直接 从池中获取该对象，而不是实例化一个新的对象。在程序设计 过程中，大部分人关注的往往只是对象的使用和效果的实现， 实际上创建和使用之间还有一个初始化的过程，不过系统会将 初始化和创建这两步结合在了一起，这样使得设计者忽略了系 统创建和销毁对象这一过程对系统的影响。通常来讲，一个对 象的创建和销毁过程开销很小，可以忽略不计，但是如果一个 程序中涉及到一种对象多次创建，并且创建时间比较长，那就 会能很明显的感觉到这部分的消耗所造成的系统速度受限。对象池可以看作是减少 GC 压力的首选方法，同时也是最简单的方法。

对象池模式主要适用于以下应用场景：

  • 资源受限的场景。比如，不需要可伸缩性的环境（CPU、内存等物理资源有限），CPU性能不够强劲，内存比较紧张，垃圾收集，内存抖动会造成比较大的影响，需要提高内存管理效率， 响应性比吞吐量更为重要。
  • 在内存中数量受限的对象。
  • 创建成本高的对象。
  • 大量的存活期短且初始化成本低的对象池化，以降低内存分配和再分配成本，避免内存碎片。
  • Python 的这样的动态语言，GC 是依靠引用技术来来保证对象不会过早的回收，某些场景下可能出现虽然创建了但是没人使用的空闲期，导致对象被回收了。可以委托给对象池来保管。

主要贡献

Pond 是一个 Python 中高效的通用对象池，具有性能好、内存占用小、命中率高的特点。基于近似统计的根据频率自动回收的能力，能够自动调整每个对象池的空闲对象数量。

因为目前 Python 目前没有比较好的、测试用例完备、代码注释完备、文档完善的对象池化库，同时目前的主流对象池库也没有比较智能的自动回收机制。Pond 可能是 Python 中第一个社区公开的测试用例完整，覆盖率 90% 以上、代码注释完备、文档完善的对象池化库。

Pond 灵感来自于 Apache Commons Pool、Netty Recycler、HikariCP、Caffeine，集合了多家的优点。其次 Pond 通过使用近似计数的方式以极小的内存空间统计每个对象池的使用频率，并且自动回收。

本文的主要贡献在于展示了用基于近似 LFU 的回收策略的通用对象池的可行性和有效性，包括以下几个方面。

首先，我提出了一个对象池结构 Pond，在这个结构中，可以存放不同种类的对象，并将它们池化。

第二，我参考 Caffeine 使用了一种自适应缩减的近似 LFU 统计并进行了优化，计数的表格会随着对象池的种类自适应变大或变小，可以支撑非常大的访问计数以及非常多完全不同种类的对象池，同时这种近似统计可以很好地模仿了真实访问频率中的相应排序。

第三，提出了一种基于访问频率回收对象池中的对象的策略。

第四，设计了两种调取对象的实验，对 Pond 的自动回收能力进行比较，评估是否能以更少的对象来支撑更大的使用量的可行性。

POND 架构设计

POND 设计概述

Pond 主要由 FactoryDict、Counter、PooledObjectTree 三部分以及一个单独的回收线程构成。

FactoryDict

使用 Pond 需要实现对象工厂 PooledObjectFactory，PooledObjectFactory 提供对象的创建、初始化、销毁、验证等操作，由 Pond 调用。所以为了让对象池支持存放完全不同的对象，Pond 使用了一个字典来记录每个工厂类的名称和自己实现的工厂类的实例化对象。

每个 PooledObjectFactory 应该具备创建对象、销毁对象、验证对象是否还可用、重置对象四个功能。

比较特别的是 Pond 支持自动重置对象，因为某些场景下可能会存在对象中要先赋值进行传递，传递完又被回收的情况，为了避免污染建议这种场景下无比实现这个功能。

Counter

Counter 中保存了一个近似计数器，这个会在后面详细论述。

PooledObjectTree

PooleedObjectTree 是个字典，每个 key 对应着一个先进先出的队列，这些队列都是线程安全的。每个队列中保存着多个 PooleedObject。PooledObejct 保存了创建时间、最后借出的时间以及实际需要的对象。

线程安全

Pond 的借用和回收都是线程安全的。Python 的 queue 模块提供了一个适用于多线程编程的先进先出（FIFO）数据结构。它可以用来安全地在生产者和消费者线程之间传递消息或其他数据。锁是调用者来处理的，所有多个线程能够安全且容易的使用同样的 Queue 实例工作。而 Pond 的借用和回收都是在操作 queue，所以基本可以认为是线程安全的。

借出机制

在使用 Pond 借出一个对象时，会先检查想要借出的对象的种类是否已经在 PooledObjectTree 存在，如果存在会检查这个对象的对象池是否为空，如果为空会创建一个新的。

如果对象池中有多余的对象，会利用 queue 弹出一个对象并验证这个对象是否可用。如果不可用会自动调用所属的 Factory 清理销毁该对象，同时清理它在 Python 中的 GC 计数，让它更快被 GC 回收，不断拿取下一个直至有可用的。

如果这个对象可用，则会直接返回。当然无论是从对象池中取出对象还是新创建了一个对象，都会利用 Counter 增加一个计数。

回收机制

回收一个对象时会判断目标对象池存不存在，如果存在会检查对象池是否已经满了，满了的话会自动销毁要归还的这个对象。

然后会检查这个对象是否已经被借出太长时间，如果超过了配置的最长时间同样会被清理掉。

近似计数法概述

Count-Min Sketch 是一种可以处理等值查询，Join 大小估计等的数据结构，并且可以提供很强的准确性保证。自 2003 年在文献 An improved data stream summary: The count-min sketch and its applications 中提出以来，由于其创建和使用的简单性获得了广泛的使用。 Count-Min Sketch 维护了一个 d*w 的计数数组，对于每一个值，用 d 个独立的 hash 函数映射到每一行的一列中，并对应修改这 d 个位置的计数值。

我们利用 Count-Min Sketch 实现了 Counter，在实际测试中，一千种对象只需要 7-8 kb 的内存空间进行计数。

详情可以看我的另一篇博文。

TinyLFU 分析
TinyLFU 是一种为了解决传统 LFU 算法空间存储比较大的问题同时也是 Caffeine 使用的缓存算法，特别是淘汰算法和并发模型。本文将深入分析 TinyLFU。
QINQin

计数器重置

在某些高并发等的场景下，会导致每个对象的调用计数疯狂的增多，这样会导致 Count-Min Sketch 记录的数值可能会越来越不准，其次是会消耗更多的内存空间。

我们知道 Count-Min Sketch 的精准度是受到 m 和 d 两个参数影响的，而 Pond 并不能提前知道到底有多少种类的对象池，所以为了能够更精准的记录，在每次执行自动回收时会检查 PooledOBjectTree 的大小是否发生了变化，发生了的话会自动求最佳的 m 和 d。然后重新生成一个更适合的 Count-Min Sketch。参考原论文的式子：

$$\text { parameters }(\varepsilon, \delta), \text { set } w=\left\lceil\frac{e}{\varepsilon}\right\rceil \text { and } d=\left\lceil\ln \frac{1}{\delta}\right\rceil$$

我们设定 \(W\) 是样本大小，\(f_i\) 是 item i 的频率，\(h_i\) 是 Count-Min Sketch 中的估计数字。\(n\) 为对象池种类的数量。

我们预设了一些值，会得到下面这样的式子：

$$\varepsilon = \begin{cases} \Large \frac{10}{n}&n>10\\ 0.1&0<=n<=10 \end{cases}$$< p>

$$\delta = 0.1$$

$$w=\left\lceil\frac{e}{\varepsilon}\right\rceil \text { and } d=\left\lceil\ln \frac{1}{\delta}\right\rceil$$

在 \(1-{\delta}\) 的概率下，总误差（所有元素查询误差的之和）小于 \({\varepsilon}\)

我在 Counter 中已经默认了一些公式中的参数。

为了避免计数无限增长，参考了 TinyLFU 采用了一种基于滑动窗口的时间衰减设计机制，借助于一种简易的 reset 操作：每次添加一条记录到 Sketch 的时候，都会给一个计数器上加 1，当计数器达到一个尺寸 W 的时候，把所有记录的 Sketch 数值都除以 2，该 reset 操作可以起到衰减的作用。

由于我们的重置操作使用整数除法，它引入了截断错误。也就是说，在复位操作之后，计数器的值可能比浮点计数器的值低 0.5。如果我们必须再次复位，在复位之后，前一个复位操作的截断误差除以 0.25，但是我们积累了一个新的截断误差 0.5，导致总误差为 0.75。很容易看出，最坏情况下截断误差最多收敛到比项的准确率低一点。因此，截断错误对一个项目的记录发生率的影响在复位操作后高达 2/w。这意味着样本容量越大，截断误差越小。

重置部分参考原文论文的证明：

根据重置之前的计数，我们会得到一个式子，\( \epsilon(h_i) = f_i \cdot W\)

每次重置后都会处以 2，但下一次增长的时候是在 \(\frac W 2\) 的样本中增长的，那么就会加上 \(\frac {f_i \cdot W} 2\)  ，相加后又会等于 \(f_i \cdot W\) 考虑到是相加增长的，所以我们可以认为在下一次重置之前 \( \epsilon(h_i) = f_i \cdot W\)。

正常情况下 Count-Min Sketch 是有误差 \(\delta\) 的，所以 \( \epsilon(h_i) = f_i \cdot W + \delta\)，在重置操作后会变成  \(\frac {f_i \cdot W} 2 + \frac \delta 2\)，那么在重置后的增长为  \(\frac {f_i \cdot W} 2 + \frac \delta 2 + \frac {f_i \cdot W} 2= f_i \cdot W + \frac \delta 2\)，那么 \(k\) 次重置后会得到 \( h_i = f_i \cdot W + \frac \delta {2^k} \) 。

因此我们可以写成：

$$\lim _{k \rightarrow \infty}\left(f_{i} \cdot W+\frac{\delta}{2^{k}}\right)=f_{i} \cdot W$$

由于上面的复位操作是使用整数出发，所以有可能会出现截断错误，因为每次处以 2 的浮点计算都会带来一定的误差。但样本量越大误差越小。

自动回收

自动回收时每隔一段时间，默认是 300 s，就会执行一次。每次执行时会取出 Counter 中记录的最大使用频次 \(n\)，然后将 PooledObjectTree 中小于 \(wn\) 频次的所有对象池中的对象的空闲数量缩减一半并向下取整。\(w\) 默认是 0.8。

帕累托法则（英语：Pareto principle，也被称为 80/20 法则、关键少数法则、八二法则 指出，约仅有 20% 的变因操纵着 80% 的局面。也就是说：所有变量中，最重要的仅有 20%，虽然剩余的80%占了多数，控制的范围却远低于“关键的少数”。 管理咨询约瑟夫·朱兰首先提出该原则。此一概念起源于意大利经济学家 帕累托 (Vilfredo Pareto) 在洛桑大学注意到了 80/20 的联系，于他的第一篇文章《政治经济学》中说明了该现象，例如：意大利约有 80％ 的土地由 20％ 的人口所有、80% 的豌豆产量来自 20% 的植株等等。

参考了二八定律，所以默认值是 0.8 。Pond 认为 80% 的调用量应该只会调用其中 20% 的对象池，所以应该淘汰掉 80% 的对象池中的对象。

实验结果

随机访问实验

随机访问实验是模拟正常的网络请求下的对象访问几回收情况，生成了 1000 种对象的对象池，每个对象池的大小为 8。每个 200 ms 随机访问 100 个对象，持续访问 60 秒，然后看不同的自动回收间隔时间下的在访问持续时间结束后剩余的所有对象池对象的总数。x 轴是间隔时间，y 轴是剩余数量。

我们可以在随机实验中发现的确 0.8 的权重效果更好，能节省更多的内存，在智能调控后只需要更少的对象就可以撑住同样的访问量。但随机访问只是代表了更平均的流量。

2/8 访问实验

为了更好的模拟线上的访问请求，理论上 80% 的流量是由 20% 的 API 承担的。 2/8 访问实验与随机访问实验类似，只不过访问的方式从随机改为 100 次的前 80 次只能访问对象池中前 20% 的对象。

通过上述图表我们可以发现 0.8 的权重仍然效果很好，可以用更少的对象数承载更大的访问量。

命中率实验

借用命中率（Borrow hit rate）是指 1- (借用对象时的创建次数 / 总调用量) ，借此衡量回收是否可能会回收掉应该保留的对象的可能性。命中率越高则对象重新创建次数越低。

我们可以发现在随机访问的较为平均的场景下和 2/8 的调用量场景下，只要不是太高的回收频率都可以保障 100% 的命中率，即使是每 10s 回收一次都能保障 96% 以上的命中率。

实验结论

即使在只自动回收一次且流量较为随机平均的情况下，默认策略和权重可以降低  48.85% 内存占用，命中率 100%。

即使在只自动回收一次且流量较为符合 2/8 定律的情况下，默认策略和权重可以降低 45.7% 内存占用， 命中率 100%。

使用说明

你可以先安装 Pond 的库并且在你的项目中引用。

pip install pondpond

from pond import Pond, PooledObjectFactory, PooledObject

首先你需要声明一个你想要放入的类型的对象的工厂类，比如下面的例子我们希望池化的对象是 Dog，所以我们先声明一个 PooledDogFactory 类，并且实现 PooledObjectFactory。

class Dog:
    name: str
    validate_result:bool = True


class PooledDogFactory(PooledObjectFactory):
    def creatInstantce(self) -> PooledObject:
        dog = Dog()
        dog.name = "puppy"
        return PooledObject(dog)

    def destroy(self, pooled_object: PooledObject):
        del pooled_object

    def reset(self, pooled_object: PooledObject) -> PooledObject:
        pooled_object.keeped_object.name = "puppy"
        return pooled_object

    def validate(self, pooled_object: PooledObject) -> bool:
        return pooled_object.keeped_object.validate_result

接着你需要创建 Pond 的对象：

pond = Pond(borrowed_timeout=2,
            time_between_eviction_runs=-1,
            thread_daemon=True,
            eviction_weight=0.8)

Pond 可以传递一些参数进去，分别代表：

  • borrowed_timeout ：单位为秒，借出对象的最长期限，超过期限的对象归还时会自动销毁不会放入对象池。
  • time_between_eviction_runs ：单位为秒，自动回收的间隔时间。
  • thread_daemon ：守护线程，如果为 True，自动回收的线程会随着主线程关闭而关闭。
  • eviction_weight ：自动回收时权重，会将这个权重与最大使用频次想乘，使用频次小于这个值的对象池中的对象都会进入清理步骤。

实例化工厂类：

factory = PooledDogFactory(pooled_maxsize=10, least_one=False)

所有继承了 PooledObjectFactory 都会自带构造函数，可以传递 pooled_maxsize 和 least_one 两个参数。

  • pooled_maxsize：这个工厂类生成出的对象的对象池的最大能放置的数量。
  • least_one：如果为 True，在进入自动清理时，这个工厂类生成出的对象的对象池会至少保留一个对象。

向 Pond 注册这个工厂对象，默认会使用 factory 的类名作为 PooledObjectTree 的 key ：

pond.register(factory)

当然你也可以自定义它的名字，名字会作为 PooledObjectTree 的 key：

pond.register(factory, name="PuppyFactory")

注册成功后，Pond 会自动根据 factory 中设置的 pooled_maxsize 自动开始创建对象直至填满这个对象池。

借用和归还对象：

pooled_object: PooledObject = pond.borrow(factory)
dog: Dog = pooled_object.use()
pond.recycle(pooled_object, factory)

当然你可以用名字来进行借用和归还：

pooled_object: PooledObject = pond.borrow(name="PuppyFactory")
dog: Dog = pooled_object.use()
pond.recycle(pooled_object, name="PuppyFactory")

完全清理一个对象池：

pond.clear(factory)

通过名字清理一个对象池：

pond.clear(name="PuppyFactory")

正常情况下，你只需要使用上面的这些方法，生成对象和回收对象都是全自动的。

目前已经开源在 GitHub：

GitHub - T-baby/pondpond: Pond is a high performance object-pooling library for Python
Pond is a high performance object-pooling library for Python - GitHub - T-baby/pondpond: Pond is a high performance object-pooling library for Python
GitHubT-baby

下一步

  • 考虑用 cython 之类的进一步优化性能。
  • 可以考虑使用更优秀的字典数据结构以及队列结构。