问题背景

Polardb MySQL InnoDB采用的是基于page的数据存储管理，因此内存使用主要是通过page buffer pool来完成的。通常，常规实例的内存配置为规格的75%，其中大部分内存用于buffer pool，同时一部分留给log parse buffer（只读节点）以及performance schema等。不同的负载对内存的需求相对一致，因此不需要调整各个模块的内存，可以充分利用物理机器上的内存。

然而，Polardb MySQL IMCI采用的是面向AP场景的列式存储，与InnoDB不同，它没有page的概念，读写内存是分离的。在IMCI上，查询通常会扫描大量的数据，并且可能有大量行存的更新操作，因此，读写内存都有较大的需求。这导致IMCI的内存使用与纯粹的InnoDB行存相比具有较大的差异。对于IMCI列存节点，需要预留近20%的内存给InnoDB本身的一些功能（如buffer pool、log parse buf等），剩余内存可以从功能层面上分为读内存（pack、meta cache）和写内存（nci、mem pack、trx buf等）。

随着workload的变化，读写模块内存的使用也会发生巨大的变化。例如，在只读负载下，需要分配给执行器和pack cache较多的内存，而其它模块占用较多内存对性能几乎没有帮助。更进一步，在只读负载下，需要分配给多个模块，例如执行器和存储引擎，执行器内存不足需要算子落盘，而存储的pack cache内存不足会导致IO开销增加，执行器与存储引擎之间的内存如何分配也需要权衡。

线上实例内存使用情况统计，不同实例对于不同负载，各个模块占用的内存比例具有较大差异。存在两个问题：1. 部分模块内存占用过高 2. 模块内存静态配置，无法根据当前负载自适应调整
由于不同模块之间的内存是独立的，在各个模块内存静态配置的情况下，为了防止oom，IMCI给各个模块内存设定了比较小的上限（例如，pack cache仅配置了机器规格的15%）。这种模块间的内存边界导致在只读或只写的负载下，机器的内存无法充分利用。因此，IMCI需要实现时空转移的内存管理，从而在面向不同的工作负载时，能够在各个模块之间充分利用内存配额，从而达到性能最大化。为了解决这些问题，我们推出了多个patch联合解决，例如缓存压缩的data pack、delta存储减少partial pack占用并且支持lru淘汰、pack mask支持lsm tree存储等来降低模块内存的占用。然而，如果不同模块之间的内存配额不能共享，这些解决方案仍然无法最大化利用内存。因此，本文的主要工作是打破不同内存模块之间的边界，提升IMCI对内存的利用率，从而使性能得到提升。

使用说明

可调整参数

• imci_memory_scheduler_check_interval_in_sec（默认0）：为0时，关闭调整功能，并且将各模块内存恢复至初始状态
• imci_physical_memory_high_watermark_ratio（默认85%）：高于这个比例会触发部分低优先级模块内存回收，比例计算方式为物理内存占用/server_mem_resource，按优先级从低到高顺序回收。低于这个比例会触发内存分配，空闲的内存（物理内存*ratio - 实际使用的内存）会按需分配给不同模块，使得每个模块的内存使用比例低于该模块的high_watermark，按优先级从高到低顺序分配。
• imci_physical_memory_low_watermark_ratio（60%）：低于这个比例，物理内存水位进入RELEASE demand level，主要用于后期管控serverless对接。
• imci_physical_memory_danger_watermark_ratio(95%)：高于这个比例，触发所有模块的内存回收

相关可调整参数：server_mem_resource，如果默认不设置这个参数（0），由于无法感知内存使用比例，调整功能不会起作用。

关于单个模块（lru pack、query、pruner）内存的手动调整（如set global imci_lru_cache_capacity=1GB) ，这种设置会使得该模块内存固定在1GB，后续不会参与自动调整，暂时也没有提供手段恢复自动调整。

线上参数建议：

• imci_memory_scheduler_check_interval_in_sec = 5
• imci_parallel_replay_nci_worker_num=CPU*2

可视化

增加 information_schema.imci_mem_module_usage 表，显示每个模块的名称、Priority、Demand Level、内存使用、quota、以及quota range。

日志

如果模块内存发生调整，会产生 IMCI_SEVERLESS_LOG, 搜索 [ALLOCATE MEMORY] ，[RELEASE MEMORY] ，可查看内存调整记录

当前已经接入的模块：

• PACK-NCI 的LRU Cache
• Pruner LRU Cache
• 执行器

方案设计

设计目标

