Memoization in PHP_PHP教程-PHP Tutorial-php.cn

谈到PHP应用的性能优化，很多人最先想到的肯定是缓存。因为一般的程序不会用PHP进行太多的计算，算法优化的余地很小，所以性能瓶颈不会出现在CPU上，而更可能出现在IO上。而IO操作最需要缓存的莫过于耗时的数据库查询了。最常见的缓存使用情形就是类似这样的一次查询：

function query_author_articles($author) {
  global $pdo,$memcache;
  $sql='SELECT * FROM `articles` WHERE author=:author ORDER BY `date` DESC';
  $cacheKey="author_{$author}_articles";
  $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;
}

Copy after login

除了SQL查询，还有哪些IO情形需要缓存呢？ —— 当然少不了外部网络接口请求了！比如请求Google搜索结果，尽管Google服务器处理查询很快，但这个请求完成仍需要很长时间，不但因为建立HTTPS连接比建立HTTP连接更耗时、以及这个URL会产生302跳转，更是因为（此处已被屏蔽，请自行脑补）。示例代码如下：

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

Copy after login

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

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

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

Copy after login

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

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

Copy after login

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

那将问题抽象化之后，我们能发现什么？之前我们还在发散思维，努力思索着有多少种不同情形的缓存，现在，我们发现所有的缓存情形都可以归类成一种情形：对执行具体操作函数的返回结果进行缓存。同时得到一个统一的解决方案：将需要对结果进行缓存的操作放到一个函数中，只需要对该函数调用的返回结果进行缓存就行了。而这种函数调用缓存技术有一个专门的术语：Memoization。唉～说半天就是为了讲明白为什么需要Memoization！

Memoization适用范围

设计良好的函数通常尽量遵循这些简单的原则：输入相同的参数总是返回相同的值（纯函数），它的返回值只受它的参数影响，不依赖于其它全局状态；没有副作用。比如一个简单的加法函数：function add($a,$b) { return $a+$b; } 。这样的函数可以安全使用Memoization，因为它输入相同的参数总是返回相同的结果，所以函数名加上参数值即是一个自动生成的缓存Key。但是现实中很多和外部有数据交互的函数（IO）并不具备这样的特性，如上面的query_author_articles函数，它的返回结果由数据库中的内容决定，如果该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 $store;
  public function __construct() {$this->store=array();}
  public function set($key,$value) {$this->store[$key]=$value;}
  public function get($key) {
    return array_key_exists($key,$this->store)?$this->store[$key]:false;
  }
}
$cache=new DemoCache();
# 比如对于add函数，调用方式为：
memoize_call('add',array(3,6));

Copy after login

注意这里需要使用序列化方法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'); //直接调用就行了

Copy after login

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

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

Copy after login

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

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(1E4,3E4);

Copy after login

是不是感觉清爽多了？……还不行？
是啊，仍然会有两个函数！但是这个真没办法，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);

Copy after login

还不满意？好好的都变成了变量函数，使用起来仍然不便。其实，虽然全局函数我们拿它没辙，但我们还可以在对象的方法调用上做很多Hack！PHP的魔术方法提供了很多机会！

静态方法重载：__callStatic

Class的静态方法__callStatic可用于拦截对未定义静态方法的调用，该特性也是在PHP5.3开始支持。将前面的命名后缀方案应用到对象静态方法上，事情就变得非常简单了。将需要应用缓存的函数定义为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');

Copy after login

实例方法重载：__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);
    }
    throw new Exception("Undefined method ".get_class($this)."->$name();");
  }
  public function add_memoizable($a,$b) {return $a+$b;}
}
# 调用实例方法时不带后缀
$m=new Memoizable;
$m->add(3E5,7E3);

Copy after login

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

function memoize_call(callable $fn,$args) {
  global $cache;
  # 函数名和参数值都进行序列化
  $cacheKey=serialize($fn).':'.serialize($args);
  $results=$cache->get($cacheKey);
  if (false===$results) {
    $results=call_user_func_array($fn,$args);
    $cache->set($cacheKey,$results);
  }
  return $results;
}

Copy after login

PHP 5.4开始可以使用callable参数类型提示，见：Callable Type Hint。Callable类型的具体格式可见 is_callable 函数的示例。

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

class Bar {
  public $tags=array('PHP','Python','Haskell');
  public $current='PHP';
  #...这里省略实现Memoizable功能的__call方法
  public function getCurrent_memoizable() {return $this->current;}
}
$b=new Bar;
$b->getCurrent();
$b->tags[0]='OCaml';
# 由于不相干的tags属性内容也被序列化放入Key
# tags被修改后，该方法的缓存就失效了
$b->getCurrent(); # 会被再次执行
# 但它的缓存不应该失效

