Memoization in PHP

谈到PHP应用的性能优化,很多人最先想到的都是缓存。因为PHP一般不会用于完成计算密集型任务,算法优化的余地很小,所以性能瓶颈不会出现在CPU上,而更可能出现在IO上。而IO操作通常优化方案都是采用缓存,最常见的缓存情形莫过于这样一次数据库查询了:

function query_posts($author) {
  global $pdo,$memcache;
  $sql='SELECT * FROM `posts` WHERE author=:author ORDER BY `date`';
  $cacheKey="author_{$author}_posts";
  $results=$memcache->get($cacheKey);
  if (false===$results) { //缓存没有命中则执行查询并将结果存到memcache
    $sth=$pdo->prepare($sql);
    $sth->bindParam(':author', $author, PDO::PARAM_STR);
    $sth->execute();
    $results=$sth->fetchAll(PDO::FETCH_ASSOC);
    $memcache->set($cacheKey,$results);
  }
  return $results;
}

除了SQL查询,还有哪些IO情形需要缓存呢? — 当然少不了外部网络接口请求了!比如获取Google搜索结果,尽管Google服务器处理查询很快,但这个请求仍非常耗时,不但因为HTTPS连接有额外开销,更是因为(此处请自行填空)。示例代码如下:

function search_google($keywords) {
  global $memcache;
  $url='https://google.com/search?q='.$keywords;
  $results=$memcache->get($url);
  if (false===$results) { //缓存没有命中则发起请求
    $results=file_get_contents($url);
    $memcache->set($url,$results);
  }
  return $results;
}

先停下来观察下前面两个典型的缓存案例代码。你会发现什么样的问题?

  1. 代码重复!违背了DRY原则。缓存是否命中的检查代码都是一样的。
    并且,缓存检查代码与主逻辑代码混杂在一起,耦合度高,使得程序逻辑支离破碎。
  2. 不同缓存的Key都是人肉管理,很难保证Cache Key不会出现冲突。

如何逐步解决这些问题呢?代码重复,就意味着缺少抽象!
先将这些步骤抽象一下,缓存的使用一般都是这样一个流程:

if 缓存命中 then
  返回缓存中的内容
else
  执行操作
  将操作结果放入缓存并返回结果
end

而其中“执行操作”这一步才是程序的主逻辑,而其它的都是缓存代码的逻辑。如果要避免代码重复,那就只有将程序主逻辑代码与缓存操作代码分离开来。那么我们就不得不将原来的一个函数拆分成这样两个函数:

function cache_operation() {}; //缓存操作代码,可重用
function action() {};     //程序主体代码
# 以search_google函数为例,抽取掉缓存检查代码后
# 它就露出了原形 —— 我们会惊讶地发现原来主逻辑只有一行代码
function search_google($k) {
  return file_get_contents('https://google.com/search?q='.$k);
}

至于如何实现先放一边。至此,我们已经清楚解决代码重复问题的方向。接下来第二个问题:如何实现缓存Key的统一管理?很明显,当然是在可重用的缓存操作函数中自动生成缓存Key了。

那将问题抽象化之后会发现什么?之前我们还在发散思维,思索有多少种不同的缓存情形。现在我们发现,其实所有的缓存情形都可以抽象成一种情形:对执行具体操作函数的返回结果进行缓存。同时得到一个统一的、几乎万能的解决方案:将需要对结果进行缓存的操作放到一个函数中,只需对该函数调用的返回结果进行缓存就行了。而这种函数调用缓存技术有一个专门的术语:Memoization

Memoization适用范围

设计良好的函数通常尽量遵循这些简单的原则:输入相同的参数总是返回相同的值(纯函数),它的返回值只受它的参数影响,不依赖于其它全局状态;没有副作用。比如一个简单的加法函数:function add($a,$b) { return $a+$b; } 。这样的函数可以安全使用Memoization,因为它输入相同的参数总是返回相同的结果,所以函数名加上参数值即是一个自动生成的缓存Key。但是现实中很多和外部有数据交互的函数(IO)并不具备这样的特性,如上面的query_posts函数,它的返回结果由数据库中的内容决定,如果该Author有新的Article提交到数据库中,那么即使相同的 $author 参数,返回结果也不一样了。对于这样的函数,我们需要用一种变通的方案:我们可以近似地认为,包含IO的函数在同一个缓存周期内其行为一致性(即相同参数返回相同结果)是有保证的。如,我们对数据库查询允许有10分钟的缓存,那么我们就可以认为,相同的查询,在10分钟内,它可以始终只返回相同的结果。这样包含IO的函数也可以使用具有缓存过期时间的Memoization,而这类情形在真实环境中也更为常见。

