实现一个LRU Cache

1.什么是Cache和LRU Cache

狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。

CPU中Cache能极大提高存取数据和指令的时间,让整个存储器(Cache和内存)既有Cache的高速度,又能有内存的大容量;操作系统中的内存Page中使用的Cache能使得频繁读取的内存磁盘文件较少的被置换出内存,从而提高访问速度;数据库中数据查询也用到Cache来提高效率;即便是Powerbuilder的DataWindow数据处理也用到了Cache的类似设计。

Cache的算法设计常见的有FIFO(first in first out)和LRU(least recently used)。LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

注:

动态随机存取存储器(Dynamic Random Access Memory,DRAM)是一种半导体存储器,主要的作用原理是利用电容内存储电荷的多寡来代表一个二进制比特(bit)是1还是0。由于在现实中电容会有漏电的现象,导致电位差不足而使记忆消失,因此除非电容经常周期性地充电,否则无法确保记忆长存。由于这种需要定时刷新的特性,因此被称为“动态”存储器。相对来说,“静态”存储器(SRAM)只要存入数据后,纵使不刷新也不会丢失记忆。

静态随机存取存储器(Static Random-Access Memory, SRAM)是随机存取存储器的一种。所谓的“静态”,是指这种存储器只要保持通电,里面储存的数据就可以恒常保持[1]。相对之下,动态随机存取内存(DRAM)里面所储存的数据就需要周期性地更新。然而,当电力供应停止时,SRAM储存的数据还是会消失(被称为volatile memory),这与在断电后还能储存资料的ROM或闪存是不同的。

下图是存储器层次结构,以前在《深入理解计算机系统》这本书看到的,顺便放到此处:

2.数据结构

Cache中的存储空间往往是有限的,当Cache中的存储块被用完,而需要把新的数据载入到Cache的时候,就需要设计一种良好的算法来完成数据块的替换。LRU的思想是基于“最近用到的数据被重用的概率比较早用到的大的多”这个设计规则来实现的。

为了能够快速删除最久没有访问的数据项和插入最新的数据项,我们双向链表连接Cache中的数据项,并且保证链表维持数据项从最近访问到最旧访问的顺序。每次数据项被查询到时,都将此数据项移动到链表头部(O(1)的时间复杂度)。这样,在进行过多次查找操作后,最近被使用过的内容就向链表的头移动,而没有被使用的内容就向链表的后面移动。当需要替换时,链表最后的位置就是最近最少被使用的数据项,我们只需要将最新的数据项放在链表头部,当Cache满时,淘汰链表最后的位置就是了。

注:
对于双向链表的使用,基于两个考虑。首先是Cache中块的命中可能是随机的,和载入进来的顺序无关。其次,双向链表插入、删除很快,可以灵活的调整相互间的次序,时间复杂度为O(1)。

我们要访问某个结点,就需要顺序地一个个找,时间复杂度是O(n)。使用哈希表可以让我们在O(1)的时间找到想要访问的结点,或者返回未找到。

所以:LRU的典型实现是双向链表和哈希表,双向链表用于存储数据结点,并且它是按照结点最近被使用的时间来存储的。哈希表用于快速访问某个结点。

3.一个面试题

Question: Implement LRU cache algorithm 
Implement the LRU cache algorithm with the following interface: 
—————————————————————————————————
T get(K key);
void put(K key, T data);

