合适以及为何使用最少使用(LFU)缓存与Golang中的实现

[译]合适以及为何使用最少使用(LFU)缓存与Golang中的实现

在过去的这些年,参与计算机科学和工程师的人们一直在努力优化各种性质。我们生活在一个资源有限的世界里,人们一直致力于优化成本和速度的方法。

在软件工程方面而言,我认为,最流行的改善性能的就是缓存了。在许多app都有缓存,依赖于软件方面的存储,缓存背后的想法非常简单。为了加载较快,存储数据经常被用到。

事实上,缓存必须在两个方面很快

  1. 确保尽可能多的文件请求(缓存命中),而不是通过网络或者主内存(没有命中)
  2. 使用它的开销应该比较小,测试人员决定何时更换文件

在这篇文章中,我们将会关注第二部分。对最不常用的缓存采取特定的实现方法,并使成员资格测试和驱逐算法具有良好的性能。并且,我们还将介绍基础知识并探究这种缓存方案可用的地方。

基础

LFU是一种缓存算法。只要达到缓存的容量限制,就会删除缓存中最不常用项。这意味着对于缓存中的每个项目,我们必须跟踪它的使用频率。一旦超过了容量,讲运用驱逐算法,从缓存中挑选和过期(移除)项目。

如果你之前实现过LFU缓存,你可能已经考虑使用最小堆数据结构。因为它对数时间复杂度处理插入,删除和更新。在这篇文章中,我们将介绍另一种实现它的方法。

但在我们进入实施之前,让我们看看LFU在哪些情况下比替代品更好。

LFU闪耀点

想象一下CDN上的资产缓存,其中资产根据使用模式进行缓存。因此,当用户在网页上请求加载一些图片时,此CDN会将其添加到缓存中,以便其他用户更快获取它。

例如,一个这样的图像(资产)是网站的标志,你能想象一天有多少次谷歌的标识被要求在他们的所有产品上。我真的很想找到这个数字,但就目前而言,我们可能会认同这个数字是庞大的。

这种资产缓存是LFU缓存的完美用例。LFU缓存逐出算法永远不会驱逐频繁访问的资产。事实上,在这样的缓存中,谷歌的微标几乎将永远缓存,相比之下。如果由于Reddit,Slashdot和Hackernews首页上的新产品的新登录页面而有任何图像将会访问,一旦超级风暴过去,资产将被驱逐得更快,因为访问频率将急剧下降,尽管在过去几天他们已经被访问过很多次。

正如你可能已经注意到的那样,在缓存对象的访问模式不经常更改的情况下。这种缓存逐出的方法非常有效。虽然LRU缓存将驱逐最近无法访问的资产,但LFU驱逐方法将在炒作结束后逐出不再需要的资产。

实现LFU缓存

现在,让我们来了解它,如我们之前所说的。我们不是将min-heap视为可能支持LFU缓存的可能数据结构,而是考虑采用更好的方法。

事实上,在2010年,一组研究人员Ketan Shah教授,Anirban Mitra和Dhruv Matani发表了一篇题为“用户实现LFU缓存驱逐方案的O(1)算法”的文章(你可以点击这里查看),在这文章中他们解释LFU缓存的实现,其运行的时间复杂度为O(1),用于其所有操作,包括插入,访问,和删除(驱逐)。

在此,我将向你展示如何实现此缓存并引导你完成实现。

数据结构

不,它不会是某种科学怪人的红黑树,事实上,它是两个双向链表和一个哈希表。是的,就是这样。

为了能够理解LFU实现的基本原理,让我们将链表和哈希表看做图形。在我们查看实际图形之前,我们需要了解如何使用哈希表和链接列表。

哈希表将使用通过哈希算法处理的密匙存储所有项目(为了我们的目的,我们 可以保持简单),值将是实际项目。

key

链表有点复杂,第一个将是”频率列表“,它将具有所有访问频率。此列表中的每一个节点都有一个项目列表。该列表将包含已使用相应频率访问的所有项目。此外,项目列表中的每一个项目都会在频率列表中指向其祖先。