1. 提升线上实例 lru cache的占比到50%（峰值）
2. 支持根据负载情况，各模块能充分利用空闲内存，并减少OOM
3. 未来支持拓展更多模块接入
4. 未来支持对接管控Serverless内存调整，合理规划各个模块的内存

难点&挑战

整体来说，后续的IMCI 内存主要分为三大类型

• 支持落盘/踢出去的内存，即LRU cache内存。这种内存也包括两种，一种是写入型cache（如nci），另一种是只读cache，写入型cache淘汰涉及到异步刷脏的问题，回收速度比较慢。
• 支持shrink（不支持落盘）的内存，例如执行内存，它可以通过block query来抑制内存的增长，也可通过kill query的方式来释放内存。但目前query memory的回收机制还不完善，通过kill query的方式回收内存比较粗暴，缩容代价不可控。
• 动态申请的其它内存，例如mask、mem pack这类，它们只能常驻内存，优先级最高，缺少内存时直接OOM，暂时没有手段进行内存回收，等后续这类问题解了可进一步增加内存回收能力

想要实现目标，主要从机制和策略两个方面入手。首先是机制，就是基于现有IMCI的能力，如何实现内存之间的共享；其次是策略，就是如何将内存合理分配到不同的模块。

挑战一：workload快速变化。workload不可预测，不同模块对内存的需求变化较快，mem scheduler如何快速响应这种情况，并且防止oom，这需要良好的内存共享机制。
挑战二：不同模块内存使用复杂。例如可分为执行内存、运行时内存、lru 读cache、lru写cache等，需要内存调整策略来实现不同模块内存的合理分配。

解决方案

内存共享机制

内存共享机制主要依赖IMCI内存管理系统现有的三大能力：内存监控能力、内存分配能力以及内存回收能力

整体框架

内存监控能力：主要依赖于物理内存监控以及各个模块自己的内存统计，比如lru模块以及query 模块均有自己的内存使用统计，物理内存的上限目前依赖于变量server_mem_resource来感知，该变量属于规格参数，与实例内存相关，对于后台docker加的内存，无法感知，需要调整server_mem_resource才能感知。虽然目前大部分IMCI都能被AllocWrapper 根据mod_id 统计到，但目前的统计存在交叉混杂、缺少行存等问题（见下文）。
内存分配能力：依赖模块自身的动态分配能力。目前lru cache与执行器均支持在线调整capacity/limit，但由于是静态的配置，需要设置的比较小，从而防止占用过多内存导致oom。
内存回收能力：依赖模块自身的内存回收能力。对于lru cache来说，内存回收比较简单，但是对于执行器来说，当前内存回收通过block/kill 查询方式来降低内存使用，可能导致查询执行到一半被kill从而反复执行，造成抖动，目前还不支持通过驱动算子落盘的方式来回收内存。

IMCI 定义了一些宏来方便对不同ModId的内存申请与释放进行统计，可通过AllocWrapper全局单例获取不同ModId的内存使用，然而直接依赖于IMCI的AllocWrapper来监控内存使用在完整性、高效性、准确性方面都存在问题，改造难度比较大。
1）目前的内存统计不包含所有内存模块（比如行存、线程开销、stl、栈内存等），为了解决这个问题，一种方式是通过后台定时获取进程的物理内存使用情况，如果物理内存水位高于一定阈值，则触发内存回收任务，降低整体内存水位，防止OOM。另一种方式是完善改统计模块的能力，使其监控到所有内存使用。
2）获取总内存使用开销大。与ck不一样的是，IMCI的AllocWrapper目前对于总内存使用的统计接口是需要遍历所有线程的tls统计指标，而ck是当线程内存统计达到一定阈值时自动累加到全局内存统计中。
3）模块之间的mod_id存在交叉，目前mod_id比较多，默认的default就不知道包含了多少模块的内存。因此直接根据mod_id 不太好统计各个模块的内存使用情况，这点需要规范，或者各个模块各自统计自己的。

目前通过mysqld的物理进程内存来进行整体内存的监控，以及模块内存的独立统计来监控模块内存，来解决上述问题，以确定当前是否需要分配/释放内存。

模块划分