Memoization基本实现

根据前面的分析,Memoization函数(即前面列出的要实现的cache_operation函数)的接口及工作方式应该是这样的:

/**
memoize_call 将$fn函数调用的结果进行缓存
@param {String} $fn 执行操作的函数名
@param {Array} $args  调用$fn的参数
@return $fn执行返回的结果,也可能是从缓存中取到
*/
function memoize_call($fn,$args) {
  global $cache;
  # 函数名和序列化的参数值构成Cache Key
  $cacheKey=$fn.':'.serialize($args);
  # 根据Cache Key,查询缓存
  $results=$cache->get($cacheKey);
  if (false===$results) { # 缓存没有命中则调用函数
    $results=call_user_func_array($fn,$args);
    $cache->set($cacheKey,$results);
  }
  return $results;
}
# 下面给出一个示例的Cache实现,以便使这段代码可以成功运行
class DemoCache {
  private $db;
  public function __construct() {$this->db=array();}
  public function set($k,$v) {$this->db[$k]=$v;}
  public function get($k) {
    return array_key_exists($k,$this->db)?$this->db[$k]:false;
  }
}
$cache=new DemoCache();
# 比如对于add函数,调用方式为:
memoize_call('add',array(3,6));

注意这里需要使用序列化方法serialize函数将参数转换成String,序列化方法会严格保留值的类型信息,可以保证不同的参数序列化得到的String Key不会冲突。除了serialize函数,也可以考虑使用json_encode等方法。

Memoization接口人性化

至此我们已经实现了缓存Key的统一管理,但这个实现却给我们带来了麻烦,原本简简单单的add($a,$b)现在竟要写成memoize_call('add',array($a,$b))!这简直就是反人类!
…………那该怎么解决这个问题呢?
…………也许你可以这样写:

function _search_google() {/*BA LA BA LA*/}
function search_google() {
  return memoize_call('_search_google',func_get_args());
}
//缓存化的函数调用方式总算不再非主流了
echo search_google('Hacker'); //直接调用就行了

至少正常一点了。但还是很麻烦啊,本来只要写一个函数的,现在要写两个函数了!这时,匿名函数闪亮登场!(没错,只有在PHP5.3之后才可以使用Closure,但这关头谁还敢提更反人类的create_function?)使用Closure重写一下会变成啥样呢?

function search_google() {
  return memoize_call(function () {/*BA LA BA LA*/},func_get_args());
}

还不是一样嘛!还是一堆重复的代码!程序主逻辑又被套了一层厚大衣!
别忙下结论,再看看这个:

function memoized($fn) {
  return function () use($fn) {
    return memoize_call($fn,func_get_args());
  };
}
function add($a,$b) { return $a+$b; }
# 生成新函数,不影响原来的函数
$add=memoized('add');
# 后面全部使用$add函数
$add(1,2);

是不是感觉清爽多了?……还不行?
是啊,仍然会有两个函数!但是这个真没办法,PHP的全局函数名其实是字符串常量,所以你没办法创建一个同名的新函数覆盖掉旧函数。如果是JavaScript完全可以这样写嘛:add=memoized(add),如果是Python还可以直接用Decorators多方便啊!

没办法,这就是PHP!

……不过,我们确实还有相对更好的办法的。仍然从削减冗余代码入手!看这一行:
$add=memoized('add');
如果我们通过规约要求Memoized函数名的生成遵守固定的规则,那么生成新的缓存函数这个步骤就可以通过程序自动处理。比如规定所有需要Memoize的函数命名都使用_memoizable后缀,然后自动生成去掉后缀的新的变量函数:

# add函数声明时加一个后缀表示它是可缓存的
# 对应自动创建的变量函数名就是$add
function add_memoizable($a,$b) {return $a+$b;}
# 自动发现那些具有指定后缀的函数
# 并创建对应没有后缀的变量函数
function auto_create_memoized_function() {
  $suffix='_memoizable';
  $suffixLen=strlen($suffix);
  $fns=get_defined_functions();
  foreach ($fns['user'] as $f) {
    //function name ends with suffix
    if (substr_compare($f,$suffix,-$suffixLen)===0) {
      $newFn=substr($f,0,-$suffixLen);
      $GLOBALS[$newFn]=memoized($f);
    }
  }
}
# 只需在所有可缓存函数声明之后添加上这个
auto_create_memoized_function();
# 就自动生成对应的没有后缀的变量函数了
$add(3.1415,2.141);

这就是CoC(Convention over Configuration)的好处,帮我们省去了不少重复代码。

