memcached缓存，只能保存【关键字/数据对】
存 ：自己通过保存命令（协议中的set add等命令）保存的，命令是字符串
要保存数据的最大长度是有限制的(1M)，超过的保存【失败】
初始化时指定了一个能分配给memcached的用于缓存的最大内存(如1024M)，
当且仅当已经用完了，就用【LRU算法】删除一个项用来保存新项
如命令"set foo 0 600 3\r\nbar\r\n"
set 命令，通知memcached保存该项
foo 关键字
0 flags，memcached只是帮我们保存，对memcached没意义
600 超时秒数，这里超过10分钟后，该缓存数据就失效了
3 数据的字节数
\r\n 分隔符
bar 关键字对应的数据
\r\n 分隔符
取 ：通过协议的get命令获取之前保存到memcached中的数据，返回的是字符串
如果
之前已经保存了，
并且没有超时，
并且没有因为分配给memcached的内存不足该项被用LRU算法挪用，就返回该缓存项
如命令"get foo\r\n"
get 命令，在memcached缓存中查找
foo 关键字
返回"VALUE foo 0 3\r\nbar\r\n"
VALUE 前缀
foo 关键字
0 flags
\r\n 分隔符
bar 该关键字对应的数据
\r\n 分隔符
每个缓存项用数据结构item表示
关键字/flags/数据三项内容都是保存在end字符串中，格式为"关键字\0 flags 数据长度\r\n数据\r\n"
其他的项是信息项和用于数据结构组织（hash桶链表指针，正在使用item项双向链表指针等）的项
需要保存项时，不是直接malloc分配内存的，而是采用了slabs分配算法，放到合适的chunk中的
每次malloc分配的内存是一个特定大小(比如1M)的slab
然后把这个slab划分成很多大小(比如88字节)相同的chunk
每个chunk中能容纳一个不超过其容量的item(slab=1M, chunk=88B时能放11915个chunk)
如果需要保存很多接近且不超过88B的item，一个slab不足时，就会分配另外一个同样组织结构的slab
这样有很多chunk大小为88B的slab，所有这些slab的集合成为slabs class，用数据结构slabclass_t表示
slab只是一个概念，没有专门的数据结构表示，其chunk的大小在slabclass_t中指出了
slabclass_t中包含有所有slab的指针
slabs class中需要记录
每个chunk的大小，每个slab中能容纳的chunk的个数
它有哪些slab(指针)
chunk状态
1：哪些chunk还从来没有使用过 : slabclass_t.end_page_ptr 第一个未被使用的空间的指针
slabclass_t.end_page_free 未使用的chunk的个数
2：哪些chunk使用过被回收了 : slabclass_t.slots二维指针维护它们的指针
3：哪些chunk正在使用 : slabclass_t本身没有记录这些，
通过另外的全局的双向链表(heads或tails)记录
struct item中的next prev字段就是双向链表指针
slab只管内存分配、回收和维护，所有项是通过hash表和单向链表组织起来的
hash表
hash表存的是是item的指针
初始化时是有2^16个桶，当item个数超过同的个数的1.5倍时，会扩大一倍
#define hashsize(n) ((ub4)1<<(n))
初始化 primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
扩大 if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2)
primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
hash函数
没懂，
其中涉及位操作，在configure时还要判断是大端字节序还是小端字节序
具有相同hash值的item，通过单向链表连接(struct item中的h_next字段)
操作
查找
插入 插入桶的最前面
删除 只是把需要删除前面的指针跳过需要删除的，指向后面的，不会释放内存
由于加入了slabs内存分配管理。所以在增删项时涉及到多个方面
1：组织item项指针的hash表
2：slabs class结构中
3：对应slabs class正在使用item的双向链表heads tails
do_item_alloc
依次查看
使用后被回收【1】
分配后从未被使用【2】
中还有没空闲的chunk，有就返回这个
如果两种情况都没有，那么尝试分配新的slab【3】（如果系统(所有slab class)已分配内存超过了限制，则失败）
如果不能分配新的slab，就是用LRU算法(heads tails说明)删除(do_item_unlink)一个item，返回这个【4】
do_item_link
1：把该item指针插入hash表桶
2：把该item插入双向链表的最前面
do_item_unlink
1：从hash表桶中删除该item的指针，就找不到了
2：从该slab class双向链表heads（链接了该slab class所有正在使用的items的指针）中去掉这个item指针
3：把这个item空间放到其slab class的空闲区列表slots中
do_item_remove
1.1：或者减少引用计数refcount
1.2：或者把该item放入到其slab class的被释放空闲item堆中(slots)
do_item_update
把该item放到双线链表的最前而已，这样根据LRU算法被删除的可能会推迟
do_item_replace
do_item_unlink老的item
do_item_link新的item
item_get
根据关键字查找item
如果没找到，返回NULL
如果已经超时就do_item_unlink该item，返回NULL（lazy expiration/deletion logic等到了查找时才看是不是超时）
如果找到并且没有超时，就返回该item的指针
----------------------------------------------------------------------------
memcached中的struct conn包含很多字段，还有指针，指向malloc的内存
如果每次要用的时候malloc一个。用完free，耗时
memcached中malloc的struct conn，用完不会free，而是放到一个可用链表中
如果下回需要struct conn时，先看这个链表中还有没有，如果有就从链表的尾部取一个来用，没有在malloc一个
如果不需要了就放到链表的尾部，而不是free释放空间。
/*
* Free list management for connections.
*/
static conn **freeconns; // 可用链表
static int freetotal; // 总共的指针个数
static int freecurr; // 可用链表尾数组下标
slabcalss_t代表一个存放指定大小chunk的集合，系统中有很多个slabclass_t
比如存放的88 112字节长度的两个subclass_t
size -- slab class中每个chunk的大小
perslab -- 每个slab中能存放上面size大小chunk的个数
这两个参数在初始化时确定，并且始终不变，下面是一个实际运行例子
/userhome/zhongyj/sfw/memcached/bin>memcached -vv
slab class 1: chunk size 88 perslab 11915
slab class 2: chunk size 112 perslab 9362
slab class 3: chunk size 144 perslab 7281
slab class 4: chunk size 184 perslab 5698
slab class 5: chunk size 232 perslab 4519
slab class 6: chunk size 296 perslab 3542
......
每个slab的大小由宏参数POWER_BLOCK决定这里是1M，每个slab能存放的个数perslab = 1M / size，
初始化时确定每个slab class的chunk大小
全局变量
static void *mem_base = NULL;
static void *mem_current = NULL;
static size_t mem_avail = 0;
只在启动就与分配所有内存的情况下才有用
mem_base记录的是启动就分配所有内存的指针，如果不是启动就与分配所有内存的情况，这个值恒定为NULL
mem_current记录的是与分配内存空闲区的首指针
mem_avail记录的是预分配的空间还有多少可用的空间
current_time
全局当前时间：是自启动以来的秒数，作为事件(clock_handler函数)，周期的被更新，其他需要取当前时间时，就去这个全局
每个slab class都有一个双向链表
static item *heads[255];
static item *tails[255];
heads指向双向链表的头 ： 插入的时候从这边插入
tails指向双线链表的尾 ： 删除的时候从这边删除（LRU算法）
int tries = 50;
for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev)
{
if (可以删除)
do_item_unlink(search); // 从hash表的桶中删除指针,然后把这个item放到slab class的空闲item列表中slots
}
|
typedef struct {
unsigned int size; /* sizes of items */ // 每个chunk字节数大小
unsigned int perslab; /* how many items per slab */ // 每个slab中chunk个数
void **slots; /* list of item ptrs */ // 被释放的空闲的item，分配时首先分配这些，不够时在看末尾，还不够就要malloc分配
unsigned int sl_total; /* size of previous array */ // slots的总容量，每次分配时是16的2次方个，这个就是这个数
unsigned int sl_curr; /* first free slot */ // 第一个还没用的的slots
void *end_page_ptr; /* pointer to next free item at end of page, or 0 */ // 最后一个slab空闲内存起始地址
unsigned int end_page_free; /* number of items remaining at end of last alloced page */ // 最后一个slab空闲区能存放的item个数
unsigned int slabs; /* how many slabs were allocated for this class */ // 每次malloc实际分配一个slab(1M)是会加1
void **slab_list; /* array of slab pointers */
unsigned int list_size; /* size of prev array */ // 每次分配slab_list时，都是分配16的2次方倍，这个是这个数，而slabs是实际malloc分配了内存的个数
unsigned int killing; /* index+1 of dying slab, or zero if none */
} slabclass_t;
typedef struct _stritem {
struct _stritem *next; // 可用item的双向链表(heads tails)的前面item指针
struct _stritem *prev; // 可用item的双向链表(heads tails)的后面item指针
struct _stritem *h_next; /* hash chain next */ // 指向hash表该桶的下一项, hash表中的项就是item指针
rel_time_t time; /* least recent access */
rel_time_t exptime; /* expire time */
int nbytes; /* size of data */
unsigned short refcount;
uint8_t nsuffix; /* length of flags-and-length string */
uint8_t it_flags; /* ITEM_* above */
uint8_t slabs_clsid;/* which slab class we're in */
uint8_t nkey; /* key length, w/terminating null and padding */
uint64_t cas_id; /* the CAS identifier */
void * end[]; // 关键字 flags 数据长度 数据内容都存放在一个字符串数组中
/* then null-terminated key */
/* then " flags length\r\n" (no terminating null) */
/* then data with terminating \r\n (no terminating null; it's binary!) */
} item;
|
阅读(4037) | 评论(0) | 转发(0) |
