缓存管理经验教训

2021-01-24 03:34:23

我们即将迎来LMDB十周年纪念日,而我一直在回想起LMDB出现之前我们一直在努力的缓存调整的糟糕年代。如LMDB设计中所述,文档调整缓存曾经是管理OpenLDAP的主要难题。由于存在至少3个不同的缓存层(每个缓存层具有不同的时空特性),因此这是一种持续的变戏法行为。尽管我们已经摆脱了近十年的负担,但在此之前的几年中,我们获得了很多来之不易的缓存知识。大部分知识不再是操作OpenLDAP所必需的,但是当今仍在使用许多试图管理自己的缓存的软件,并且我们在其他情况下所汲取的教训仍然很有价值。

slapd-ldbm,slapd-bdb和slapd-hdb后端都使用它们自己的应用程序级条目缓存来优化读取性能。这些缓存非常重要,因为基础数据库库(gdbm,bdb,ndbm等)本身执行得很慢。每个LRU:最近最少使用了相同的缓存管理策略。这是最容易理解和最容易实现的方法之一,并且已被广泛记录。

C语言中的典型实现使用双链表。使用缓存元素时,它们会在列表的一端添加,而在达到缓存大小限制时会从列表的另一端删除。再次引用的所有缓存元素将从列表中间的位置拉出,然后添加回末尾。

事实证明,这种数据结构在较高的并发级别下表现非常差。列表的头和尾指针以及每个缓存元素中的指针必须是互斥保护的。服务器中的每个读取操作实际上都会扩展为缓存中的写入操作,从而将条目从其旧位置拉出并固定到新位置。

我们对slapd-bdb / hdb缓存进行的一项重大改进是在2006年用CLOCK取代了这种LRU机制。

从逻辑上讲,它与LRU是相同的策略,但是实现使用循环链接列表。不是将页面弹出其位置并将其固定到末尾,而是有一个指向当前头/尾的时针指针,以及每个条目的“已引用”标志。当引用一个条目时,手将前进到圆圈中的下一个条目。这种方法极大地减少了读取和更新缓存时的锁定开销,从而消除了多线程操作中的主要瓶颈。

重要第一课:如果您在代码中使用普通LRU,请停止。请改用CLOCK。

除了经典的LRU难以实现多线程性能外,它在某些病理情况下根本无法提供任何性能优势。特别地,如果高速缓存具有N个条目的最大大小,并且到达操作序列,则触摸M> M。 N个条目,缓存效率变为零。

例如,给定一个最大大小为4的缓存,以及访问5个条目A,B,C,D和E的请求,该缓存将增长为:

在每个步骤,条目都会添加到缓存中。由于序列中没有重复,因此在执行序列时不会重用任何缓存的条目。在最后一步,由于缓存已满,因此驱逐了条目A,以便为要添加的条目E腾出空间。

如果重复访问此5个条目的序列的操作,则缓存内容将变为

C D E A D E A B E A B C A B C D B C D E

缓存的任何内容都不会再用于服务请求,因为被请求的下一个条目始终是刚才被逐出的条目。在这些情况下,缓存只是浪费时间和内存。

这是LRU及其相关的缓存管理方案的主要弱点。针对此问题提出的解决方案之一是Clock-Pro算法。

使用这些实验算法的困难之一是它们往往是在管理按需分页的操作系统内核中的虚拟内存页的上下文中开发的。内核拥有许多低级的高性能设施,这些设施在用户级应用程序空间中不具有等效功能,或者在用户领域的使用成本较高。在Clock-Pro的情况下,它可能已经在内核空间中工作,但是使其适应用户级别非常不适合。

最终找到了一个更简单的解决方案:如果在请求中访问的条目数超过了缓存的最大大小,则停止将条目添加到缓存中。这使得缓存效率接近100%(缓存中的每个条目都被重用),并且极大地提高了这些病理操作的性能。为了说明与上一示例相同的缓存和操作,缓存的增长与之前几乎相同:

但是,当我们处理条目E时,我们将其丢弃而不是进行缓存。然后,当重复序列时,条目A,B,C和D已经在高速缓存中,并且以基本上为零的成本进行处理。我们只需支付再次获取条目E的费用。在此示例中,重复操作的运行速度比未缓存的操作快5倍。

这种简单的优化之所以可行,是因为我们对正在执行的请求有更高的了解。在采用LMDB并将所有缓存管理留给操作系统方面,我们放弃了这一优势。 (像这样的优势是大多数数据库工程师声称数据库可以比操作系统更好地管理缓存的原因。)实际上,Linux等系统中的内存管理已经超越了简单的LRU,并具有Clock-Pro和其他设计所采用的功能。

因此,至少在Linux上,LMDB并不是缓存性能问题。 Windows上的情况明显更糟,Windows上的内存管理也是如此,但是显然Windows并不是一开始的高性能平台。

重要的第二课:异国情调的解决方案并不总是全部被破解。退后一步,您可能会看到一个更简单的选择。

尽管LRU在某些罕见的极端情况下具有弱点,但总体上仍然表现良好。由于这些结构的性质,对于分层结构的数据尤其如此。例如,给定这样的目录树:

假设缓存大小限制为4,则对cn = Bob,ou = people,dc = example,dc = com的查找将触摸以下条目并将其缓存:

LRU策略自然会退出cn = Carol条目,同时保留其他条目。因此,使用树状结构的数据,您将始终从基于LRU的缓存中获得最大的效率。相同的原理适用于LMDB内部使用的B +树。因为树遍历始终从树的根开始,所以树的根在缓存中将始终是热的,而经常使用的分支在缓存中也将保持热,只有叶子是冷的。因此,面向树的数据结构的自然访问模式本质上可以最大程度地提高系统缓存的效率,而无需任何额外的工作。这就是为什么OpenLDAP仍然是当今世界上最快,最高效的分布式数据库而无需进行缓存调整的原因之一。

在设计最佳缓存算法方面,大量的工作仍在进行中。即使您拥有出色的设计,但要在良好的实现中实现它仍然是一个艰巨的挑战。 (通过查看OpenLDAP中旧缓存代码的提交历史,可以看出需要花多少精力才能正确处理。)对于本地存储的数据,如今最好的缓存管理策略是“让操作系统为您完成。 ”