item

如果我们查看上面的图形例子,我们可以注意到项A,B,C和D已被访问过一次。E和F项已被访问过4次,依据类推。蓝线是项列表中的每个项都与频率列表中的祖先有关的指针。

那么,如果再次访问项E会发生会发生什么?让我们完成以下步奏:1. 从哈希表中检索项很容易(并且很好地扩展)O(1)。 2. 我们将访问项的frequencyParent指针,从中我们可以检查列表中的下一个频率是什么。3. 如果存在新频率(列如8),我们将其作为频率节点8下的项目列表的第一项。4. 如果新频率不存在,我们将创建频率节点8并将节点8添加E到项列表中.

就是这样,检索项并刷新项的频率是O(1),在我们开始实现访问算法前,让我们首先建立我们需要的基本类型。

类型

如我们之前所说,我们需要对所需的类型进行建模,这些类型将成为我们缓存的主干。

第一个结构将是CacheItem,这将是将存储在缓存中的实际项目。

1
2
3
4
5
6

type CacheItem struct {
key string // Key of entry
value interface{} // Value of item
frequencyParent *list.Element // Pointer to parent in cacheList
}

它包含我们可以在哈希表中查找它的键,值是实际的缓存项,以及指向频率列表中的frequencyParent指针。

下一个结构是FrequencyItem,它表示频率列表中的每一个项。它包含一组条目,这些条目将是一组CacheItem指针,我们将使用map来存储它,以便我们可以将其视为一个集合,它只包含唯一的项。

1
2
3
4
5

type FrequencyItem struct {
entries map[*CacheItem]byte // Set of entries
freq int // Access frequency
}

我们需要具有平滑运行缓存的最后一个结构就是Cache本身。

1
2
3
4
5
6
7

type Cache struct {
bykey map[string]*CacheItem // Hashmap containing *CacheItems for O(1) access
freqs *list.List // Linked list of frequencies
capacity int // Max number of items
size int // Current size of cache
}

Cache将包含hash键,称为bykey(命名来自上面链接的文件),频率列表称为freqs,缓存的最大容量称为容量,缓存的大小表示任何给定缓存的项目数时刻。

New, set & get

让我们看看使缓存工作所需的前三个函数。第一个是一个小构造函数:

1
2
3
4
5
6
7
8
9
10

func New() *Cache {
cache := new(Cache)
cache.bykey = make(map[string]*CacheItem)
cache.freqs = list.New()
cache.size = 0
cache.capacity = 100

return &c
}

构造函数New将创建一个新的Cache结构,并将所有默认值设置为它。如果你想知道list.New()是如何工作的:对于频率列表,我们将使用Go的容器/列表包,其中包含一个整洁的链表实现。你可以查看其文档以获取更多详细信息。

将在Cache上实现的第二个函数是Set函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
// Increment item access frequency here
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
// Eviction, if needed
// Increment item access frequency
}
}

该函数将缓存键和实际值/项缓存为参数。然后,它检查项目是否已经缓存。如果它被缓存,它只会更新项目的值。否则,它将创建一个新的CacheItem,它将封装实际值,它将设置密钥,它将把项添加到bykey哈希表,它将增加缓存的大小。

现在,在两个逻辑分支中,我为缺失的部分添加了一些注释:1。缓存必须知道如何增加aCacheItem的访问频率,但我们还没有实现它; 2.如果大小达到容量,缓存必须知道如何根据访问频率逐出项目。

我们将保留这些注释,直到我们实现增量和逐出函数。

Cache将接收的第三个函数是Get - 通过哈希表中的键访问项目并返回它:

1
2
3
4
5
6
7
8
9

func (cache *Cache) Get(key string) interface{} {
if e, ok := cache.bykey[key]; ok {
// Increment acess frequency here
return e.value
}

return nil
}

这里也没有魔法 - 我们检查bykey散列表是否包含带有key参数的值,如果存在则返回它。否则,我们返回零。在这里,就像在Set中一样,我们将保留占位符注释,一旦我们实现它就必须添加频率增量函数调用。