IMCI实例的mysqld进程，包含行存以及IMCI两个板块的内存。
如果将内存划分为三类模块，一类模块是lru的，一类是query（执行器）的，最后一类就是其它所有的（后称最高优先级模块，包括行存+列存的其它所有内存）。lru和query模块的内存使用统计均可以通过现有的接口拿到，lru有自己的usage统计，query也有自己的usage统计，而其它模块内存可以使用总内存使用减去这两个部分。
其中LRU又可进一步划分成为pack、nci、pruner，未来可能会有更多，例如mask、delta以及compacted pack。对于不同LRU模块内存的管理，有两种方案：
方案一：扁平化管理。不同LRU模块作为独立的模块，与Query模块、最高优先级模块并列，使用一套方案进行管理。这样做的优点是灵活；缺点则是前期query模块与lru之间的优先级比较比较复杂。

扁平化管理
方案二：层次化管理。不同LRU模块统一由LRUManager管理，而LRUManager与Query、最高优先级模块并列一起管理。这样做的优点是，前期LRU与Query之间的策略会简单许多，同时LRU之间到优先级定义相对更容易定义；缺点则是灵活性差，例如想让query优先级介于nci与其它lru模块之间就不好办。

层次化管理

目前，采用第一种更加灵活的方案。

内存调整策略

策略概览

概念定义

• memory demand level： 来描述不同模块对内存的需求程度，物理内存也有自己的内存需求程度（如上图所示），物理内存的memory demand level定义比较简单，仅根据水位来决定，每个模块有自己的MDF函数，用来告诉调度器自己当前的memory demand level，从而使得不同内存模块与内存调度控制器解偶合。
• 空闲物理内存：physical_memory_usage - physical_memory_limit * high_watermark
• final 优先级：每个模块enum定义的数值（越大优先级越高）/(所有模块数+1) + Demand Level，也就是说按照final 优先级排序，等价于先按照demand level排序（整数部分），再按照模块优先级排序（小数部分）。例如三个模块pack、pruner、nci，在demand level分别为HOLD、NEED、RELEASE的情况下，pack 的final 优先级为 1/4+1 = 1.25，以此类推，pruner final优先级为2/4+2 = 2.5, nci的final 优先级为 3/4+0 = 0.75，按照final优先级从高到低排序是pruner > pack > nci。

内存调度整体流程

1. 更新各模块demand level
2. preReleaseQuota：对demand level为 RELEASE的进行quota回收
3. release/allocate 二选一：physical memory的demand level处于NEED以上时触发release，反之触发allocate

• 单个模块触发allocate必要条件：module’s memory demand level > physical memory demand level && modules’ demand level >= NEED，否则跳过这个模块
• 单个模块触发release必要条件：module’s memory demand level <= physical memory demand level

举例说明：当前物理内存处于HOLD level，而NCI处于NEED level，则会分配内存给NCI，能分配的最大内存是空闲物理内存；当物理内存上升，进入NEED level时，即使NCI处于URGENT level也无法分配到内存，因为没有空闲物理内存，但此时由于物理内存进入NEED level，因此会触发回收，由于NCI的demand level更高，因此也不会回收NCI的内存，直到物理内存进入URGENT level，才会回收NCI的内存。

内存分配策略

**分配时机：**模块内存水位达到本模块的high water mark raito，物理内存水位低于imci_physical_memory_high_watermark_ratio
分配策略：按final优先级从高到低顺序分配，对于每个模块，初始时具有自己的初始内存上限mem_init，后续无论是borrow还是lend的内存都是用mem_delta来记录。
单个模块内存分配量：min（空闲物理内存，使得模块水位达到high_wm以下的最少内存，使得模块quota达到该模块上限的最少内存）
通过总的内存水位来判断当前整体内存使用状态，预留一部分内存兜底。
空闲内存 = 总内存上限*high_watermark_ratio - 当前已使用内存
如果空闲内存 < 1% 或 < 32MB, 回收内存 < 2% 或 32MB，则认为操作空间不大，本次不进行调整
如果能分给某个模块的内存不到1MB，本次不给该模块调整内存

不同模块内存水位设置
高水位：85%
低水位：65%
lru pack-nci模块：

• max/default/min limit: 45%，15%，15%，下限为15%，防止内存回收导致性能回退

lru pruner模块：

• max/default/min limit: 3%, 1%，1% of global limit

query 模块：暂时不参与调整

• max/default/min limit: 15%, 15%，15% of global limit

recycle_ratio：10% 当进行内存回收时，模块单次回收的最大内存。

内存回收策略

目前可强制回收的内存包括LRU pack，LRU nci，LRU pruner，query等。假设这几个模块均借用了内存，以什么样的策略进行回收需要小心设计，因为缩容比扩容往往代价要大很多。
回收时机：水位高于high_watermark_ratio
内存回收量：物理水位低于high_watermark_ratio的最少内存。
回收策略：按照final优先级顺序从低到高，回收recycle_ratio的内存，直到满足需求

