Photo by Brina Blum on Unsplash

多半情况下,LRU 会和 哈希表 一起使用,然后我们把这个组合称为 LRU-cache

LRU-cache 中, 哈希表 提供快速索引的功能; 而 LRU 则是将 最近最少使用 (least recently used) 的元素在适当的时机标记为过期,并予以删除,用来防止缓存无限增大。本篇我们主要看 哈希表 的实现。

概述 (课本都讲过了, 跳过

哈希表 本质上是一块 固定大小 的数组。数组的索引是由哈希生成的整形。在 哈希表 中,这个数组的元素也被称作 ,以区别于 哈希表 本身的元素,item。当然,如果生成的索引超过 的数量,则取模之。如果两个 键值哈希 成同一个整形索引值,或者两个索引值被取模后的值刚好相同,则 冲突 发生。 所以一般做法是在每个 上建立一个链表来存储所有 冲突 于此的键值对。

需要提一下,冲突 会降低 哈希表 的查找速度,原因很简单,因为要遍历链表 O(n)。处理方法也很简单,把数组大小扩容,然后重新对所有的元素进行 重新哈希,因为 的数量增加了,冲突 也就减少了,而由 冲突 所形成的链表也就变少或变短了。 当然,重新哈希 的代价很大,所以一般是在性能实际下降时严重时才会发起。具体过程很快会就会讲到 …


Photo by Matthew T Rader on Unsplash

Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.

Slab I
Slab II
Slab III
LRU I
LRU II
LRU III
Event driven I
Event driven II
Event driven III (this article)

We continue examining the other two operations, i.e., create and delete, in the event-driven context. …


多半情况下, LRU 会和 哈希表一起使用,然后我们把这个组合称为

LRU 缓存

LRU缓存 中,哈希表提供了快速随机访问对象的能力;而 LRU(算法)则用于淘汰 很久没用 ( least recently used) 的对象,来避免缓存无限增加。我们先大致看下 LRU 组成。

链表

从技术上来说, LRU 算法是在链表上完成的 — 当一个表项被使用(访问或更新), LRU 会先做移除,然后把它重新插入到表头。这样,越接近表尾的对象就是 越久没使用 ( least recently used),淘汰起来比较简单。

哈希表

链表是不支持快速的随机访问的,所以需要和 哈希表 一起使用。之前我们之前已经读过, 子系统的空闲列表是通过链表把 里的 (chuck) 串起来形成的。在 LRU缓存 里也差不多,而这次用链表 …


Photo by Sharon McCutcheon on Unsplash

上次我们看完了内存分配,以及形成待分配列表(free list,即slots)的过程。本篇我们继续查看如何使用建立好的数据结构来分配/回收块内存,并将它们用于存储对象

首先,我们来看

do_slabs_alloc

这个函数对应讨论过的do_slabs_free.

这里do_slabs_alloc的“公有”接口是slabs_allocslabs_alloc除了提供了对外接口外,还对核心数据结构加了线程锁以保证此函数(在Memcached被配置为多线程时,multithreaded)线程安全。

static void *do_slabs_alloc(const size_t size, unsigned int id, unsigned int *total_chunks,
unsigned int flags …

这次我们继续看用于 Slab 的内存是如何分配的。

首先我们继续看 slabs_init 的两个实参。第一个是 settings.maxbytes — 控制这个 Memcached 实例可以使用的总内存大小。在传入 slabs_init 之前,这个参数被赋值为全局变量 mem_limit

另外一个怎是 preallocate。它决定了是否为(各个)Slab组 预分配 内存。这个参数的值由 L 命令行参数来决定。

下面我们来看 slabs 的内存分配函数。

New slab

具体来说,这个函数用于给 Slab组 分配大小为1M的内存块(slab)。而 Slab组 由参数 id 指定。

static int do_slabs_newslab(const unsigned int id) {
slabclass …

Photo by Brooke Lark on Unsplash

Slab分配器是这个缓存系统的核心,并在很大程度上决定了核心资源 — 内存 — 的利用效率。其它的三个部分,用来淘汰(超时)对象的LRU算法;和基于libevent的事件驱动;以及用于分布数据的一致性哈希,可以看作是围绕Slab来开发的。

在其他系统,比如内核,都能看到 Slab 分配器 的身影。无论它出现在哪里,都是为了对抗同一个性能问题,内存碎片。而本文就主要讨论 Slab 分配器 在memcached 中的实现(废话)。

memcached version: 1.4.28

首先我们来回答一些问题。

前言

Slab翻译过来就是(一块)板子,具体来说,它是是被预先分配好的,大小为1M的内存块。这些板子可以被进一步分割成一些相同大小的小块,对象就存写在每一个小块上面。板子们会根据所存储对象的大小分成Slab组


Photo by Toa Heftiba on Unsplash

Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.

Slab I
Slab II
Slab III
LRU I
LRU II
LRU III
Event driven I
Event driven II (this article)

In classic multithreading, blocking I/O operations constrain the maximum number of requests a server can handle. Hence asynchronous event driven model is used to eliminate the throughput bottleneck. …


Photo by NeONBRAND on Unsplash

Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.

Slab I
Slab II
Slab III
LRU I
LRU II
LRU III
Event driven I (this article)

In classic multithreading, large amounts of slow and blocking operations, mostly, I/O, can easily drain out available thread resources, which severely constrains the maximum number of requests a server can handle per…


Photo by Velizar Ivanov on Unsplash

Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.

Slab I
Slab II
Slab III
LRU I
LRU II
LRU III (this article)
Event driven I

In previous posts, we have discussed different facets of an item, i.e., slab, hash map and LRU list as well as their associated (CRUD) methods, which build up the internal procedures and…


Photo by Brina Blum on Unsplash

Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.

Slab I
Slab II
Slab III
LRU I
LRU II (this article)
LRU III
Event driven I

More often than not, the LRU algorithm is combined with a hash map, and is referred to as a LRU cache.

In a LRU-cache, the hash map enables fast accessing of cached

Holmes He

a practical idealism https://holmeshe.me

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store