怎么?还不满意?总觉得变量函数用起来有点别扭是吧。其实,虽然全局函数我们拿它没辙,但对象的方法调用则可以做些Hack!PHP的魔术方法提供了很多机会!

静态方法重载:__callStatic

Class的静态方法__callStatic可用于拦截对未定义静态方法的调用,该特性也是在PHP5.3开始支持。将前面的CoC命名后缀方案应用到对象静态方法上,事情就变得非常简单了。将需要应用缓存的函数定义为Class静态方法,在命名时添加上后缀,调用时则不使用后缀,通过 __callStatic 方法重载,自动调用缓存方法,一切就OK了。

define('MEMOIZABLE_SUFFIX','_memoizable');
class Memoizable {
  public static function __callStatic($name,$args) {
    $realName=$name.MEMOIZABLE_SUFFIX;
    if (method_exists(__CLASS__,$realName)) {
      return memoize_call(__CLASS__."::$realName",$args);
    }
    throw new Exception("Undefined method ".__CLASS__."::$name();");
  }
  public static function search_memoizable($k) {return "Searching:$k";}
}
# 调用时则不添加后缀
echo Memoizable::search('Lisp');

实例方法重载:__call

同样对象实例方法也可使用这个Hack。在对象上调用一个不可访问方法时,__call会被调用。对照前面 __callStatic 依样画葫芦,只要稍作改动就可得到 __call 方法:

class Memoizable {
  public function __call($name,$args) {
    $realName=$name.MEMOIZABLE_SUFFIX;
    if (method_exists($this,$realName)) {
      return memoize_call(array($this,$realName),$args);
    }
    $cls=get_class($this);
    throw new Exception("Undefined method ".$cls."->$name()");
  }
  public function add_memoizable($a,$b) {return $a+$b;}
}
# 调用实例方法时不带后缀
$m=new Memoizable;
$m->add(3E5,7E3);

运行一下会得到一个错误,因为前面memoize_call函数的第一个参数只接受String类型的函数名,PHP的call_user_func_array方法本可以接受Array参数表示的一个对象方法调用,这里传了个数组: array($this,$realName)。如果$fn参数传入一个数组,生成缓存Key则成了问题。对于Class静态方法,可以使用Class::staticMethod格式的字符串表示,与普通函数名并无差别。对于实例方法,最简单的方式是将memoize_call修改成对$fn参数也序列化成字符串以生成缓存Key:

function memoize_call(callable $fn,$args) {
  # 函数名和参数值都进行序列化
  $cacheKey=serialize($fn).':'.serialize($args);
  // .....
}

PHP 5.4起可以使用callable参数类型提示,见:Callable Type Hint。具体格式可见 is_callable 函数的示例。

但这样会带来一些不必要的开销。对于复杂的对象,它的被缓存方法可能只访问了它的一个属性,而直接序列化对象会将它全部属性值都序列化进Key,这样不但Key体积会变得很大,而且一旦其它不相关的属性值发生了变化,缓存也就失效了。

对此问题的第一反应可能是……将代码改成:只序列化该方法中使用到的属性值。随之而来的障碍是,我们根本没有办法在运行时分析出方法M到底访问了$this的哪几个属性。对此或许我们可以手动在代码中声明方法M访问了对象哪几个属性,可以在类中静态声明一张表存放相关信息。或者本着Hack到底(分明是折腾到底)的精神,为了能自动获取方法访问过哪些属性,我们还可以依葫芦画瓢,参照前面Memoizable方法调用拦截,再搞出这样一个 CoC 方案:属性定义时也都添加上_memoizable后缀,访问时则不带后缀,通过__get方法,我们就可以在方法执行完后,得到这一次该方法访问过的属性列表了(但Memoize不是需要在函数调用之前就得确定缓存Key么?这样才能查看缓存是否命中以决定是否要执行该方法啊?这个简单,对方法M访问了对象哪些属性也进行缓存,就不用每次都执行了)。

不过,Stop!我们不能真的这么干!这样会把事情搞得越来越复杂。我们不能在错误的道路上越走越远!有些问题我们应该让它消失掉而不是去解决掉。我们应避免对实例方法进行缓存,因为实例方法通常都不是纯函数,它依赖于$this的状态,因此它也不适用于Memoization,依赖于全局变量的函数也是如此。 通常情况下对静态方法缓存已经够用了,如果实例方法需要缓存,可以考虑重构代码提取出一个可缓存的纯函数出来。

重载方法可重用化

如果要将这里的__callStatic__call 代码重用,可将其作为一个BaseClass,让需要Memoize功能的子类去继承:

class ArticleModel extends Memoizable {
  public static function getByAuthor_memoizable() {/*...*/}
}

