open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  • Abstract
  • Introduction
  • Uses of LFU
  • Dictionary Operations Supported by An LFU Cache
  • The Currently Best Known Complexity of the LFU algorithm
  • The Proposed LFU Algorithm
  • Set
  • Get
  • EvictOne
  • 参考
  1. Papers We Love

LFU Implementation With O(1) Complexity (2010)

An O(1) algorithm for implementing the LFU cache eviction scheme

PreviousDynamic Hash Tables (1988)NextTime, Clocks, and the Ordering of Events in a Distributed System (1978)

Last updated 5 years ago

Abstract

缓存置换算法 (Cache Eviction Algorithm) 在操作系统、数据库以及其它系统中被广泛用于缓存置换模块,当缓存空间不足时,它利用局部性原理 (Principle of Locality) 预测未来数据的使用模式,将最不可能被访问的数据清出从而提高缓存命中率。目前已经存在的缓存置换算法包括 MRU (Most Recently Used)、MFU (Most Frequently Used)、LRU (Least Recently Used) 以及 LFU (Least Frequently Used) 等。每个算法都有其各自的适用场景。到目前为止,应用范围最广的是 LRU,主要原因在于 LRU 贴近大多数应用的实际负载模式 (workloads),同时 LRU 拥有O(1)O(1)O(1) 时间复杂度的成熟实现方案。与 LRU 类似,LFU 同样与大多数应用的负载模式相近,但目前 LFU 最佳实现方案的时间复杂度是O(log2n)O(log_2{n})O(log2​n) ,不如 LRU。本文,我们提出一种同样达到O(1)O(1)O(1)时间复杂度的 LFU 实现方案,它支持的操作包括插入、访问以及删除。

Introduction

本文将按顺序介绍:

  • LFU 的典型使用场景

  • LFU 的接口说明

  • 目前 LFU 的最佳实现方案

  • 时间复杂度为O(1)O(1)O(1) 的 LFU 实现方案

Uses of LFU

LFU 的一个典型使用场景就是 HTTP 的缓存代理应用 (caching network proxy application)。它位于网络服务与用户之间,如下图所示:

它通过将大多数用户可能请求的静态文件放入缓存中,来优化网络利用率,提高服务的响应速度。这种缓存代理需要满足:

  1. 在有限的存储资源中缓存尽可能多的、更可能被重复使用的数据

  2. 实现的成本应该尽可能小,保证代理在高负荷下也能正常工作

当缓存空间占满时,我们需要尽可能地将那些使用频率最低的资源清理出去 (eviction),这恰好符合 LFU 的定义。LRU 也许也是一个不错的选择,但在特定场景下,如轮流地访问 (round-robin fashion) 一连串不同的数据导致缓存不断地被置换,LRU 将可能失效。

Dictionary Operations Supported by An LFU Cache

LFU 的接口如下所示:

type LFU interface {
    // 放入键值数据
    Set(k string, v interface{})
    // 用键查值
    Get(k string) (v interface{}, ok bool)
    // 清出使用频率最低的键值对
    EvictOne(n int)
}

The Currently Best Known Complexity of the LFU algorithm

在此论文发布之时,当前的 LFU 最佳实现方案满足:

它通过 binomial heap 和 hash table 这两个抽象数据类型 (Abstract Data Type, ADT) 组合实现,它们的具体实现可以是 min-heap 和 hash-map:

  • min-heap:以访问次数为值

  • hash-map:以缓存的键,如 url 为键,以缓存的数据,如 html 文件为值,建立 hash-map

  • Set:

    • 放入 hash-map 中

    • 记录使用频次为 1,插入到 min-heap 中

  • Get:

    • 从 hash-map 中取数据

    • 将 min-heap 中它的使用频次自增 1,然后调整 min heap,使其恢复不变性

  • Eviction:

    • 从 min-heap 顶部取出访问频次最小的数据,并调整 min heap,使其恢复不变性

    • 从 hash-map 中删除相应键值数据

The Proposed LFU Algorithm

本文提出的 LFU 通过一个两级 Doubly Linked List 和一个 Hash Map 来实现,其基本结构如下图所示:

我们将两级 Doubly Linked List 分为横向和纵向,具体说明如下:

  • head 与横向 Doubly Linked List 相连,后者的节点由近及远地、从低到高地存储访问频次数据

  • 横向 Doubly Linked List 中的每个节点都指向一个纵向 Doubly Linked List

  • 纵向 Doubly Linked List 中的节点存储的是出现频次相同的元素,且每个节点都维护着一个指向其对应的横向 Doubly Linked List 节点的指针。

以上图为例:

  • 元素 x、y 都只被访问 1 次

  • 元素 z、a 都只被访问 2 次

  • 元素 b 被访问 5 次

  • 元素 c 被访问 9 次

  • 通过键 kx 可以找到位于频度为 1 的纵向 Doubly Linked List 的节点 x,而通过 x 又能访问其对应的横向 Doubly Linked List 的节点 1

下面我们分析其 3 个核心 API 的算法复杂度。

Set

func (c *cache) Set(k string, v interface{}) {
    // 如果没有频率为 1 的纵向 Doubly Linked List,则新建一个,并插入 kv 数据
    // 如果有,直接将 kv 数据插入其中
    var item *kvItem
    if c.horizontalDDL.Len() == 0 || c.horizontalDDL.first.freq != 1 {
        node := &DDLNode{
            freq: 1,
            verticalDDL: NewDDL(),
        }
        
        item = &kvItem{
            k: k,
            v: v,
            parent: node,
        }
        node.verticalDDL.PushFront(item)
        c.horizontalDDL.PushFront(node)
    } else {
        item = &kvItem{
            k: k,
            v: v,
            parent: c.horizontalDDL.first,
        }
        c.horizontalDDL.first.vertialDDL.Push(item)
    }
    
    // 插入 kv 到 Hash Map 中
    c.hashMap[k] = item
    return
}

Get

func (c *cache) Get(k string) (vv interface{}, ok bool) {
    // 如果 k 不在 Hash Map 中,则返回
    v, ok := c.kv[k]
    if !ok {
        return
    }
    
    // 如果 k 在,则找到其对应的纵向 Doubly Linked List 节点 vNodeK
    // 假设 vNodek 对应的横向 Doubly Linked List 节点 hNodeK 的频率为 freq
    // 将 vNodek 移动到 freq + 1 的纵向 Doubly Linked List 上即可
    vNodeK = v
    hNodeK = v.parent
    
    if hNodeK.next.freq != hNodeK.freq+1 {
        node := &DDLNode{
            freq: hNodeK.freq+1,
            verticalDDL: NewDDL(),
        }
        hNodeK.verticalDDL.Remove(vNodeK)
        node.verticalDDL.PushFront(node)
        c.horizontalDDL.InsertAfter(hNodeK, node)
    } else {
        hNodeK.verticalDDL.Remove(vNodeK)
        hNodeK.next.vertialDDL.PushFront(vNodeK)
    }
    
    return
}

EvictOne

func (c *cache) EvictOne() {
    // 取出频度最小的纵向 Doubly Linked List
    front := c.horizontalDDL.first.vertialDDL.RemoveFront()
    // 从 Hash Map 中删除其对应的键值对
    delete(c.kv, front.k)
    return
}

参考

Set: O(logn)O(logn)O(logn)

Get: O(logn)O(logn)O(logn)

EvictOne: O(logn)O(logn)O(logn)

hash-map 的时间复杂度可以看作是 O(1)O(1)O(1) ,因此整个 LFU 算法的复杂度受制于 min-heap 的时间复杂度。下面我们逐个分析:

由于 Set 操作只涉及频度为 1 的纵向 Doubly Linked List,因此时间复杂度为 O(1)O(1)O(1) 。

Hash Map 访问的时间复杂度为 O(1)O(1)O(1) ,更新 Doubly Linked List 只涉及相邻的两个横向节点及其对应的纵向 Doubly Linked List,因此时间复杂度 O(1)O(1)O(1)。因此 Get 的时间复杂度为O(1)O(1)O(1)。

EvictOne 时,只需要从频度最小的纵向 Doubly Linked List 上删除任意元素即可,其时间复杂度为O(1)O(1)O(1);Hash Map 删除的时间复杂度为O(1)O(1)O(1),因此 EvictOne 的时间复杂度为O(1)O(1)O(1)。

An O(1) algorithm for implementing the LFU cache eviction scheme
Github: ZhengHe-MD/lfu