Yac (Yet Another Cache) – 无锁共享内存Cache

好久没有更新blog了, 这一年来的工作确实很忙….. anyway, 今天终于有新东西可以和大家分享.

这个idea来自一个很简单的想法, 以及目前所遇到的一个机会. 首先我们来谈谈这个机会.

在以前, 很多人都会选择使用APC, APC除了提供Opcode Cache以外, 还会提供一套User Data Cache(apc_store/apc_fetch), 所以对于很多有需求使用User Data Cache的同学, 使用APC, 就没什么问题.

然而, 最近Zend Optimizer Plus开源了, 测试表明, Zend O+在Opcode Cache方面, 因为做了Opcode Cache优化, 所以会比APC要高效, 再后来, PHP5.5已经把Zend O+作为了源代码的一部分. 会随着PHP一起发布.

这就有了个问题, 对于那些既要使用Zend O+的Opcode Cache, 又要使用APC的User Data Cache的同学, 怎么办呢?

开始的时候, 我只是给APC增加了一个开关apc.opcode_cache_enable, 这样一来, 用户就可以使用APC然而关闭opcode cache来达到这个目的, 但是APC的User Data Cache使用的存储机制是和Opcode Cache一样的, 这样的场景要求数据严格正确, 所以锁会比较多, 测试表明, APC的User Data Cache的效率和本地memcached几乎相当.

所以, 我想到了这个idea, 单独开发一个基于共享内存的, 高性能的User Data Cache, 来满足:

• 1. 我就是想让PHP进程之间共享一些简单的数据
• 2. 我希望非常高效的缓存一些页面结果

Okey, 那么叫什么呢? 呵呵, 考虑到我之前的Yaf, Yar, 那么自然就叫Yac啦,

言归正传, 谈谈这个无锁的共享内存Cache的设计思路, 首先, 这个设计基于如下几个经验假设:

• 1. 对于一个应用来说, 同名的Cache键, 对应的Value, 大小几乎相当.
• 2. 不同的键名的个数是有限的.
• 3. Cache的读的次数, 远远大于写的次数.
• 4. Cache不是数据库, 即使Cache失效也不会带来致命错误.
• 5. 典型的应用场景类似于:

  <?php
      if (!(data = cache_fetch(key))) {
           /* cache不存在 */
           data =  从接口/数据库取数据();
           cache_set(key, $data);
      }
  ?>
  

好, 基于这些假设, 我们来看看如何实现Yac, 首先Cache最常用的就是读了, 那么能不能做到读不加锁呢?

这个很容易, 不加锁的读, 拿到以后做数据校验, 如果校验成功, 增说明查询成功, 否则就认为查询失败, 这是一种常用的采用CPU来换锁的方法. 对于目前的服务器, 大部分都是多核的, 如果是加锁, 那么对CPU是一个极大的浪费.

那么, 与其让这些CPU空闲, 不如大家同时读, 大不了回来多做一个数据校验(Yac 采用的是crc校验)

okey, 读锁很容易解决, 但是写锁呢? 我们先来看看Yac的共享内存分配模型图:

Key空间在启动的时候就是确定大小的, 这个是基于上面的假设(2), 默认的(在64位Linux上), Yac会开辟32768个Key Slots, 也就是说你最多可用存储32768个不同的Cache值, 当然这个大小你可以通过yac.keys_memory_size来调整, 如果你设置yac.keys_memory_size为32M的话, 你就能得到262144个Key Slots.

Yac采用双散列法来解决Hash冲突, 首选的Hash函数是进来比较流行的 MurmurHash.

共享内存会被按照固定带下分为尽量多的小块, 默认是4M一小块, 然后Key的值会根据Key的Hash, 来选择到底在那一块内存上申请空间, 从而减少写的时候可能的冲突.

而对于大块内存分配的时候, 只需要操作一个segment->pos指针, 也就是只需要做一个加操作, 从而减少多个进程同时在同一块内存分配的时候可能出现的冲突.

那么, 万一真正的发生了冲突呢? 比如A进程申请了40字节, B进程申请了60字节, 但是Pos只增加了60字节. 这个时候有如下几种情况:

1. A写完了数据, 返回成功, 但是B进程又写完了数据返回成功, 最终B进程的Cache种上了, 而A进程的被踢出了.

2. B进程写完了数据, 返回成功, A进程又写完了数据返回成功, 最终A进程的Cache种上了, B进程的被踢出.

3. A进程写一半, B进程写一半, 然后A进程又写一半, B进程又写一半, 都返回成功, 但最终, 缓存都失效.

可见, 最严重的错误, 就是A和B的缓存都失效, 但是Yac不会把错误数据返回给用户, 当下一次来查询Cache的时候, 因为存在crc校验, 所以都miss.

那么, 考虑到上面的假设(3), (4), (5), okey, Not a big deal, 对吧? 没关系, 错就错吧, 呵呵

那么, 当内存写满了呢? 再看上面的内存分配图, 注意到红色的部分没有?

当一个新的Key到来的时候, Yac会尝试查找合适的Key Slot, 如果找到同名的Key, 那么紧接着判断原来Key的Value内存大小, 考虑到假设(1), 并且Yac在分配内存的时候, 会有意的多给一些内存. 所以, 很大的概率上, 你不需要重新分配内存, 只需要再原有的内存基础上写入新数据即可.

那么万一原有的内存不够呢? 那就分配呗.

这个时候, 假设内存已经分配完了, Yac就会在选定的内存快上, 重置pos, 从头开始分配, 注意到上图的红色部分, 就是新写入的数据, 而黄色部分就是因为写入的新数据, 导致Cache失效的部分. 也就是说, 并不会导致大量的Cache失效.

那么, 万一Key Slots不够了呢?

Yac会从目地Key Slots开始, 根据Hash路径, 选取5个Keys slot, 根据LRU, 踢出一个.

那么, 这样的Cache, 性能到底怎么样呢? 我做了一个和APC对比的简单测试(ab -n 10000 -c 50), 测试脚本如下:

Yac:

<?php

yac = new Yac();

for (i = 0; i<1000;i++) {
    key =  "xxx" . rand(1, 10000);value = str_repeat("x", rand(1, 10000));

    if (!yac->set(key, value)) {
        var_dump("write " .i);
    }

    if (value != (new = yac->get(key))) {
        var_dump("read " . i);
    }
}

var_dump(i);

APC:

<?php

for (i = 0;i<1000; i++) {key =  "xxx" . rand(1, 10000);
    value = str_repeat("x", rand(1, 10000));

    if (!apc_store(key, value)) {
        var_dump("write " .i);
    }

    if (value != (new = apc_fetch(key))) {
        var_dump("read " .i);
    }
}

var_dump($i);

最终的结果:
Yac

Write errors:           0
Total transferred:      597358 bytes
HTML transferred:       368358 bytes
Requests per second:    359.69 [#/sec] (mean)
Time per request:       139.010 [ms] (mean)
Time per request:       2.780 [ms] (mean, across all concurrent requests)
Transfer rate:          209.83 [Kbytes/sec] received

APC的:

Write errors:           0
Total transferred:      7050591 bytes
HTML transferred:       6828577 bytes
Requests per second:    46.79 [#/sec] (mean)
Time per request:       1068.502 [ms] (mean)
Time per request:       21.370 [ms] (mean, across all concurrent requests)
Transfer rate:          322.20 [Kbytes/sec] received

好了, 主要的思想就是这些, 接下来说说Yac的限制吧:

1. key的长度最大不能超过48个字符. (我想这个应该是能满足大家的需求的, 如果你非要用长Key, 可以MD5以后再存)

2. Value的最大长度不能超过64M, 压缩后的长度不能超过1M.

3. 当内存不够的时候, Yac会有比较明显的踢出率, 所以如果要使用Yac, 那么尽量多给点内存吧.

感谢@cydu @cunsheng @rodin, @猫咪的万岁爷_宋Q等同学给的建议.

最后, Yac的代码已经上传到了github: Yac, 不过目前还是完善阶段, 还不支持Windows, 我会继续完善, 有兴趣的同学可以抢先试用, 更加感谢如果能帮忙找找bug, 做做优化. thanks