此题参考价值还是蛮大的,不少公司,特别后台开发职位会考到此题。hawstein大牛用C++代码实现了,我们看下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// A simple LRU cache written in C++
// Hash map + doubly linked list
#include <iostream>
#include <vector>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;
template &lt;class K, class T&gt;
struct Node{
K key;
T data;
Node *prev, *next;
};
template &lt;class K, class T&gt;
class LRUCache{
public:
LRUCache(size_t size){
entries_ = new Node&lt;K,T&gt;[size];
for(int i=0; i< size; ++i)// 存储可用结点的地址
free_entries_.push_back(entries_+i);
head_ = new Node<K,T>;
tail_ = new Node<K,T>;
head_->prev = NULL;
head_->next = tail_;
tail_->prev = head_;
tail_->next = NULL;
}
~LRUCache(){
delete head_;
delete tail_;
delete[] entries_;
}
void Put(K key, T data){
Node<K,T> *node = hashmap_[key];
if(node){ // node exists
detach(node);
node->data = data;
attach(node);
}
else{
if(free_entries_.empty()){// 可用结点为空,即cache已满
node = tail_->prev;
detach(node);
hashmap_.erase(node->key);
}
else{
node = free_entries_.back();
free_entries_.pop_back();
}
node->key = key;
node->data = data;
hashmap_[key] = node;
attach(node);
}
}
T Get(K key){
Node<K,T> *node = hashmap_[key];
if(node){
detach(node);
attach(node);
return node->data;
}
else{// 如果cache中没有,返回T的默认值。与hashmap行为一致
return T();
}
}
private:
// 分离结点
void detach(Node<K,T>* node){
node->prev->next = node->next;
node->next->prev = node->prev;
}
// 将结点插入头部
void attach(Node<K,T>* node){
node->prev = head_;
node->next = head_->next;
head_->next = node;
node->next->prev = node;
}
private:
hash_map<K, Node<K,T>* > hashmap_;
vector<Node<K,T>* > free_entries_; // 存储可用结点的地址
Node<K,T> *head_, *tail_;
Node<K,T> *entries_; // 双向链表中的结点
};
int main(){
hash_map<int, int> map;
map[9]= 999;
cout<<map[9]<<endl;
cout<<map[10]<<endl;
LRUCache<int, string> lru_cache(100);
lru_cache.Put(1, "one");
cout<<lru_cache.Get(1)<<endl;
if(lru_cache.Get(2) == "")
lru_cache.Put(2, "two");
cout<<lru_cache.Get(2);
return 0;
}

看到此处,我就想研究下redis和memcache的cache是怎么设计的了。等下次研究完后,再做下笔记吧。

参考链接:

http://www.cs.uml.edu/~jlu1/doc/codes/lruCache.html

http://hawstein.com/posts/lru-cache-impl.html

http://blog.csdn.net/hexinuaa/article/details/6630384

 

linux内存空间分配和内存管理

前段时间把《程序员的自我修养–链接、装载与库》这本书看完了,期间有些地方不是太明白,当时网络搜索了下,今天把当时看到的东西摘抄下,基本文中大部分内容都是拷贝下面提到的参考链接里的东西,自己在组织下,以备以后需要时查看。

地址分为三类,逻辑地址,线性地址和物理地址。

在《深入理解linux内核》中其把地址分为三类:逻辑地址(汇编语言中操作数地址或指令的地址,对于80x86的CPU,逻辑地址是段+段内偏移地址)、线性地址(也叫虚拟地址)和物理地址。但在Stott Maxwell的《Linux Core Kernel Commentrary》中确是这样分的:逻辑地址(也叫虚拟地址)、线性地址和物理地址。按照386CPU总设计师John Crowford的解释,虚拟地址是保护模式下段和段内偏移量组成的地址,而逻辑地址就是代码段内偏移量,或称进程的逻辑地址。其实对于linux来说,这三种说法都没错,由于linux下并不主张将程序分段,而是主张分页,所以即使是在80x86的体系结构下,段的基地址也是0。因此逻辑地址、线性地址、虚拟地址在linux中其实是相同的。所以对于linux下的ELF可执行文件来说,代码段的起始地址0x08048000既是逻辑地址,也是线性地址也是虚拟地址。

1.X86的物理地址空间布局


以x86_32,4G RAM为例:

物理地址空间的顶部以下一段空间,被PCI设备的I/O内存映射占据,它们的大小和布局由PCI(Peripheral Component Interconnect,一种连接电子计算机主板和外部设备的总线标准)规范所决定。640K~1M这段地址空间被BIOS和VGA(Video Graphics Array,视频传输标准)适配器所占据。