试一下,便会发现这样是行不通的。在__callStatic中,我们直接使用了Magic Constants__CLASS__,来得到当前类名。但这个变量的值是它在代码中所在的类的名称,而不是运行时调用此方法的类的名称。即这里的__CLASS__的值永远是Memoizable。这问题并不很难解决,只要升级到PHP5.3,将__CLASS__替换成get_called_class()就行了。然而还有另外一个问题,PHP的Class是不支持多继承的,如果一个类已经继承了另外一个类,就不好再使用继承的方式实现Memoize代码重用了。这问题仍然不难解决,只要升级到PHP5.4,使用Traits就可以实现Mixin了。并且,使用 Traits 之后,就可以直接使用__CLASS__常量而不需要改成调用get_called_class()函数了,真是一举两得:

trait Memoizable {
  public static function __callStatic() {
    echo __CLASS__; # => 输出use trait的那个CLASS名称
  }
}
class ArticleModel {
  use Memoizable;
  public static function getByAuthor_memoizable() {/*...*/}
}

只是你需要升级到PHP5.4。也许有一天一个新的PHP版本会支持Python那样的Decorators吧,不过那时估计我已不再关注PHP,更不会回来更新这篇文章的内容了。

缓存过期时间

前面讲到,在现实世界中,通常都是对IO操作进行缓存,而包含IO操作的函数都不是纯函数。纯函数的缓存可以永不过期,而IO操作都需要一个缓存过期时间。现在问题不是过期时间到底设置成多长,这个问题应该交给每个不同的函数去设定,因为不同的操作其缓存时长是不一样的。现在的问题是,我们已经将缓存函数抽取了出来,让函数代码自身无需关心具体的缓存操作。可现在又要自己设置缓存过期时长,需要向这个memoize_call函数传递一个$expires参数,以在$cache->set时再传给MemCache实例。初级解决方案:类中所有方法的缓存过期时长,可以用一个Class::methodMemoizeExpires数组来配置映射。不过,我们不能一直这样停留在初级阶段百年不变!设想中最好的方案当然是将缓存过期时长和方法代码放一起,分开来写肯定不利于维护。可如何实现呢?前面已经将PHP的魔术方法差不多都用遍了,现在必须换个招术了。一直被遗忘在角落里的静态变量反射机制,终于也能派上用场了!

缓存过期时间,声明成函数的一个静态变量:

function search_google_memoizable($keywords) {
  static $memoizeExpires=600;//单位:秒
}

通过ReflectionFunctiongetStaticVariables方法,即可获取到函数设置的$memoizeExpires值:

$rf=new ReflectionFunction('search_google_memoizable');
$staticVars=$rf->getStaticVariables();
$expires=$staticVars['memoizeExpires'];

举一反三,类静态方法及实例方法,都可以通过ReflectionClassReflectionMethod这些途径获取到静态变量的值。

通过PHP C Extension实现Memoize

前面讨论了那么多,大部分的篇幅都是在讨论如何让缓存化函数的调用方式更优雅,尽量和普通调用保持一致。 筋疲力竭之后又突然想起来,虽然PHP代码中无法覆盖一个已经定义的函数,但PHP C Extension则可以做到!正好,PECL上已经有一个C实现的Memoize模块,不过目前仍然是Beta版。可以通过下面的命令安装:

sudo pecl install memoize-beta

该模块工作方式正如前面PHP代码所想要实现却又实现不了的那样。它提供一个memoize函数,将一个用户定义的函数修改成一个缓存化函数。主要步骤和前面的PHP实现方案并无二致,本质上是通过memoize("fn")创建一个新的函数(类似前面PHP实现的memoized),新的函数执行memoize_call在缓存不命中时再调用原来的函数,只不过C扩展可以修改函数表,将旧的函数重命名成fn$memoizd,将新创建的函数命名成fn并覆盖用户定义的函数:

function hack($x) {sleep(3);return "Hack $x\n";}
memoize('hack');
echo hack('PHP'); # returns in 3s
echo hack('PHP'); # returns in 0.0001s
$fns=get_defined_functions();
echo implode(' ',$fns['user']); # => hack$memoizd
# 函数hack现在变成internal了
var_dump(in_array('hack',$fns['internal'])); # => bool(true)

由于新函数是memcpy其内置函数memoize_call,所以变成了internal。

分析下memoize函数部分C代码可见基本逻辑和前面PHP实现是一样的:

PHP_FUNCTION(memoize)
{
  zval *callable;
  /*...*/
  zend_function *fe, *dfe, func, *new_dfe;
  /*默认为全局函数表,EG宏获取当前的executor_globals*/
  HashTable *function_table = EG(function_table);
  /*...*/
  /*检查第一个参数是否is_callable*/
  if (Z_TYPE_P(callable) == IS_ARRAY) {
    /*callable是数组则可能为类静态方法或对象实例方法*/
    zval **fname_zv, **obj_zv;
    /*省略:obj_zv=callable[0],fname_zv=callable[1]*/
    if (obj_zv && fname_zv &&
        (Z_TYPE_PP(obj_zv)==IS_OBJECT || Z_TYPE_PP(obj_zv)==IS_STRING) &&
         Z_TYPE_PP(fname_zv)==IS_STRING) {
      /* looks like a valid callback */
      zend_class_entry *ce, **pce;
      if (Z_TYPE_PP(obj_zv)==IS_OBJECT) {/*obj_zv是对象*/
        /*获取对象的class entry,见zend_get_class_entry*/
        ce = Z_OBJCE_PP(obj_zv);
      } else if (Z_TYPE_PP(obj_zv)==IS_STRING) {/*obj_zv为string则是类名*/
        if (zend_lookup_class(Z_STRVAL_PP(obj_zv),
          Z_STRLEN_PP(obj_zv),&pce TSRMLS_CC)==FAILURE){/*...*/}
        ce = *pce;
      }
      /*当callable为array时,则使用该Class的函数表*/
      function_table = &ce->function_table;
      /*PHP中函数名不区分大小写,所以这里全转成小写*/
      fname = zend_str_tolower_dup(Z_STRVAL_PP(fname_zv),Z_STRLEN_PP(fname_zv));
      fname_len = Z_STRLEN_PP(fname_zv);
      /*检查方法是否存在*/
      if (zend_hash_exists(function_table,fname,fname_len+1)==FAILURE) {/*RET FALSE*/}
    } else {/*RET FALSE*/}
  } else if (Z_TYPE_P(callable) == IS_STRING) {/*普通全局函数,省略*/
  } else {/*RET FALSE*/}
  /* find source function */
  if (zend_hash_find(function_table,fname,fname_len+1,(void**)&fe)==FAILURE){/*..*/}
  if (MEMOIZE_IS_HANDLER(fe)) {/*已经被memoize缓存化过了,RET FALSE*/}
  if (MEMOIZE_RETURNS_REFERENCE(fe)) {/*不接受返回引用的函数,RET FALSE*/}
  func = *fe;
  function_add_ref(&func);
  /* find dest function,dfe=memoize_call */
  /* copy dest entry with source name */
  new_dfe = emalloc(sizeof(zend_function));
  /*从memoize_call函数复制出一个新函数,memoize_call本身是internal的*/
  /*其实可以通过new_def->type=ZEND_USER_FUNCTION将其设置成用户函数*/
  memcpy(new_dfe, dfe, sizeof(zend_function));
  /*将复制出的memoize_call函数的scope设置成原函数的scope*/
  new_dfe->common.scope = fe->common.scope;
  /*将新函数名称设置成和原函数相同*/
  new_dfe->common.function_name = fe->common.function_name;
  /*修改function_table,将原函数名映射到新函数new_dfe*/
  if (zend_hash_update(function_table,fname,
      fname_len+1,new_dfe,sizeof(zend_function),NULL)==FAILURE){/*..*/}
  if (func.type == ZEND_INTERNAL_FUNCTION) {/*省略对internal函数的特殊处理*/}
  if (ttl) {/*省略ttl设置*/}
  /*原函数重命名成 fname$memoizd并添加到函数表*/
  new_fname_len = spprintf(&new_fname, 0, "%s%s", fname, MEMOIZE_FUNC_SUFFIX);
  if (zend_hash_add(function_table,new_fname,
      new_fname_len+1,&func,sizeof(zend_function),NULL)==FAILURE){/*RET FALSE*/}
}

memoize_call函数是不可以直接调用的,它只专门用来被复制以生成新函数的,其执行时通过自己的函数名找到对应要执行的原函数,并且同样使用serialize方法序列化参数,并取序列化结果字符串的MD5值作为缓存Key。

zend_get_class_entryzend_function等Zend API函数的源码均可通过http://lxr.php.net/在线搜索浏览。另可参考:深入理解PHP内核 — PHP函数内部实现

其它参见Github上的源码和文档:https://github.com/arraypad/php-memoize

最后

完整的PHP Memoization实现参见:
https://github.com/JexCheng/anthology/tree/master/php/Memoize

该实现覆盖了很多其它的边缘问题。比如通过Reflection API,实现了将方法参数默认值也序列化到缓存Key的功能。不过该实现现在只支持PHP5.4以后的版本。