更新访问频率

正如我们已经看到的,对于缓存的每个访问操作,我们必须更新所访问项的访问频率。

让我们看一下我们的Increment函数必须采取的步骤。首先,对于要过期的项目,我们将不得不决定该项目是否已经是哈希表和频率列表的一部分。如果是,我们将不得不在频率列表中找到它的新频率值和下一个频率位置(节点)。

其次,我们必须弄清楚对于新频率,频率列表中是否已经存在节点。如果有,我们将不得不将该项添加到其条目列表中并分配其新的访问频率(即当前访问频率+ 1)。如果没有,我们将不得不在频率列表中创建一个新的频率节点(并设置其所有合理的默认值),然后将该项添加到其条目列表中

第三,一旦我们检测到FrequencyParent,我们的函数就必须将新的父项设置为正在递增的项,并将其添加到父项的列表中。

作为最后一步,增量函数将从旧频率节点(frequencyParent)的条目中删除该项目。

这是Golang代码:

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

func (cache *Cache) increment(item *CacheItem) {
currentFrequency := item.frequencyParent
var nextFrequencyAmount int
var nextFrequency *list.Element

if currentFrequency == nil {
nextFrequencyAmount = 1
nextFrequency = cache.freqs.Front()
} else {
nextFrequencyAmount = currentFrequency.Value.(*FrequencyItem).freq + 1
nextFrequency = currentFrequency.Next()
}

if nextFrequency == nil || nextFrequency.Value.(*FrequencyItem).freq != nextFrequencyAmount {
newFrequencyItem := new(FrequencyItem)
newFrequencyItem.freq = nextFrequencyAmount
newFrequencyItem.entries = make(map[*CacheItem]byte)
if currentFrequency == nil {
nextFrequency = cache.freqs.PushFront(newFrequencyItem)
} else {
nextFrequency = cache.freqs.InsertAfter(newFrequencyItem, currentFrequency)
}
}

item.frequencyParent = nextFrequency
nextFrequency.Value.(*FrequencyItem).entries[item] = 1
if currentFrequency != nil {
cache.remove(currentFrequency, item)
}
}

让我们回顾一下频率和条目列表的原始图表,并逐步增加E项目。

E

我们的增量函数将采用的第一步是分配一个指向节点4(frequencyParent)及其值(即4)的指针。由于节点4存在于列表中,它将在频率列表中找到下一个节点,在我们的例子中是节点7。

一旦它确定E节点的新频率应为5而不是7,它将在节点4和7之间的列表中追加一个新的频率节点:

new

将5节点添加到列表后,该函数将设置节点正常运行所需的默认值。然后它会将E的指针设置为新的frequencyParent(5节点):

parent

作为最后一步,它将采用具有指针* CacheItem类型的项目,并将其添加到条目列表,同时从先前的frequencyParent的条目列表中删除它:

让我们看看从FrequencyItem的条目列表中删除CacheItem的步骤是什么。

删除条目

一旦我们知道列表中我们想要删除它的节点,我们就可以从条目列表中删除该项,如果条目变空,还可以从频率列表中完全删除FrequencyItem:

1
2
3
4
5
6
7
8

func (cache *Cache) Remove(listItem *list.Element, item *CacheItem) {
frequencyItem := listItem.Value.(*FrequencyItem)
delete(frequencyItem.entries, item)
if len(frequencyItem.entries) == 0 {
cache.freqs.Remove(listItem)
}
}

驱逐

拼图的最后一部分是逐出,或者换句话说,一旦缓存达到其最大容量,就删除最不常用的项目。

我们必须知道我们想要驱逐多少项。通常,我们的缓存将具有低限和高限,因此当达到上限时,我们将删除项目直到下限。在我们的例子中,我们将驱逐任意数量的项目,Evict函数将作为参数。

该功能将从开始到结束开始“遍历”频率列表。由于频率列表是按升序排列的,因此它将开始从第一个频率节点开始删除条目,直到它删除与传入的任意数字一样多的项目。

