合适以及为何使用最少使用(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
7

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
6

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

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

1
2
3
4
5
6
7
8

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
11

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
16

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
10

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
32

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
9

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
16

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
31

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
5

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
18

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缓存和缓存的了解：

本文翻译自–原文

分享到 评论