由于这两段地址空间的存在,导致相应的RAM空间不能被CPU所寻址(当CPU访问该段地址时,北桥会自动将目的物理地址“路由”到相应的I/O设备上,不会发送给RAM),从而形成RAM空洞。

Linux内核是以物理页面(也称为PAGE FRAME)为单位管理物理内存的(X86机器中一个页面的大小默认为4KB),为了方便的记录每个物理页面的信息,Linux定义了page结构体,位于include/linux/mm_types.h
Linux系统在初始化时,会根据实际的物理内存的大小,为每个物理页面创建一个page对象,所有的page对象构成一个mem_map数组。进一步,针对不同的用途,Linux内核将所有的物理页面划分到3类内存管理区中,如图,分别为ZONE_DMA,ZONE_NORMAL,ZONE_HIGHMEM。

ZONE_DMA的范围是0~16M,该区域的物理页面专门供I/O设备的DMA(Direct Memory Access,直接内存存取)使用。之所以需要单独管理DMA的物理页面,是因为DMA使用物理地址访问内存,不经过MMU,并且需要连续的缓冲区,所以为了能够提供物理上连续的缓冲区,必须从物理地址空间专门划分一段区域用于DMA。

ZONE_NORMAL的范围是16M~896M,该区域的物理页面是内核能够直接使用的。

ZONE_HIGHMEM的范围是896M~结束,该区域即为高端内存,内核不能直接使用。

2.linux虚拟地址内核空间分布

在kernel image下面有16M的内核空间用于DMA操作。位于内核空间高端的128M地址主要由3部分组成,分别为vmalloc area,persistent kernel mapping(持久化内核映射区),tempoary kernel mapping(临时内核映射区)。

由于ZONE_NORMAL和内核线性空间存在直接映射关系,所以内核会将频繁使用的数据如kernel代码、GDT、IDT、PGD、mem_map数组等放在ZONENORMAL里。而将用户数据、页表(PT)等不常用数据放在ZONE HIGHMEM里,只在要访问这些数据时才建立映射关系(kmap())。比如,当内核要访问I/O设备存储空间时,就使用ioremap()将位于物理地址高端的mmio区内存映射到内核空间的vmalloc area中,在使用完之后便断开映射关系。

3.linux虚拟地址用户空间分布

用户进程的代码区一般从虚拟地址空间的0x08048000开始,这是为了便于检查空指针。代码区之上便是数据区,未初始化数据区,堆区,栈区,以及参数、全局环境变量。

4.linux虚拟地址与物理地址映射的关系 [内核访问物理地址]

Linux将4G的线性地址空间分为2部分,0~3G为user space,3G~4G为kernel space。

由于开启了分页机制,内核想要访问物理地址空间的话,必须先建立映射关系,然后通过虚拟地址来访问。为了能够访问所有的物理地址空间,就要将全部物理地址空间映射到1G的内核线性空间中,这显然不可能。于是,内核将0~896M的物理地址空间一对一映射到自己的线性地址空间中,这样它便可以随时访问ZONE_DMA和ZONE_NORMAL里的物理页面;此时内核剩下的128M线性地址空间不足以完全映射所有的ZONE_HIGHMEM,Linux采取了动态映射的方法,即按需的将ZONE_HIGHMEM里的物理页面映射到kernel space的最后128M线性地址空间里,使用完之后释放映射关系,以供其它物理页面映射。虽然这样存在效率的问题,但是内核毕竟可以正常的访问所有的物理地址空间了。

5.linux内存管理

Linux采用了分页的内存管理机制。由于x86体系的分页机制是基于分段机制的,因此,为了使用分页机制,分段机制是无法避免的。为了降低复杂性,Linux内核将所有段的基址都设为0,段限长设为4G,只是在段类型和段访问权限上有所区分,并且Linux内核和所有进程共享1个GDT(全局描述符表),不使用LDT(局部描述符表即系统中所有的段描述符都保存在同一个GDT中),这是为了应付CPU的分段机制所能做的最少工作。

