如何实现一个应用级缓存（下），实现应用级缓存
如何实现一个应用级缓存（下），实现应用级缓存
以前留的坑必须填，不然终有一日被埋进去 :)
上篇说到linux的文件cache分为page cache和buffer cache。实际上，一个page cache对应多个buffer cache。
这两个东西容易傻傻分不清楚，将他们分开很有必要。首先，page cache和buffer cache在不同层次。page cache在vfs和内存管理系统数据交换，这一文件系统逻辑层次上。而buffer cache在具体文件系统，这一文件系统物理层次上。其次page cache和buffer cache不是为了同一个目的，page cache就是页，作为文件系统在内存上的缓存。buffer cache是缓冲区，读写磁盘的时候为了减少I/O的数量，攒齐一定量的数据再写和攒齐一定数量读出的数据再返回。
linux如何实现LRU
linux的页面调度算法用的是LRU，linux用了两个双向链表实现。active_list和inactive_list。顾名思义，active_list存放最近被访问频路较高的，inactive_list存放最近访问频率较低的的。链表节点有是否被访问的状态，设为referenced状态表示正在被访问，设置unreferenced表示没被访问。那么具体算法如下，新加入的节点插入到inactive_list的首部。淘汰的时候，遍历一遍active_list的节点，将unreferenced状态的节点插入到inactive_list首部，然后从inactive_list尾部开始逐个淘汰。
这是改良版的LRU 2Q算法，用两个优先队列完成算法。最近访问过一次，不算是“常”访问。最近没访问，也不直接淘汰。
文件随机访问cache
在内存缓存实现的时候我用了LinkedHashMap来加速随机访问。linux用的是radix tree(基数树)来加速随机访问。radix tree将文件内偏移量和其对应的cache对应起来。radix tree分为叶子节点和非叶子节点。非叶子节点指向其他节点。叶子节点指向cache。从根节点到叶子节点的路径上所经过的节点的键值拼接起来就是文件内偏移量的地址。
实现中，文件的inode对应一个address_space结构体，address_space结构体又对应一个radix tree。radix tree的叶子节点对应一个page结构体。简化过的结构体如下，
struct inode {
struct address_space *i_mapping; //对应address_space
struct address_space i_data; //对应address_space的host
};
struct address_space {
struct inode *host; //指向此space的inode
struct radix_tree_root page_tree; //radix tree根节点
unsigned long nrpages; //对应的page的数量
} __attribute__((aligned(sizeof(long))));
struct radix_tree_root {
unsigned int height; //树的高度
gfp_t gfp_mask;
struct radix_tree_node __rcu *rnode;
};
struct page{
struct list_head list;
struct address_space * mapping; //对应的address_space
unsigned long index;
struct page *next_hash; //自身的指针，这样就可以链接成一个链表
atomic t count; //用于页面交换的计数,若页面为空闲则为0，分配就赋值1，没建立或恢复一次映射就加1，断开映射就减一
unsigned long flags; //反应页面各种状态，例如活跃，不活跃脏，不活跃干净，空闲
struct list_head lru;
unsigned long age; //页面寿命
wait_queue_head_t wait;
struct page ** pprev_hash;
struct buffer_head * buffers; //buffer cache数据结构
void * virtual
struct zone_struct * zone; //指向所属的管理区
}
这些结构体的关系如下
inode ------ addressSPace ------ RadixTree
| | | | / | | \
| | | | page page page page
| | | | | | | |
| | | ------ | | |
| | -------------- | |
| -------------------- |
---------------------------
文件通过inode找到对应的addressSpace，从addressSpace找到对应的radixTree，再索引到页。通过以上步骤，文件可以找到文件内任意地址对应的页，然后将页的虚拟地址交给MMU和页表，如果根据虚拟地址判断出页是虚拟页，就会发生缺页中断。最后返回页的物理地址，页就被缓存到了内存中。
mmap
mmap相当于将文件的页载入内存，进程修改内存指针的内容就修改了文件。页缓存是将文件缓存进了内存，载入和缓存入是有不同的。进程通过页缓存访问文件需要经过两次拷贝，由于页缓存在内核空间中，先要将页缓存入内核空间，再将页拷贝给进程。进程通过mmap访问文件需要一次拷贝。不需要将页拷贝入内核，直接拷贝给进程就可以。所以mmap效率更高。
swap
swap和文件cache的目的是完全不同的，swap是当内存容量告急，将内存上的数据交换到硬盘上。swap的内容是堆上申请的空间，本来就是内存中的计算数据，而不是像页本来是硬盘上的数据。swap在现在的操作系统中，大多默认是不开启的。swap可想而知会耗费大量I/O和内存。在iOS中，没有swap机制，才会出现内存告急的时候，系统发给你一个通知，你如果不做处理就会被kill掉。
填坑完毕，继续挖坑。人生就是挖一个坑再填起来的do while。
本篇聊聊硬盘缓存，硬盘存储可以直接对文件读写或者创建一个数据库，对于所有数据库，单条数据在一个阈值之上，文件读写会比数据库读写更快。而sqlite官方推荐这个阈值在20KB，详见：http://www.sqlite.org/intern-v-extern-blob.html
阈值下数据库为何快过文件存取？
数据库建立的索引和查询器优化都是优化速度的关键。
数据库索引
数据库索引分为顺序索引、B+树索引、hash索引。
1.顺序索引为每个文件建立一个数组索引，块中的元组按逻辑存储的顺序用链表连接起来，加速顺序访问(类LlinkedHashMap结构)。
2.B+树索引为文件建立一个B+树，B+树分为叶子节点和非叶子节点。非叶子节点包含(本层高度-1)/2到(本层高度-1)个索引和索引对应的其他节点。叶子节点包含(本层高度-1)/2到(本层高度-1)个索引和索引对应的元组地址。
3.hash索引为文件建立一个hash表，映射索引和索引对应的元组地址。
索引的目的就是减少磁盘块的I/O。假如你存入文件，需要把文件所有块整个读取入内存。而存入数据库，只需要将存储索引的块和所查找的元组所在的块读入内存就可以了。大部分情况，存储索引的块一般已经缓存在内存了，这就需要更少的磁盘块的I/O了。
查询器优化
查询器优化，这是数据库的精髓，不同数据库使用的策略不同，并且没有公开，应该是属于商业机密吧。
假设要找出两个关系之间的相同值，需要将这两个关系进行join，有3种优化方法。
1.nested loop join，将所有数据取出，双层for循环两个关系的元组，O(M N)。这个方法有改进的空间，利用空间局部性，改进为包含两个块的双层for循环，先循环块再循环块内的元组，复杂度同样是O(MN)，但这个M和N指的是块的数量而不是元组的数量。
2.hash join，为一个关系中的所有元组建立一个拉链法的hash表，对另一个关系用同样的hash函数，再将映射到同一表项中的元组，判断是否值相等。如果内存足够的话，将hash表放入内存中，这种方法会很快，否则就要添加多次的hash表的I/O，O(M + N)。
3.排序-归并-连接(merge-join)，先将两个关系排序，如果两个关系装不下内存，就要外部排序。然后再像归并排序那样判断元组是否相等，O(M + N)。
SQL语句会被数据库解释成关系代数，因为关系代数有等价性，也就是说可以解释成多个关系代数，形成多个查询计划。多个关系连接顺序形成多种的排序方式，每个关系连接可以使用不同种的join方式，乘起这两个数是很大的数量，找出最优查询计划会很耗时。动态规划可以帮助减少耗时，不同种的排序方式会包含很多重复的连接，存储下来节省时间。也可以使用贪心算法，每次只选择最低成本的连接来排序，这也叫最近邻居算法，3.8.0版本之前的sqlite就是使用的这个算法。详见：http://www.devbean.net/2016/04/how-database-works-5/
阈值上文件为何快过数据库？
这个问题我无法给出一个很严谨的答案，这个结果是各个数据库实际benchmark出来的结果，网络上资料有限，我的理解是，光插入和查询数据库不会比文件系统慢太多，性能更多的消耗应该在事务、数据库缓存器、数据库备份上。而mongo有个单个文档的限制在16MB，mongo的文档限制和大blob降低数据库性能没有关系，mongo限制的原因是不希望，单个文档耗费太多内存或者带宽。 详见：https://docs.mongodb.com/manual/core/document/
让Idea不仅仅是Idea：
如果要实现一个网络请求的缓存，数据库的性能肯定要优于文件。实现出硬盘缓存难点就在于实现一个数据库驱动，数据库的驱动就是对数据库的封装，对外层调用者隔绝数据库的操作，并负责把SQL语句作为参数，传递给数据库。一个数据库驱动的实现，只要按照JDBC和ODBC规范，包括Connection、ResultSet、Statement等等。再加上相关数据库API的调用就妥了。
数据库驱动实现的时候有一些缓存技巧。可以用一个ConnectionPool缓存数据库的连接，可以缓存经过prepared的statement。查询优化是很费时间的一个步骤，所以数据库内部会缓存查询计划(plan caching)。
SQL语句会被数据库翻译成Statement，对于数据库SQL语句就像是源代码，Statement是翻译后的机器码。一个Statement从建立到执行就是编程时要注意的关键。
第一步建立Statement和准备Statement
- (RBEStatement *)prepareStatementWithSql:(NSString *)sql {
sqlite3_stmt *pStmt;
pStmt = (sqlite3_stmt *)CFDictionaryGetValue(_cachedStatement, (__bridge const void *)sql);
//缓存prepared statement
if (!pStmt) {
int responseCode = sqlite3_prepare_v2(_db, sql.UTF8String, -1, &pStmt, 0);
if (responseCode != SQLITE_OK) {
NSLog(@"RBEDatabase: error occur statement preparing errorcode %d errorMsg %@", [self lastErrorCode], [self lastErrorMsg]);
//释放statement资源
sqlite3_finalize(pStmt);
return nil;
}else {
CFDictionarySetValue(_cachedStatement, (__bridge const void *)sql, pStmt);
}
}else {
//重新使用statement
sqlite3_reset(pStmt);
}
RBEStatement *statement = [[RBEStatement alloc] init];
[statement setStmt:pStmt];
return statement;
}
第二步绑定参数，将SQL语句中的参数绑定到Statement上
//不同数据类型，调用不同数据库API
- (void)bindObject:(id)obj toIndex:(int)idx ofStmt:(sqlite3_stmt *)pStmt {
if (!obj || [obj isKindOfClass:[NSNull class]]) {
sqlite3_bind_null(pStmt, idx);
}else if ([obj isKindOfClass:[NSData class]]) {
const void *bytes = [obj bytes];
if (!bytes) {
bytes = "";
}
sqlite3_bind_blob(pStmt, idx, bytes, (int)[obj length], SQLITE_STATIC);
}else if ([obj isKindOfClass:[NSDate class]]) {
sqlite3_bind_double(pStmt, idx, [obj timeIntervalSince1970]);
}else if ([obj isKindOfClass:[NSNumber class]]) {
if (strcmp([obj objCType], @encode(unsigned char)) == 0) {
sqlite3_bind_int(pStmt, idx, [obj unsignedCharValue]);
}else if (strcmp([obj objCType], @encode(unsigned short)) == 0) {
sqlite3_bind_int(pStmt, idx, [obj unsignedShortValue]);
}else if (strcmp([obj objCType], @encode(unsigned int)) == 0) {
sqlite3_bind_int64(pStmt, idx, [obj unsignedIntValue]);
}else if (strcmp([obj objCType], @encode(unsigned long)) == 0) {
sqlite3_bind_int64(pStmt, idx, [obj unsignedLongValue]);
}else if (strcmp([obj objCType], @encode(unsigned long long)) == 0) {
sqlite3_bind_int64(pStmt, idx, [obj unsignedLongLongValue]);
}else if (strcmp([obj objCType], @encode(bool)) == 0) {
sqlite3_bind_int(pStmt, idx, [obj boolValue] ? 1 : 0);
}else if (strcmp([obj objCType], @encode(char)) == 0) {
sqlite3_bind_int(pStmt, idx, [obj charValue]);
}else if (strcmp([obj objCType], @encode(short)) == 0) {
sqlite3_bind_int(pStmt, idx, [obj shortValue]);
}else if (strcmp([obj objCType], @encode(int)) == 0) {
sqlite3_bind_int(pStmt, idx, [obj intValue]);
}else if (strcmp([obj objCType], @encode(long)) == 0) {
sqlite3_bind_int64(pStmt, idx, [obj longValue]);
}else if (strcmp([obj objCType], @encode(long long)) == 0) {
sqlite3_bind_int64(pStmt, idx, [obj longLongValue]);
}else if (strcmp([obj objCType], @encode(float)) == 0) {
sqlite3_bind_double(pStmt, idx, [obj floatValue]);
}else if (strcmp([obj objCType], @encode(double)) == 0) {
sqlite3_bind_double(pStmt, idx, [obj doubleValue]);
}else {
sqlite3_bind_text(pStmt, idx, [[obj description] UTF8String], -1, SQLITE_STATIC);
}
}else {
sqlite3_bind_text(pStmt, idx, [[obj description] UTF8String], -1, SQLITE_STATIC);
}
}
第三步ResultSet里的next语句执行SQL语句
- (BOOL)next {
//执行SQL语句
int responseCode = sqlite3_step(_statement.stmt);
if (responseCode != SQLITE_DONE && responseCode != SQLITE_ROW) {
NSLog(@"RBEDatabase: error occur query excuting errorcode %d errorMsg %@", [_db lastErrorCode], [_db lastErrorMsg]);
}
if (responseCode != SQLITE_ROW) {
[self close];
}
return responseCode == SQLITE_ROW;
}
最后就可以从结果集获取结果了。
sqlite会为除select SQL语句使用隐式事务，我实现的单表简单操作不需要考虑事务，sqlite已经帮我照顾好了。
注意多线程！要不然在多线程下加锁访问同一个数据库连接，要不然在同一个线程上访问同一个数据库连接。
引用:
linux cache http://www.penglixun.com/tech/system/linux_cache_discovery.html
linux内存管理中的基数树 http://rick_stone.leanote.com/post/%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F%E4%B8%AD%E7%9A%84%E9%A1%B5%E9%AB%98%E9%80%9F%E7%BC%93%E5%AD%98%E2%80%94%E2%80%94%E5%9F%BA%E6%95%B0%E6%A0%91%EF%BC%88%E4%BA%8C%EF%BC%89
mmap http://www.cnblogs.com/huxiao-tee/p/4660352.html
数据库书籍：数据库系统概念
本系列：
- 如何实现一个应用级缓存（上）
- 如何实现一个应用级缓存（下）
用户点评