恒定时间LFU

让任何系统都具有超强性能的一种常见策略是缓存。几乎所有大规模运行的软件产品在其体系结构中都有多层缓存。如果处理得当，缓存确实会影响响应时间，这也是产品在大规模环境下运行良好的主要原因之一。高速缓存引擎受可用内存量的限制，因此一旦内存变满，引擎就必须决定应该逐出哪个项目，这也是LFU和LRU等逐出算法的位置。开始发挥作用了。

LRU(最近最少使用)缓存清除策略是目前最流行的策略之一。LFU(最不频繁使用)策略在某些用例中表现良好，但其最流行的实现(其中使用最小堆)的一个问题是，它为所有三个操作(插入、更新和删除)提供了O(Logn)的运行时间复杂度；因此，它经常被次优但极快的O(1)LRU逐出方案所取代。

本文在Ketan Shah，Anirban Mitra和Dhruv Matani教授关于实现LFU缓存驱逐方案的O(1)算法的基础上，研究了常数时间LFU的实现，其中不使用最小堆，而是使用双向链表和哈希表的组合来获得所有三个核心操作的运行时间复杂度为O(1)。

LFU通常是使用根据每个元素的访问频率组织的最小堆来实现的。该堆的每个元素都保存一个成对的缓存值和访问频率；并且按照该频率的顺序进行组织，以便具有最低访问频率的缓存值位于顶部，从而快速识别要驱逐的元素。

虽然识别要驱逐的元素很快，但是为了让堆保持其属性-访问频率最低的元素位于顶部-它需要重新平衡，并且这个重新平衡过程的运行复杂度为O(Logn)。更糟糕的是，每次更改项的频率时都需要重新平衡；这意味着在实现LFU的缓存中，每次插入、访问或收回项时都需要重新平衡-使得所有三个核心操作的时间复杂度都为O(Logn)。

通过使用一个哈希表和一串双向链表，对于所有三种操作，LFU缓存的复杂度都可以达到O(1)。正如rum猜想所述，为了获得恒定时间的读取和更新操作，我们必须在内存利用率方面做出妥协。这正是我们在此实现中观察到的。

哈希表存储缓存键到保存缓存值的值节点的映射。键的值通常是指向实际值节点的指针。给定哈希表的查找复杂度为O(1)，从该哈希表访问给定关键字的值的操作可以在恒定的时间内完成。

上图描绘了保存高速缓存键K1、K2等的哈希表通过直接指针映射到保存值v1和v2的节点。节点是使用动态分配在堆上分配的，因此有点杂乱无章。键映射到的Value Node不仅保存缓存值，还保存一些指向系统中不同实体的指针，从而实现恒定时间操作。

LFU的这种实现要求我们维护一个双向链接的频率列表，称为freq_list，为跨越所有缓存值的每个唯一频率保存一个节点。该列表按节点表示的频率保持排序，使得表示最低频率的节点在一端，而表示最高频率的节点在另一端。

每个频率节点保存它在成员FREQ中表示的频率以及指向相邻频率节点的通常的NEXT和PREV指针；它还保持指向另一个双向链表的VALUES_PTR，该值列表保存具有相同访问频率FREQ的值节点(在哈希表中引用)。

双向链表的总体示意图及其排列如上图所示。存放频率节点的双向链表水平排列，而存放值节点的列表垂直排列，以便更清晰地查看和理解。

由于缓存值v1和v7都被访问了7次，因此它们都链接在双向链表中，并与代表频率7的频率节点挂钩。类似地，持有值v5、v3和v9的值节点也链接在另一个双向链表中，并与代表频率18的频率节点挂钩。

Value Node包含成员数据中的缓存值，以及通常指向列表中相邻值节点的NEXT和PREV指针。它还持有指向列表所挂接到的频率节点的freq_Pointer。拥有所有这些指针可以帮助我们确保所有三个操作都在恒定的时间内进行。

现在我们已经准备好了所有必要的结构，接下来我们来看一下3个核心操作及其伪实现。

向缓存添加新值是一个相对简单的操作，它需要一系列指针操作，并以恒定的时间运行复杂性完成这项工作。在缓存中插入值时，我们首先检查表中是否存在键，如果键已经存在，并尝试再次放置它，则函数将引发错误。然后，我们确保存在代表频率1的频率节点，并且在此过程中，我们可能还需要创建一个新的频率节点。然后，我们将值包装在一个Value Node中，并将其添加到此Frequency节点的VALUES_LIST中；最后，我们在表中创建一个条目，确认缓存过程已完成。