如果频率节点由于逐出而不包含条目,则Evict函数也必须从频率列表中移除频率节点。它将通过调用Remove函数来实现。这样,驱逐就不会留下任何垃圾。

这是我们上面描述的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

func (cache *Cache) Evict(count int) {
for i := 0; i < count; {
if item := cache.freqs.Front(); item != nil {
for entry, _ := range item.Value.(*FrequencyItem).entries {
if i < count {
delete(cache.bykey, entry.key)
cache.Remove(item, entry)
cache.size--
i++
}
}
}
}
}

回到Set and Get

在本文开头,我们实现了Set和Get函数。那时我们没有的东西是Evict和increment函数,所以我们可以相应地使用它们。让我们添加他们的调用。

增加访问频率

在Get函数中,如果我们在bykey哈希表中找到一个项目,我们需要在继续返回其值之前增加它的访问频率:

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

func (cache *Cache) Get(key string) interface{} {
if e, ok := cache.bykey[key]; ok {
cache.increment(e)
return e.value
}

return nil
}

``

通过此更改,Cache将在返回之前增加该特定项的频率。但是,我们忘了什么吗?此外,Set函数在实际缓存它们时访问缓存的项目。这意味着当一个项被缓存时,它将立即被添加到频率列表中,值为1的节点下:

```go

func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
cache.increment(item)
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
// Eviction, if needed
cache.increment(item)
}
}

在驱逐后

Set函数允许我们的LFU Cache用户在其中缓存更多项目。任何缓存的一个关键组件是,当新项目添加到缓存时,它应该知道如何逐出项目(释放空间)。对于LFU缓存,当缓存达到容量时,需要删除最不常用的项。

让我们首先添加一个函数,如果缓存达到其最大容量,它将返回一个bool:

1
2
3
4

func (cache *Cache) atCapacity() bool {
return cache.size >= cache.capacity
}

功能很简单:检查Cache的当前大小是大于还是等于容量。

现在,让我们在Set函数中使用它。一旦我们在缓存中设置了新项目,我们就必须检查缓存是否已达到其容量,然后从中删除多个项目。

为简单起见,我们每次达到最大容量时只会删除10个项目:

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

func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
cache.increment(item)
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
if cache.atCapacity() {
cache.Evict(10)
}
cache.increment(item)
}
}

通过此更改,如果在任何时候添加项目达到缓存的容量,缓存将驱逐最不常用的项目。

通过此更改,如果在任何时候添加项目达到缓存的容量,缓存将驱逐最不常用的项目。

如果您想查看本文的完整代码,可以查看

关于缩放和时间复杂性的评论

LFU是一个有趣的驱逐计划,特别是与LRU相比,在我看来,由于其非常规性质。虽然其应用受到限制,但由于该方法的扩展能力,本文中使用的论文中解释的算法和后备数据结构非常吸引人。

如果我们重新阅读本文开头提到的论文,我们将看到虽然LFU不是新闻,但它传统上是使用min-heap实现的,它具有插入,查找和删除的对数时间。有趣的是,在本文中,作者解释说,他们提出的方法对于每个操作(插入,查找和删除)都具有O(1)时间复杂度,因为操作基于哈希表。此外,链接列表不会增加任何时间复杂度,因为我们不会在任何时候遍历列表 - 我们只是在需要时添加或删除其中的节点(这是一个O(1)操作)。

总结

在本文中,我们了解了LFU缓存的基础知识。我们确定了最重要的绩效指标(命中率,成员资格和驱逐速度)。我们看到虽然它不是最广泛使用的缓存方案,但在某些用例中肯定会非常高效。

然后我们继续实施它,使用一种在时间复杂度方面可以很好地扩展的方法。我们看到了实施驱逐和频率增量算法的复杂性。最后,我们进一步探讨了我们用于实现它的方法如何扩展。

如果您想阅读有关该主题的更多信息,请参阅以下几个链接,以丰富您对LFU缓存和缓存的了解:

本文翻译自–原文

分享到 评论