由于查询内存要远比查询mongo数据库快,为了减少数据库查询压力,提升业务进程处理速度,实现了一个简单的lrucache,笔记链接LRU算法C++实现。内存相对于磁盘永远是奢侈品,但随着时代的发展,现在的服务器动辄32G 64G起步,分出几个G来提高访问速度是必要的。计算机中有个比较有意思的现象,要么以时间换空间,要么以空间换时间,LRU算法则属于后者。
QQ group里听某位大哥说google leveldb中有一套非常经典的lrucache实现,心向往之,周日跑了一天的装修后,晚上一边泡着脚一边github上拉下来代码研究下。
首先是leveldb的安装,网上找了一些安装方法,差不多都过时了,正确的安装方法:

git clone --recursive https://github.com/google/leveldb.git
mkdir -p build && cd build
cmake -DCMAKE_BUILD_TYPE=Release .. && cmake --build .

这里主要有几个错误需要注意,首先是CMak版本过低会报错,其次是clone代码时需要clone子模块。
在build目录下生成了一个静态库libleveldb.a, 我们把这个静态库复制到/usr/local/lib/, 并把leveldb相关的头文件复制到/usr/local/include/

sudo cp build/libleveldb.a /usr/local/lib/
sudo cp -r include/leveldb/ /usr/local/include/

至此,leveldb安装成功,可以找些例子编译验证。编译命令:

g++ -std=c++11 -o example example.cc -pthread -lleveldb 

代码整体框架

几个关键的数据结构:

LRUHandle
HandleTable
LRUCache
ShardedLRUCache

学习代码实现中的一些知识点:

nullptr

nullptr
Understanding nullptr in C++

在C语言中,空指针可以使用(void *)0;来表示,且标准库中也是如此定义,但在C++语言中,由于对语法的类型检查更为严格,因而空指针的值就不能表示为(void *)0;。例如,空指针的值表示为FILE *fp=(void *)0;编译报错。所以至少自C++98开始#define NULL 0。 但这会在函数重载时遇到新的困难。

nullptr主要为了解决如下错误:

// C++ program to demonstrate problem with NULL 
#include <bits/stdc++.h> 
using namespace std; 

// function with integer argument 
int fun(int N) { cout << "fun(int)"; } 

// Overloaded function with char pointer argument 
int fun(char* s) { cout << "fun(char *)"; } 

int main() 
{ 
    // Ideally, it should have called fun(char *), 
    // but it causes compiler error. 
    fun(NULL); 
} 

编译报错:

[root workspace]#g++ -g -o nullptr nullptr.cpp
nullptr.cpp: In function ‘int main()’:
nullptr.cpp:15:10: error: call of overloaded ‘fun(NULL)’ is ambiguous
  fun(NULL);
          ^
nullptr.cpp:6:5: note: candidate: int fun(int)
 int fun(int N) { cout << "fun(int)"; }
     ^~~
nullptr.cpp:9:5: note: candidate: int fun(char*)
 int fun(char* s) { cout << "fun(char *)"; }
     ^~~