内存防抖动策略

我们用一个简单的模型来描述这个问题。我们可以把不同模块在不同时间的内存需求当作一个数组，假设就高优先级模块和lru两个模块。高优先级模块的内存虽然无法被抢占，但是可能它一段时间内释放了1GB，再过一会又需要1GB。如果在其释放1GB后，马上分配给lru（仅分配，无抢占），那当它需要时必须得还给它（发生抢占），因此也会造成抖动。

为了避免这个问题，可以使用移动平均值来平滑内存调整的曲线。例如我们把一个时间窗口内的期望内存需求存下来，但实际调整的时候，用移动平均值来调整。例如，我们监测到高优先级内存模块的需求就是一直在正负抖动，那最好的策略就是不动它，移动平均值可以缓解解决这个问题。
另外对于模块内存的需求变化，也可以使用移动平均值进行smoothing。
还有就是在调整内存时，对于delta值比较小的情况会跳过，对于空闲内存<1%，需要释放的内存<2%时也不会操作，防止内存在该水位附近时不断触发回收/分配的问题。

注意：对于Demand Level 为URGENT的模块，在内存分配/回收时会跳过 smoothing。

讨论：执行器模块内存的抖动问题
这个问题仅通过移动平均值不能很好解决，主要是查询内存的回收，目前通过block/kill query方式，可能造成查询性能回退，以及查询反复重试。最好是执行器能够在进行execution_memory_limit 缩容时，支持主动通知查询算子spill disk来回收内存。

更多lru模块的接入

后续delta、mask、compaction pack、innodb bp等lru模块接入时，会产生更多的lru模块。在内存分配策略中，我们会先把优先级低的lru cache淘汰出去，然后再做分配。如果存在多个lru 模块，并且具有自己的优先级，优先淘汰优先级低的策略初步看问题不大，因此对于新接入的lru，仅需设定好cost模型即可，但首先需要确保加入的lru模块稳定地支持动态调整capacity能力。

管控serverless对接

管控可通过查询i_s.imci_mem_module_usage的mysqld模块的memory demand level 来确定进行升配还是降配

低水位后台加载cache

当整体内存usage比较低时，可以让后台线程加载lru pack、pruner之类的来加速后续的查询，减少查询冷启动开销。

内存调整速度自适应策略

主要应对的场景是，某个模块的内存使用增长比较迅速，后台调整的时间间隔比较长，无法满足时效性。初期可以将后台调整间隔设置比较小，但这样调整的开销可能比较大。
一个策略是：如果oom checker发现物理内存再次进入危险水位，则提升内存检查频率。

基于代价评估的优先级策略

通过demand level与优先级的方式，主要基于规则枚举，难以保证内存分配是最优的。现有学术论文的方法更多是建立cost模型去量化代价，从而达到理论最优，这是个比较复杂的工程。

工作规划

• 一期：实现内存共享机制以及内存调整策略1-4的基础版，估计开发周期2～3个月
• 二期：根据需要实现内存调整策略5-7，根据需要优化代码中的内存统计以及cost模型
• 三期：稳定迭代2个版本后，对接管控serverless

性能测试

实验设置

• 实例规格：8c 32GB，rw+ro本地部署，通过cgroup限制cpu
• 实例内存：pack-nci lru 默认15%，query 默认15%，innodb bp 默认15%，pruner-lru 默认1%
• workload：纯dml（oltp_write_only)，混合负载（oltp_write_only + tpch-100g)，纯查询（tpch-100g)
• 检测指标：各模块内存、总内存，以及性能

实验结果

• 开启auto adjust 后，mysqld的内存使用率更高，且lru 大小会随着mysqld的内存使用情况动态变化。
• 纯写入性能略微提升（提升2%以内）
• 混合负载查询性能提升1.5倍，写入性能变化不大
• 纯查询性能提升2.35倍

相关系统内存管理方案调研

oracle

oracle支持automatic memory manage，即用户只需要制定数据库能使用的内存上限，oracle自动会根据不同的负载调整各个components内存的分布，并且这个内存上限也支持在线调整，因此其具备的能力基本是IMCI目前想要演进的能力。
具体实现方法没有公开，仅从官方文档上看，以下能力值得借鉴。

• 通过简单的单个内存上限参数调整IMCI整体可用内存上限，由后台内存管理模块自动根据负载完成各个模块内存的分布
• 可通过手动调整单一模块的内存下限，这时其它部分的内存依然可以由后台内存管理模块进行分配。简单的关闭auto tuning功能，因为内存模块可能很多，如果因为某个需求手动调整所有模块的内存分配，运维起来是极其麻烦的

