Cache结构

leveldb中使用的cache是一种LRUcache，其结构由两部分内容组成：

  • Hash table：用来存储数据；
  • LRU：用来维护数据项的新旧信息；

Cache结构 - 图1

其中Hash table是基于Yujie Liu等人的论文《Dynamic-Sized Nonblocking HashTable》实现的，用来存储数据。由于hash表一般需要保证插入、删除、查找等操作的时间复杂度为O(1)。

当hash表的数据量增大时，为了保证这些操作仍然保有较为理想的操作效率，需要对hash表进行resize，即改变hash表中bucket的个数，对所有的数据进行重散列。

基于该文章实现的hashtable可以实现resize的过程中不阻塞其他并发的读写请求。

LRU中则根据Least RecentlyUsed原则进行数据新旧信息的维护，当整个cache中存储的数据容量达到上限时，便会根据LRU算法自动删除最旧的数据，使得整个cache的存储容量保持一个常量。