Def(key：str，value：object)：#检查表中是否已经存在键，#如果是，则返回错误，如果键在表中：Raise KeyAlreadyExistsError#持有所有必需的指针value_node=make_value_node(Value)first_Frequency_node=freq_list.head if first_Frequency_node.freq！=1：#由于freq_list中的第一个节点不代表#Frequency of 1，我们创建一个新节点first_Frequency_node=make_Frequency_node(1)#更新保存所有频率节点#的`freq_list`，使得第一个节点表示频率1#，而其他列表保持不变。First_requency_node.next=freq_list.head freq_list.head.prev=first_Frequency_node freq_list.head=first_Frequency_node#value节点指向其所属的频率节点value_node.freq_Pointer=first_Frequency_node#在`first_Frequency_node`first_Frequency_node.values.add(Value_Node)中添加值节点#更新哈希表[key]=value_node中的条目

从上面的伪代码中可以看出，在缓存中添加新值的整个过程是一堆内存分配以及一些指针操作，因此我们观察到此操作的运行复杂度为O(1)。

逐出(与插入类似)是一个琐碎的操作，我们只需选取访问频率最低的频率节点(freq_list中的第一个节点)，然后删除其valueslist中出现的第一个value Node。由于整个逐出过程还需要指针操作，因此其运行复杂度也为O(1)。

Def()：if freq_list.head and freq_list.head.value：first_value_node=freq_list.head.values.first Second_Value_node=first_value_node.next#将第二个元素设为first freq_list.head=Second_Value_node#确保第二个节点没有悬空的Prev链接Second_Value_node.prev=None#如果freq_list.head和#删除第一个元素delete_value_node(First_Value_Node)，则删除第一个元素DELETE_VALUE_NODE(FIRST_VALUE_NODE。Head.values：#如果逐出后的Frequency Node没有保存#我们去掉它的任何值delete_Frequency_node(freq_list.head)。

从高速缓存访问项必须是任何高速缓存中最常见的操作。在LFU方案中，在返回缓存值之前，引擎还必须更新其访问频率。确保更改一个缓存值的访问频率不需要进行某种重新平衡或重构来维护完整性，这就是此实现的特殊之处。

引擎首先对哈希表进行GET调用，以检查缓存中是否存在该键。在从检索到的值节点返回缓存值之前，引擎执行以下操作-它访问与检索到的值节点对应的频率节点及其同级节点。它确保同级节点的频率比频率节点的频率高1；如果不是这样，它会创建必要的频率节点，并将其放置为新的同级节点。然后，Value Node更改其与此同级频率节点的关联性，以使其正确匹配访问频率。最后，设置从Value Node到新Frequency Node的反向指针，并返回值。

Def(key：str)->；object：#从哈希表获取Value Node value_node=table.get(key，one)#如果缓存中不存在该值，则返回错误#声明未找到key if not value_node：raise KeyNotFoundError#我们使用#freq_Pointer成员从值节点获取频率节点。FREENCY_NODE=VALUE_NODE.freq_POINTER#我们还将下一个频率节点获取到当前的#频率节点，以便我们可以调用#需要创建一个新节点。Next_Frequency_node=Frequency_node.next if next_Frequency_node.freq！=Frequency_node.freq+1：#新建频率节点new_Frequency_node=make_Frequency_node(Frequency_node.freq+1)#将频率节点放在列表Frequency_node.next中的正确位置。next=new_Frequency_node new_Frequency_node.prev=Frequency_node next_Frequency_node.prev=new_Frequency_node new_Frequency_node.prev=new_Frequency_node new_Frequency_node.prev=new_Frequency_node new_Frequency_node.prev=new_Frequency_node new_Frequency_node.prev=new_Frequency_node new_Frequency_。将新的频率节点称为Next#，因为它代表下一个频率节点Next_Frequency_node=new_Frequency_node#我们在neX Next_Frequency_node.values.add(Value_Node)中添加值Node#我们将父节点和形容词节点更改为此值节点value_node.freq_Pointer=Next_Frequency_node value_node.next=None value_node.prev=next_Frequency_node.values.last#如果频率节点没有元素，则删除。如果len(Frequency_node.values)==0，则内存泄漏：delete_Frequency_node(Frequency_Node)#返回值返回值_node.value。

同样，由于此操作也只处理通过直接指针的指针操作，因此此操作的运行时间复杂度也是恒定的时间。因此，我们可以看到恒定时间LFU实现，其中通过使用哈希表和双向链表来实现必要的时间复杂度。

如果你喜欢你所读的内容，订阅，你可以随时订阅我的时事通讯，并将帖子直接送到你的收件箱。我写各种工程主题的文章，并通过我的每周时事通讯👇与人分享。

一致性散列是设计高伸缩性的散列技术中最受欢迎的技术之一。

异常检测是一个由来已久的问题，在本文中，我们将深入研究一种无监督的算法...。

写时复制用于建模时间旅行，构建没有锁的数据库，并使分叉系统...