Copy after login

对此问题的第一反应可能是……将代码改成：只序列化该方法中使用到的属性值。随之而来的障碍是，我们根本没有办法在运行时分析出方法M到底访问了$this的哪几个属性。作为一种尝试性方案，我们可以手动在代码中声明方法M访问了对象哪几个属性，可以在类中声明一个静态属性存放相关信息：

class Foo {
  public $current='PHP';
  public $hack='HACK IT';
  # 存放方法与其访问属性列表的映射
  public static $methodUsedMembers=array(
    'getCurrent_memoizable'=>'current,hack' # getCurrent访问的两个属性
  );
  public function getCurrent_memoizable() {
    return $this->current.$this->hack;
  }
}
# 这样memoize_call就可以通过$methodUsedMembers
# 得到方法M对应要序列化的属性列表
# 对应memoize_call中生成缓存Key的逻辑则是
if (is_array($fn) && is_object($fn[0])) {
  list($o,$m)=$fn;
  $class=get_class($o);
  # $members=$class::$methodUsedMembers[$m]; # PHP5.3才支持此语法
  # 如果是PHP5.3之前的版本，使用下面的方法
  $classVars=get_class_vars($class);
  $members=$classVars['methodUsedMembers'][$m];
  $objVars=get_object_vars($o);
  $objVars=array_intersect_key($objVars,array_flip(explode(',',$members)));
  # 注意要加上以类名和方法名构成的Prefix
  # 因为get_object_vars转成数组丢了Class信息
  $cacheKey=$class.'::'.$m.'::';
  $cacheKey.=serialize($objVars).':'.serialize($args);
}

Copy after login

手动声明仍然很麻烦，仍然是在Repeat Yourself。如果本着Hack到底（分明是折腾到底）的精神，为了能自动获取方法访问过哪些属性，我们还可以依葫芦画瓢，参照前面Memoizable方法调用拦截，再搞出这样一个自动化方案：属性定义时也都添加上_memoizable后缀，访问时则不带后缀，通过__get方法，我们就可以在方法执行完后，得到这一次该方法访问过的属性列表了（但Memoize不是需要在函数调用之前就要确定缓存Key么？这样才能查看缓存是否命中以决定是否要执行该方法啊？这个简单，对方法M访问了对象哪些属性也进行缓存，就不用每次都执行了）：

class Foo {
  public $propertyHack_memoizable='Hack';
  public $accessHistory=array();//记录属性访问历史
  public function __get($name) {
    $realName=$name.MEMOIZABLE_SUFFIX;
    if (property_exists($this,$realName)) {
      $this->accessHistory[]=$realName;
      return $this->$realName;
    } # otherwise throw Exception
  }
  public function hack() {return $this->propertyHack;}
}
$f=new Foo;
#方法调用前清空历史
$f->accessHistory=array();
echo $f->hack();
var_dump($f->accessHistory); # => 得到hack方法访问过的属性列表

Copy after login

不过，我们不能真的这么干！这样会把事情搞得越来越复杂。太邪门了！我们不能在错误的道路上越走越远！
适可而止吧！对于此问题，我觉得折衷方案是避免对实例方法进行缓存。因为实例方法通常都不是纯函数，它依赖于$this的状态，因此它也不适用于Memoization。正常情况下对静态方法缓存也已经够用了，如果实例方法需要缓存，可以考虑重构代码提取出一个可缓存的类静态方法出来。

重载方法可重用化

如果要将这里的__callStatic及__call 代码重用，可将其作为一个BaseClass，让需要Memoize功能的子类去继承：

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

Copy after login

试一下，便会发现这样是行不通的。在__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名称
  }
  public function __call() {/*...*/}
}
class ArticleModel {
  use Memoizable;
  public static function getByAuthor_memoizable() {/*...*/}
}

Copy after login

只是你需要升级到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;//单位：秒
}

Copy after login

通过ReflectionFunction的getStaticVariables方法，即可获取到函数设置的$memoizeExpires值：

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

Copy after login

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

通过PHP C Extension实现Memoize

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

sudo pecl install memoize-beta

Copy after login

该模块工作方式正如前面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)

Copy after login

由于新函数是memcpy其内置函数memoize_call，所以变成了internal，分析下memoize函数部分C代码可知：

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*/}
}