Linux内存管理机制可以分为3个层次,从下而上依次为物理内存的管理、页表的管理、虚拟内存的管理。

当开启分段分页机制时,典型的x86寻址过程为:

内存寻址的工作是由Linux内核和MMU共同完成的,其中Linux内核负责cr3,gdtr等寄存器的设置,页表的维护,页面的管理,MMU则进行具体的映射工作。

物理内存主要包括:物理页面分配和物理页面回收,当空闲物理页面不足时,就需要从inactive_clean_list队列中选择某些物理页面插入空闲队列中,如果仍然不足,就需要把某些物理页面里的内容写回到磁盘交换文件里,腾出物理页面。

页表管理:

为了保持兼容性,Linux最多支持4级页表,而在x86上,实际只用了其中的2级页表,即PGD(页全局目录表)和PT(页表),中间的PUD和PMD所占的位长都是0,因此对于x86的MMU是不可见的。

6.linux中可执行程序与虚拟地址空间的映射关系

虚拟内存区域(VMA,Virtual Memory Area)是Linux中进程虚拟地址空间中的一个段,在Windows里面叫虚拟段。当操作系统创建线程后,会在进程相应的数据结构中设置一个.text段的VMA,它在虚拟空间中的地址为0x08048000~0x08049000,它对应ELF文件中的偏移为0的.text。由于linux下的ELF可执行文件会有很多个段(section),所以如果把每个section都映射为一个VMA,那么没有一个页大小的段(section)也会被映射为一个页的VMA,这样就浪费了物理空间,由于不足会用0补充。故ELF有一个装载的段(segment),与前面的段(section)不同,前面的段(section)主要用于链接,而段(segment)主要用于装载进内存。可以通过段(section)的权限来合并,如以代码段为代表的权限为可读可执行权限;以数据段和BSS段为代表的权限为可读可写的段;以只读数据为代表的权限为只读权限。

ELF与Linux进程虚拟空间映射关系如下:

7.可执行文件的装载过程

一、进程的建立

(1)创建一个独立的虚拟地址空间

(2)读取可执行文件头,并且建立虚拟空间与可执行文件的映射关系

(3)将CPU的指令寄存器设置成可执行文件的入口地址,启动运行。

二、页错误

上面的步骤执行完以后,其实可执行文件的真正指令和数据都没有载入到内存中。操作系统只是通过可执行文件头部的信息建立起可执行文件和进程虚存之间的映射关系而已。假设在上面的例子中,程序的入口地址为0X08048000,即刚好是.text段的起始地址。当CPU开始打算执行这个地址的指令时,发现0X08048000~0X08049000是个空白页,于是它就认为这是个页错误(Page Fault)。CPU将控制器交给操作系统,操作系统有专门的页错误处理例程来处理这种情况。这时候我们装载过程的第二步建立的数据结构起到了很关键的作用,操作系统将查询这个数据结构,然后找到空页面所在的VMA,计算出相应的页面在可执行文件中的偏移,然后在物理内存中分配一个物理页面,将进程中该虚拟页与分配的物理页之间建立映射关系,然后把控制权再还给进程,进程从刚才页错误的位置重新开始执行。随着进程的执行,页错误也会不断地产生,操作系统也会为进程分配相应的物理页面来满足进程执行的需求。当然有可能进程所需要的内存会超过可用的内存数量,特别是在有多个进程同时执行的时候,这时候操作系统就需要精心组织和分配物理内存,甚至有时候将分配给进程的物理内存暂时收回等等,这就涉及了操作系统的虚拟存储管理。

参考资料:

http://www.cnblogs.com/chengxuyuancc/archive/2013/04/17/3026920.html(绝大部分拷贝此链接资料)

http://www.cnblogs.com/zszmhd/archive/2012/08/29/2661461.html

《程序员的自我修养–装载、链接与库》

准备看下Redis的源代码

Redis是一个开源,BSD授权,高性能的key-value数据库,使用ANSI C编写。Redis的出现很大程度补偿了memcached这类key-value存储的不足,因为:

Memcached基本只支持简单的key-value存储,不支持枚举,不支持持久化和复制能功能。

Redis除key-value之外,还支持list,set,sorted set,hash等众多数据结构,提供了KEYS进行枚举操作,但不能在线上使用,如果需要枚举线上数据,Redis提供了工具可以直接扫描其dump文件,枚举出所有数据,Redis还同时提供了持久化和复制等功能。

如果简单地比较Redis与Memcached的区别,大多数都会得到以下观点:

  • Redis不仅仅支持简单的k/v类型的数据,同时还提供list,set,hash等数据结构的存储。
  • Redis支持数据的备份,即master-slave模式的数据备份。
  • Redis支持数据的持久化,可以将内存中的数据保持在磁盘中,重启的时候可以再次加载进行使用。
    Redis和memcached不同之处还在以下方面:1.网络IO模型 2.内存管理方面 3.数据一致性问题 4.存储方式及其它方面(上文提到了)等等,这里不在细说。

数据模型:

Redis 的外围由一个键、值映射的字典构成。与其他非关系型数据库主要不同在于:Redis 中值的类型不仅限于字符串,还支持如下抽象数据类型:
1.字符串列表
2.无序不重复的字符串集合
3.有序不重复的字符串集合
4.键、值都为字符串的哈希表
值的类型决定了值本身支持的操作。Redis 支持不同无序、有序的列表,无序、有序的集合间的交集、并集等高级服务器端原子操作。

持久化:

Redis 通常将全部的数据存储在内存中。2.4版本后可配置为使用虚拟内存,一部分数据集存储在硬盘上,但这个特性废弃了。
目前通过两种方式实现持久化:
使用快照,一种半持久耐用模式。不时的将数据集以异步方式从内存以 RDB 格式写入硬盘。
1.1版本开始使用更安全的 AOF 格式替代,一种只能追加的日志类型。将数据集修改操作记录起来。Redis 能够在后台对只可追加的记录作修改来避免无限增长的日志。

同步:

Redis支持主从同步。数据可以从主服务器向任意数量的从服务器上同步,从服务器可以是关联其他从服务器的主服务器。这使得 Redis 可执行单层树复制。从盘可以有意无意的对数据进行写操作。由于完全实现了发布/订阅机制,使得从数据库在任何地方同步树时,可订阅一个频道并接收主服务器完整的消息发布记录。同步对读取操作的可扩展性和数据冗余很有帮助。

性能:

当数据依赖不再需要,Redis 这种基于内存的性质,与在执行一个事务时将每个变化都写入硬盘的数据库系统相比就显得执行效率非常高。写与读操作速度没有明显差别。

上面东西,是从维基百科摘抄下来的,只是更好的了解此数据库。关于源码解读,发现有热心网友专门写了源码剖析,见下面链接:

Redis设计与实现

打算边看源码边看下此剖析。

Installation

Download, extract and compile Redis with:
$ wget http://redis.googlecode.com/files/redis-2.6.14.tar.gz $ tar xzf redis-2.6.14.tar.gz $ cd redis-2.6.14 $ make
The binaries that are now compiled are available in the src directory. Run Redis with:
$ src/redis-server

You can interact with Redis using the built-in client:
$ src/redis-cli redis&gt; set foo bar OK redis&gt; get foo "bar"

tutorial:
http://try.redis.io/

参考连接:

http://zh.wikipedia.org/wiki/Redis

http://www.redis.io/

http://simple-is-better.com/news/684

工欲善其事必先利其器

Emacs开发环境配置

Vim开发环境配置

首先,我们先看下自己的VIM都安装了什么插件,命令::scriptnames

我们先配置下vimrc文件,vim ~/.vimrc ,我们先设置让其显示行号和高亮代码,添加如下代码:

set nu! “显示行号
syntax enable “语法高亮
syntax on

TagList

功能:有点像VC里面的工作区,里面列出了当前文件的所有的宏,全局变量,函数名等。CTRL+W 连续2下可以左右切换。