clickhouse

clickhouse的对内存的统计与限制都是基于内存追踪机制MemoryTracker，其可以统计的维度包括线程、查询、用户、进程，这四种维度分别由不同的MemoryTracker对象统计，形成一种如下图所示的树形结构，其中parent是更加high level的内存统计值。当MemoryTracker更新时，会同时更新它的parent。系统中有一个全局的MemoryTracker total_memory_tracker，他是所有MemoryTracker的根，可以追踪整个进程的内存。

clickhouse重载了new/delete operator来追踪clickhouse和第三方库申请释放的内存。但是每次new/delete都统计一次内存会造成比较大的性能浪费，clickhouse做了一个优化就是再线程内维护一个变量，其累积再一定周期内的内存变动，如果内存变动觉得值超过4MB时，更新线程内存统计值，同时更新它的parent以及更上层的统计值，具体参考ThreadStatus::untracked_memory_limit。因此global的内存统计值得到并不是完全确切的内存使用情况。
对于global统计值可能不准确的问题，clickhouse采用了一个定时修正的方式，通过AsynchronouseMetrics每分钟根据进程实际使用的内存进行修正。
类似地，impala、doris也是通过memory tracker的机制来实现内存的统计，并且防止oom，但在实现上有所不同。

Presto

prestro由于没有存储，主要是考虑查询内存如何调度和分配。

• 通过block查询、kill查询的方式来防止oom，具体采用block还是kill，则根据reserved pool是否用满来决定
• 后台通过监测内存水位，从而驱动算子落盘来回收内存

目前IMCI在执行器内存控制方面，大体思路与presto类似，具体实现细节上存在些许差异，具体可参考《IMCI执行器内存控制实现方案》https://aliyuque.antfin.com/nituizi/oncxfu/mdn5ny

Papers

[vldb’06] Adaptive Self-tuning Memory in DB2

介绍了DB2的9.1 版本引入的Self-tuning Memory Manager技术，它将成本效益分析以及控制理论技术应用在内存调整上，从而动态调整不同模块（例如compiled statement cache, sort, and buffer pools）的内存使用量。
这里的成本是指减少某个模块的内存带来多大的性能衰减，而效益是指增加某个模块的内存带来多大的性能提升。成本和效益还可以进一步被分成IO/CPU两种资源类型，例如buffer cache节省的是IO开销，而compiled SQL statement Cache则节省的是CPU开销。
具体的成本效益评估方法，主要基于一种simulated buffer pool extension (SBPX)，将淘汰出去的page handle记录在SBPX中。例如依次访问page 1，page 2，page 3，假设访问page 3时 page 1被淘汰，其page handle记录在SBPX中。如果下次访问page1命中SBPX中的page1 handle，由于实际page 1已经被淘汰，需要进行一次IO（假设page 1时间为t1）。simulated的思想就是，如果cache更大一点使得之前的page 1 没有被淘汰出去，那么就可以节省时间t1。可通过计算 累积节省的时间T/page handle数量 来得到buffer pool单位page能节省的时间。类似的思想也可以用于其他类型的内存模块。

关于内存的分配问题，主要根据各个模块的单位内存能节省的时间，将低于平均值的模块内存划分一部分到高于平均值的模块，另外还利用了一些控制理论算法减少抖动。

[vldb’20] Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems

将LSM-tree的内存划分为buffer cache和write memory，利用代价建模自动调整这两部分内存的大小，从而达到最优的性能，相比较于最新的其它论文，该论文的特点是利用白盒模型而不是黑盒机器学习模型，核心还是对成本进行建模，只不过针对lsm-based storage system做了更多的优化工作，例如内存分区以及刷盘策略的优化。
但是该文章有两大局限性，一方面是没有考虑查询的内存，另一方面是偏学术，不像db2则是脱胎于实际商业数据库，实用性而言还是有差距。

参考

• https://docs.oracle.com/en/database/oracle/oracle-database/19/admin/managing-memory.html#GUID-B8B8923C-4213-42A9-8ED3-4ABE48C23914 oracle 内存管理
• http://jackywoo.cn/clickhouse-memory-management/ clickhouse内存管理方案
• https://presentations.clickhouse.com/meetup60/overview-of-caching.pdf clickhouse caching方案
• [vldb’20] Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems
• [vldb’06] Adaptive Self-tuning Memory in DB2