一个slab。这样就表示，1.2在默认的环境中启动进程后要分配41MB的slab空间，在这个过 程里，memcached的第二个内存冗余发生了，因为有可能一个id根本没有被使用过，但是它也默认申请了一个slab，每个slab会用掉1MB内存
238. 当一个slab用光后，又有新的item要插入这个id，那么它就会重新申请新的slab，申请新的slab时，对应id的slab链表就要增长，这个链表是成倍增长的，在函数grow_slab_list函数中，这个链的长度从1变成2，从2变成4，从4变成8??： 239.
240. static int grow_slab_list (unsigned int id) { 241. slabclass_t *p = &slabclass[id]; 242. if (p->slabs == p->list_size) {
243. size_t new_size = p->list_size ? p->list_size * 2 : 16; 244. void *new_list = realloc(p->slab_list, new_size*sizeof(void*));
245. if (new_list == 0) return 0; 246. p->list_size = new_size; 247. p->slab_list = new_list; 248. }
249. return 1; 250. }
251. 在定位item时，都是使用slabs_clsid函数，传入参数为item大小，返回值为classid，由这个过程可以看 出，memcached的第三个内存冗余发生在保存item的过程中，item总是小于或等于chunk大小的，当item小于chunk大小时，就又发 生了空间浪费。 252. ◎Memcached的NewHash算法
253. Memcached的item保存基于一个大的hash表，它的实际地址就是slab中的chunk偏移，但是它的定位是依靠对key做 hash的结果，在primary_hashtable中找到的。在assoc.c和items.c中定义了所有的hash和item操作。
254. Memcached使用了一个叫做NewHash的算法，它的效果很好，效率也很高。1.1和1.2的NewHash有一些不同，主要的实现方式还是一样的，1.2的hash函数是经过整理优化的，适应性更好一些。 255. NewHash的原型参考：
http://burtleburtle.net/bob/hash/evahash.html。数学家总是有点奇怪，呵呵～
256. 为了变换方便，定义了u4和u1两种数据类型，u4就是无符号的长整形，u1就是无符号char(0-255)。
257. 具体代码可以参考1.1和1.2源码包。
258. 注意这里的hashtable长度，1.1和1.2也是有区别的，1.1中定义了HASHPOWER常量为20，hashtable表长为 hashsize(HASHPOWER)，就是4MB（hashsize是一个宏，表示1右移n位），1.2中是变量16，即hashtable表长 65536： 259.
260. typedef unsigned long int ub4; /* unsigned 4-byte quantities */
261. typedef unsigned char ub1; /* unsigned 1-byte quantities */ 262.
263. #define hashsize(n) ((ub4)1<<(n)) 264. #define hashmask(n) (hashsize(n)-1) 265. 在assoc_init()中，会对primary_hashtable做初始化，对应的hash操作包括：assoc_find()、 assoc_expand()、assoc_move_next_bucket()、assoc_insert()、assoc_delete()，对应 于item的读写操作。其中assoc_find()是根据key和key长寻找对应的item地址的函数（注意在C中，很多时候都是同时直接传入字符串 和字符串长度，而不是在函数内部做strlen），返回的是item结构指针，它的数据地址在slab中的某个chunk上。
266. items.c是数据项的操作程序，每一个完整的item包括几个部分，在item_make_header()中定义为： 267. key：键 nkey：键长
flags：用户定义的flag（其实这个flag在memcached中没有启用） nbytes：值长（包括换行符号\\r\\n） suffix：后缀Buffer nsuffix：后缀长
268. 一个完整的item长度是键长＋值长＋后缀长＋item结构大小（32字节），item操作就是根据这个长度来计算slab的classid的。 269. hashtable中的每一个桶上挂着一个双链表，item_init()的时候已经初始化了heads、tails、sizes三个数组 为0，这三个数组的大小都为常量LARGEST_ID（默认为255，这个值需要配合factor来修改），在每次item_assoc()的时候，它会 首先尝试从slab中获取一块空闲的chunk，如果没有可用的chunk，会在链表中扫描50次，以得到一个被LRU踢掉的item，将它 unlink，然后将需要插入的item插入链表中。 270. 注意item的refcount成员。item被unlink之后只是从链表上摘掉，不是立刻就被free的，只是将它放到删除队列中（item_unlink_q()函数）。 271. item对应一些读写操作，包括remove、update、replace，当然最重要的就是alloc操作。
272. item还有一个特性就是它有过期时间，这是memcached的一个很有用的特性，很多应用都是依赖于memcached的item过 期，比如session存储、操作锁等。item_flush_expired()函数就是扫描表中的item，对过期的item执行unlink操作， 当然这只是一个回收动作，实际上在get的时候还要进行时间判断： 273. 274. /* expires items that are more recent than the oldest_live setting. */
275. void item_flush_expired() { 276. int i;
277. item *iter, *next;
278. if (! settings.oldest_live) 279. return;
280. for (i = 0; i < LARGEST_ID; i++) {
281. /* The LRU is sorted in decreasing time order, and an item's timestamp
282. * is never newer than its last access time, so we only need to walk
283. * back until we hit an item older than the oldest_live time.
284. * The oldest_live checking will auto-expire the remaining items. 285. */
286. for (iter = heads[i]; iter != NULL; iter = next) { 287. if (iter->time >= settings.oldest_live) { 288. next = iter->next;
289. if ((iter->it_flags & ITEM_SLABBED) == 0) { 290. item_unlink(iter); 291. } 292. } else {
293. /* We've hit the first old item. Continue to the next queue. */
294. break; 295. } 296. } 297. } 298. }
299. /* wrapper around assoc_find which does the lazy expiration/deletion logic */
300. item *get_item_notedeleted(char *key, size_t nkey, int *delete_locked) {
301. item *it = assoc_find(key, nkey);
302. if (delete_locked) *delete_locked = 0; 303. if (it && (it->it_flags & ITEM_DELETED)) {
304. /* it's flagged as delete-locked. let's see if that condition
305. is past due, and the 5-second delete_timer just hasn't 306. gotten to it yet... */
307. if (! item_delete_lock_over(it)) {
308. if (delete_locked) *delete_locked = 1; 309. it = 0; 310. } 311. }
312. if (it && settings.oldest_live && settings.oldest_live <= current_time &&
313. it->time <= settings.oldest_live) { 314. item_unlink(it); 315. it = 0; 316. }
317. if (it && it->exptime && it->exptime <= current_time) { 318. item_unlink(it); 319. it = 0; 320. }
321. return it; 322. } 323.
324. Memcached的内存管理方式是非常精巧和高效的，它很大程度上减少了直接alloc系统内存的次数，降低函数开销和内存碎片产生几率，虽然这种方式会造成一些冗余浪费，但是这种浪费在大型系统应用中是微不足道的。
325. ◎Memcached的理论参数计算方式 326. 影响 memcached 工作的几个参数有： 327. 常量REALTIME_MAXDELTA 60*60*24*30 最大30天的过期时间
328. conn_init()中的freetotal（=200） 最大同时连接数
329. 常量KEY_MAX_LENGTH 250 最大键长
330. settings.factor（=1.25） factor将影响chunk的步进大小 331. settings.maxconns（=1024） 最大软连接
332. settings.chunk_size（=48） 一个保守估计的key+value长度，用来生成id1中的chunk长度（1.2）。id1的chunk长度等于这个数值加上item结构体的长度（32），即默认的80字节。
333. 常量POWER_SMALLEST 1 最小classid（1.2）
334. 常量POWER_LARGEST 200 最大classid（1.2）
335. 常量POWER_BLOCK 1048576 默认slab大小
336. 常量CHUNK_ALIGN_BYTES (sizeof(void *))
保证chunk大小是这个数值的整数倍，防止越界（void *的长度在不同系统上不一样，在标准32位系统上是4） 337. 常量ITEM_UPDATE_INTERVAL 60 队列刷新间隔
338. 常量LARGEST_ID 255
最大item链表数（这个值不能比最大的classid小） 339. 变量hashpower（在1.1中是常量HASHPOWER） 决定hashtable的大小
340. 根据上面介绍的内容及参数设定，可以计算出的一些结果： 341. 1、在memcached中可以保存的item个数是没有软件上限的，之前我的100万的说法是错误的。
2、假设NewHash算法碰撞均匀，查找item的循环次数是item总数除以hashtable大小（由hashpower决定），是线性的。
3、Memcached限制了可以接受的最大item是1MB，大于1MB的数据不予理会。
4、Memcached的空间利用率和数据特性有很大的关系，又与
DONT_PREALLOC_SLABS常量有关。 在最差情况下，有198个slab会被浪费（所有item都集中在一个slab中，199个id全部分配满）。 342. ◎Memcached的定长优化 343. 根据上面几节的描述，多少对memcached有了一个比较深入的认识。在深入认识的基础上才好对它进行优化。
344. Memcached本身是为变长数据设计的，根据数据特性，可以说它是“面向大众”的设计，但是很多时候，我们的数据并不是这样的“普 遍”，典型的情况中，一种是非均匀分布，即数据长度集中在几个区域内（如保存用户 Session）；另一种更极端的状态是等长数据（如定长键值，定长数据，多见于访问、在线统计或执行锁）。
345. 这里主要研究一下定长数据的优化方案（1.2），集中分布的变长数据仅供参考，实现起来也很容易。
346. 解决定长数据，首先需要解决的是slab的分配问题，第一个需要确认的是我们不需要那么多不同chunk长度的slab，为了最大限度地利用资源，最好chunk和item等长，所以首先要计算item长度。
347. 在之前已经有了计算item长度的算法，需要注意的是，除了字符串长度外，还要加上item结构的长度32字节。
348. 假设我们已经计算出需要保存200字节的等长数据。
349. 接下来是要修改slab的classid和chunk长度的关系。在原始版本中，chunk长度和classid是有对应关系的，现在如果 把所有的chunk都定为200个字节，那么这个关系就不存在了，我们需要重新确定这二者的关系。一种方法是，整个存储结构只使用一个固定的id，即只使 用199个槽中的1个，在这种条件下，就一定要定义DONT_PREALLOC_SLABS来避免另外的预分配浪费。另一种方法是建立一个hash关系， 来从item确定classid，不能使用长度来做键，可以使用key的NewHash结果等不定数据，或者直接根据key来做hash（定长数据的 key也一定等长）。这里简单起见，选择第一种方法，这种方法的不足之处在于只使用一个id，在数据量非常大的情况下，slab链会很长（因为所有数据都 挤在一条链上了），遍历起来的代价比较高。
350. 前面介绍了三种空间冗余，设置chunk长度等于item长度，解决了第一种空间浪费问题，不预申请空间解决了第二种空间浪费问题，那么对 于第一种问题（slab内剩余）如何解决呢，这就需要修改POWER_BLOCK