下载taglist压缩包, 下载地址:http://www.vim.org/scripts/script.php?script_id=273,然后把解压的两个文件taglist.vim 和 taglist.txt 分别放到$HOME/.vim/plugin 和 $HOME/.vim/doc 目录中。

之后在~/.vimrc中添加如下几条命令:

let Tlist_Auto_Open = 1
let Tlist_Ctags_Cmd = ‘/usr/bin/ctags’
let Tlist_Show_One_File = 1
let Tlist_Exit_OnlyWindow = 1

此时,我们打开一个.c文件查看,发现左边多出一个workspace,当不想出现此工作区时,使用:Tlist可以关闭和打开。

Ctags

功能:ctags的作用是为系统头文件及自己的程序头文件建立索引,有了这个索引后,就可以使用其它VIM插件来实现相应的功能,比如我需要的功能就是代码提示,那就需要用omnicppcomplete插件,但该插件是依赖于ctags的。VIM默认已安装此插件。

sudo apt-get install exuberant-ctags

我们在源代码的最上层目录下使用此命令:

ctags -R –c++-kinds=+p 或者ctags -R –c-types=+p+x

再在VIM中运行此命令:

:set tags=/home/linuxer/source/tags 该命令将tags文件加入到vim中,也可以加入到~/.vimrc中。

使用方法:

我们把光标移动到函数上,按下CTRL+],VIM会自动切换到意义的函数处。返回时,我们输入CTRL+t。

vim“找到 tag: 1/? 或更多” 其他定义的查看方法:

:tselect 显示列表

:tn和:tp 显示后一个tag和前一个tag

或者g] 就可以了。

WinManager

功能:作用是一个文件管理器,能列出当前目标中的文件,可以通过这个浏览工程中的源文件。当光标停在某个文件或文件夹的时候,回车可以打开该文件或文件夹。

在说这个插件之前,我们先说下netrw.vim插件,这个插件在安装VIM时候就已经安装到系统里了,我们打开VIM输入:e /home/linuxer/source 就可以显示出该文件夹里面的文件,我们的插件其实原理就是由这个插件实现的。

使用方法:

http://www.vim.org/scripts/script.php?script_id=95 ,将对应的plugin和doc放入 ~/.vim 文件夹下对应的plugin和doc文件夹下。

在~/.vimrc下添加以下两行:

let g:winManagerWindowLayout=’FileExplorer|TagList’

或者 let g:winManagerWindowLayout=’FileExplorer’ “这2个显示方式不一样,读者选择自己喜欢的吧,一个是左右两列,一个是上下2列

nmap wm :WMToggle<cr>

在正常情况下输入wm(无:号)可以开启和打开,注意:第一种会把Taglist也关闭,此时用:Tlist可以重新打开。本人倾向第二种,使用时候用wm开启就可已了。

C/C++自动补全插件:clang complete

这个插件需要clang编译器的支持,我们先安装下:

sudo apt-get install clang

之后下载clang complete:http://www.vim.org/scripts/script.php?script_id=3302

方法:vim clang_complete.vmb -c ‘so %’ -c ‘q’

之后在~/.vimrc里添加 set completeopt=longest

配合CTRL+N函数、变量补全基本就差不多了。

上传了一份目前我使用的Vimrc配置到github,主要是为了方便你我使用,点击下面链接进入,我的Vimrc设置

人生大病,只是一“傲”字

先生曰:“人生大病,只是一傲字。为子而傲必不孝,为臣而傲必不忠,为父而傲必不慈,为友而傲必不信。故象与丹朱俱不肖,亦只一傲字,便结果了此生。诸君常要体此人心本是天然之理,精精明明,无致介染着,只是一无我而已:胸中切不可有,有即傲也。古先圣人许多好处,也只是无我而已,无我自能谦。谦者众善之基,傲者众恶之魁。”

引用王阳明先生的这段话来表示下我今后的学习和生活态度,与君共勉。