谈一谈Redis的数据结构，如果换做PHP，怎么实现？如果再考虑用上LFU或LRU，又该如何实现？
Redis的数据结构有String、List、Set、Sorted Set、Hash等，而PHP支持String、Array、Object等八种基本数据类型。
如果换成PHP，Redis的String可以用PHP的String实现，Redis的List、Set、Sorted Set可以用PHP的索引数组实现，Redis的Hash可以用PHP的关联数组实现。
String
Redis字符串命令用于管理Redis中的字符串值。
PHP里，可以用字符串实现。
List
Redis的List是string列表，按插入顺序排序。
PHP里，可以用索引数组实现，数据结构类似于array(value1, value2, value3, ...)。
Set
Redis的Set是string类型的无序集合。集合成员是唯一的，即集合中不能出现重复的数据。
PHP里，去重过后的索引数组就相当于Redis中的Set，所以实现Set的过程与实现List相似，但需要向数组添加数据时进行去重操作，或者在添加数据前先判定该值是否存在，如果存在就不添加。
Sorted Set
Redis的Sorted Set也是string类型的无序集合,且不允许重复的成员。但每个元素都会关联一个double类型的分数，Redis通过分数来为集合中的成员进行从小到大的排序。
PHP的数组里，key不能重复，所以用key表示成员，value可以重复，所以用value表示分数，数据结构类似于array(member1=>score1, member2=>score2, member3=>score3, ...)。
Hash
Redis的Hash是一个string类型的field和value的映射表。
PHP里，可以用关联数组实现，数据结构类似于array(key1=>value1, key2=>value2, key3=>value3, ...)。
实现LFU/LRU的思路：
定义三个关联数组，key都一样，一个数组叫kv数组，存值，形如key => value；一个数组叫kc数组，存值被访问的次数，形如key => count，用于实现LFU，当缓存满了，count值最小的数据即最少被访问的数据，最先被淘汰掉；一个数组叫kt数组，形如key => time，存值最后一次被访问的时间，用于实现LRU，当缓存满了，time值最小的数据即最先被访问的数据（不是最新数据），最先被淘汰掉。
部分代码：
/*php实现redis的string*/
<?php
class stringCache
{
var $hitNume;
var $requestNum;
// 缓存类型
var $type;
// 缓存总大小
var $totalSize;
// 存值$key=>$string
var $data = array();
// 存访问次数$key=>$count
var $lfu = array();
// 存访问时间$key=>$time
var $lru = array();
public function __construct($cacheType, $totalSize) {
$this->type = $cacheType;
$this->totalSize = $totalSize;
}
/* SET key value [EX seconds] [PX milliseconds] [NX|XX]
* 将字符串值 value 关联到 key 。
* 如果 key 已经持有其他值， SET 就覆写旧值，无视类型。
* 对于某个原本带有生存时间（TTL）的键来说， 当 SET 命令成功在这个键上执行时， 这个键原有的 TTL 将被清除。
* */
public function add($key, $value) {
$this->cleanup();
$this->data[$key] = $value;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
return true;
}
/* GET key
* 返回 key 所关联的字符串值。
* 如果 key 不存在那么返回特殊值 nil 。
* 假如 key 储存的值不是字符串类型，返回一个错误，因为 GET 只能用于处理字符串值。
* */
public function get($key) {
$value = "";
$this->requestNum += 1;
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
if (is_string($this->data[$key])) {
$value = $this->data[$key];
}
}
return $value;
}
/* APPEND key value
* 如果 key 已经存在并且是一个字符串， APPEND 命令将 value 追加到 key 原来的值的末尾。
* 如果 key 不存在， APPEND 就简单地将给定 key 设为 value ，就像执行 SET key value 一样。
* 返回追加 value 之后 key 中字符串的长度。
*/
public function append($key, $value) {
$this->requestNum += 1;
if ($this->data[$key]) {
$this->hitNum += 1;
$this->data[$key] .= $value;
} else {
$this->data[$key] = $value;
}
$len = strlen($this->data[$key]);
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
return $len;
}
// 清除缓存
public function cleanup() {
if (count($this->data) == $this->totalSize) {
if ($this->type == "lfu") {
asort($this->lfu);
$keys = array_keys($this->lfu);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lfu[$k]);
}
if ($this->type == "lru") {
asort($this->lru);
$keys = array_keys($this->lru);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lru[$k]);
}
}
return true;
}
}
/*php实现redis的list*/
class listCache
{
var $hitNume;
var $requestNum;
// 缓存类型
var $type;
// 缓存总大小
var $totalSize;
// 存值$key=>$array
var $data = array();
// 存访问次数$key=>$count
var $lfu = array();
// 存访问时间$key=>$time
var $lru = array();
public function __construct($cacheType, $totalSize) {
$this->type = $cacheType;
$this->totalSize = $totalSize;
}
/* LINDEX key index
* 返回列表 key 中，下标为 index 的元素。
* 下标(index)参数 start 和 stop 都以 0 为底，也就是说，以 0 表示列表的第一个元素，以 1 表示列表的第二个元素，以此类推。
* 你也可以使用负数下标，以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。
* 如果 key 不是列表类型，返回一个错误。
*/
public function get($key, $index) {
$this->requestNum += 1;
$result = "";
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
$result = $this->data[$key][$index];
}
return $result;
}
// 清除缓存
public function cleanup() {
if (count($this->data) == $this->totalSize) {
if ($this->type == "lfu") {
asort($this->lfu);
$keys = array_keys($this->lfu);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lfu[$k]);
}
if ($this->type == "lru") {
asort($this->lru);
$keys = array_keys($this->lru);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lru[$k]);
}
}
return true;
}
/* LINSERT key BEFORE|AFTER pivot value
* 将值 value 插入到列表 key 当中，位于值 pivot 之前或之后。
* 当 pivot 不存在于列表 key 时，不执行任何操作。
* 当 key 不存在时， key 被视为空列表，不执行任何操作。
* 如果 key 不是列表类型，返回一个错误。
* @param $pos before或after，在存在的值之前插入还是之后插入
* @param $pivot 列表里存在的值
* @param $value 要插入的值
* @return 如果命令执行成功，返回插入操作完成之后，列表的长度。
如果没有找到 pivot ，返回 -1 。
如果 key 不存在或为空列表，返回 0 。
*/
public function insert($key, $pos, $pivot, $value) {
$this->cleanup();
$result = 0;
if ($this->data[$key]) {
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
$index = array_search($pivot, $this->data[$key]);
if ($index !== false) { // 找到pivot
if ($pos == "before") {
array_splice($this->data[$key], $index, 0, array($value));
} else { // after
array_splice($this->data[$key], $index + 1, 0, array($value));
}
$result = count($this->data[$key]);
} else {
$result = -1;
}
}
return $result;
}
/* LPOP key
* 移除并返回列表 key 的头元素。
* 相当于php的array_shift()函数
*/
public function lpop($key) {
$this->requestNum += 1;
$result = "";
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
$result = array_shift($this->data[$key]);
}
return $result;
}
/* LPUSH key value [value ...]
* 将一个或多个值 value 插入到列表 key 的表头
* 如果有多个 value 值，那么各个 value 值按从左到右的顺序依次插入到表头：比如说，对空列表 mylist 执行命令 LPUSH mylist a b c ，列表的值将是 c b a ，
这等同于原子性地执行 LPUSH mylist a 、 LPUSH mylist b 和 LPUSH mylist c 三个命令。
* 如果 key 不存在，一个空列表会被创建并执行 LPUSH 操作。
* 当 key 存在但不是列表类型时，返回一个错误。
* 返回执行 LPUSH 命令后列表的长度。
* @param string $values 一个或多个值，用“,”隔开
*/
public function lpush($key, $values) {
$this->cleanup();
$values_arr = explode(",", $values);
$cnt = count($values_arr);
for ($i = 0; $i <= $cnt - 1; $i++) {
$value = array_pop($values_arr);
$this->data[$key][] = $value;
}
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
return count($this->data[$key]);
}
/* RPOP key
* 移除并返回列表 key 的尾元素。
* 相当于php的array_pop()函数
*/
public function rpop($key) {
$this->requestNum += 1;
$result = "";
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
$result = array_pop($this->data[$key]);
}
return $result;
}
/* RPUSH key value [value ...]
* 将一个或多个值 value 插入到列表 key 的表尾(最右边)。
* 如果有多个 value 值，那么各个 value 值按从左到右的顺序依次插入到表尾：比如对一个空列表 mylist 执行 RPUSH mylist a b c ，得出的结果列表为 a b c，
等同于执行命令 RPUSH mylist a 、 RPUSH mylist b 、 RPUSH mylist c 。
* 如果 key 不存在，一个空列表会被创建并执行 RPUSH 操作。
* 当 key 存在但不是列表类型时，返回一个错误。
* 返回执行 RPUSH 操作后表的长度。
* @param string $values 一个或多个值，用“,”隔开
*/
public function rpush($key, $values) {
$this->cleanup();
$values_arr = explode(",", $values);
foreach ($values_arr as $v) {
$this->data[$key][] = $v;
}
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
return count($this->data[$key]);
}
}
/*php实现redis的set*/
class setCache
{
var $hitNume;
var $requestNum;
// 缓存类型
var $type;
// 缓存总大小
var $totalSize;
// 存值$key=>$array
var $data = array();
// 存访问次数$key=>$count
var $lfu = array();
// 存访问时间$key=>$time
var $lru = array();
public function __construct($cacheType, $totalSize) {
$this->type = $cacheType;
$this->totalSize = $totalSize;
}
/* SMEMBERS key
* 返回集合 key 中的所有成员。
* 不存在的 key 被视为空集合。
*/
public function getMembers($key) {
$this->requestNum += 1;
$members = array();
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
$members = $this->data[$key];
}
return $members;
}
/* SADD key member [member ...]
* 将一个或多个 member 元素加入到集合 key 当中，已经存在于集合的 member 元素将被忽略。
* 假如 key 不存在，则创建一个只包含 member 元素作成员的集合。
*/
public function add($key, $member) {
$this->cleanup();
$this->data[$key][] = $member;
$result = array_unique($this->data);
$this->data = $result;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
return true;
}
// 清除缓存
public function cleanup() {
if (count($this->data) == $this->totalSize) {
if ($this->type == "lfu") {
asort($this->lfu);
$keys = array_keys($this->lfu);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lfu[$k]);
}
if ($this->type == "lru") {
asort($this->lru);
$keys = array_keys($this->lru);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lru[$k]);
}
}
return true;
}
/* SCARD key
* 返回集合 key 的基数(集合中元素的数量)。
* 当 key 不存在时，返回 0 。
*/
public function count($key) {
$this->requestNum += 1;
$cnt = 0;
if ($this->data[$key]) {
$this->hitNum += 1;
$cnt = count($this->data[$key]);
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
}
return $cnt;
}
/* SISMEMBER key member
* 判断 member 元素是否集合 key 的成员。
* 如果 member 元素是集合的成员，返回 1 。
* 如果 member 元素不是集合的成员，或 key 不存在，返回 0 。
*/
public function isMember($key, $member) {
$this->requestNum += 1;
$flag = 0;
if($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
if (in_array($member, $this->data[$key])) {
$flag = 1;
}
}
return $flag;
}
/* SPOP key
* 移除并返回集合中的一个随机元素。
* 如果只想获取一个随机元素，但不想该元素从集合中被移除的话，可以使用 SRANDMEMBER 命令。
*/
public function randomDel($key) {
$this->requestNum += 1;
$result = "";
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
$randomKey = array_rand($this->data[$key]);
$result = $this->data[$key][$randomKey];
unset($this->data[$key][$randomKey]);
}
return $result;
}
}
/*php实现redis的sorted set*/
class sortedsetCache
{
var $hitNume;
var $requestNum;
// 缓存类型
var $type;
// 缓存总大小
var $totalSize;
// 存值$key=>$array
var $data = array();
// 存访问次数$key=>$count
var $lfu = array();
// 存访问时间$key=>$time
var $lru = array();
public function __construct($cacheType, $totalSize) {
$this->type = $cacheType;
$this->totalSize = $totalSize;
}
/* ZADD key score member [[score member] [score member] ...]
* 将一个或多个 member 元素及其 score 值加入到有序集 key 当中。
* 如果某个 member 已经是有序集的成员，那么更新这个 member 的 score 值，并通过重新插入这个 member 元素，来保证该 member 在正确的位置上。
* score 值可以是整数值或双精度浮点数。
* 如果 key 不存在，则创建一个空的有序集并执行 ZADD 操作。
* 当 key 存在但不是有序集类型时，返回一个错误。 * @param array $values [member1=>score1, member2=>score2,……]的数组
*/
public function add($key, $values) {
$this->cleanup();
foreach ($values as $member => $score) {
$this->data[$key][$member] = $score;
}
asort($this->data[$key]);
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
return true;
}
// 清除缓存
public function cleanup() {
if (count($this->data) == $this->totalSize) {
if ($this->type == "lfu") {
asort($this->lfu);
$keys = array_keys($this->lfu);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lfu[$k]);
}
if ($this->type == "lru") {
asort($this->lru);
$keys = array_keys($this->lru);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lru[$k]);
}
}
return true;
}
/* ZRANGE key start stop [WITHSCORES]
* 返回有序集 key 中，指定区间内的成员。
* 其中成员的位置按 score 值递增(从小到大)来排序。
* 具有相同 score 值的成员按字典序(lexicographical order)来排列。
* 下标参数 start 和 stop 都以 0 为底，也就是说，以 0 表示有序集第一个成员，以 1 表示有序集第二个成员，以此类推。
* 也可以使用负数下标，以 -1 表示最后一个成员， -2 表示倒数第二个成员，以此类推。
* 比如说，当 start 的值比有序集的最大下标还要大，或是 start > stop 时， ZRANGE 命令只是简单地返回一个空列表。
* 另一方面，假如 stop 参数的值比有序集的最大下标还要大，那么 Redis 将 stop 当作最大下标来处理。
* 可以通过使用 WITHSCORES 选项，来让成员和它的 score 值一并返回，返回列表以 value1,score1, ..., valueN,scoreN 的格式表示。
*/
// TODO:只考虑了下标为正的情况
public function range($key, $start, $stop, $withScore = "false") {
$this->requestNum += 1;
$res = array();
$end = $this->card($key) - 1;
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
if ($start < $stop && $start < $end) {
if ($stop > $end) {
$stop = $end;
$ks = array_keys($this->data[$key]);
for ($i = $start; $i <= $stop; $i++) {
$k = $ks[$i];
if ($withScore == "true") {
$res[] = array($k => $this->data[$key][$k]);
} else {
$res[] = $k;
}
}
}
}
}
return $res;
}
/* ZRANK key member
* 返回有序集 key 中成员 member 的排名。其中有序集成员按 score 值递增(从小到大)顺序排列。
* 排名以 0 为底，也就是说， score 值最小的成员排名为 0 。
*/
public function rank($key, $member) {
$this->requestNum += 1;
$rank = 0;
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
$rank = array_search($member, array_keys($this->data[$key]));
}
return $rank;
}
}
/*php实现redis的hash*/
class hashCache
{
var $hitNume;
var $requestNum;
// 缓存类型
var $type;
// 缓存总大小
var $totalSize;
// 存值$key=>$array
var $data = array();
// 存访问次数$key=>$count
var $lfu = array();
// 存访问时间$key=>$time
var $lru = array();
public function __construct($cacheType, $totalSize) {
$this->type = $cacheType;
$this->totalSize = $totalSize;
}
/*
* HDEL key field [field ...]
* 删除哈希表 key 中的一个或多个指定域，不存在的域将被忽略。
* fields为key中的域，多个域之间用","隔开
* 返回被成功移除的域的数量，不包括被忽略的域。
*/
public function delField($key, $fields)
{
$i = 0;
$this->requestNum += 1;
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type == "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type == "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
$fields_arr = explode(",", $fields);
foreach ($fields_arr as $field) {
if (in_array($this->data[$key][$field], $this->data[$key])) {
$i++;
unset($this->data[$key][$field]);
}
}
}
return $i;
}
/*
* HGET key field
* 返回哈希表 key 中给定域 field 的值。
* 当给定域不存在或是给定 key 不存在时，返回 nil 。
*/
public function getValue($key, $field)
{
$result = "";
$this->requestNum += 1;
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type = "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type = "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
if ($this->data[$key][$field]) {
$result = $this->data[$key][$field];
}
}
return $result;
}
/*
* HGETALL key
* 返回哈希表 key 中，所有的域和值。
* 在返回值里，紧跟每个域名(field name)之后是域的值(value)，所以返回值的长度是哈希表大小的两倍。
* 以列表形式返回哈希表的域和域的值。
* 若 key 不存在，返回空列表。
*/
public function getAll($key)
{
$result = array();
$this->requestNum += 1;
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type = "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type = "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
foreach ($this->data[$key] as $k => $v) {
$result[] = $k . "," . $v;
}
}
return $result;
}
/*
* HKEYS key
* 返回哈希表 key 中的所有域。
* 当 key 不存在时，返回一个空表。
*/
public function getFields($key)
{
$this->requestNum += 1;
$result = array();
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type = "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type = "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
foreach ($this->data[$key] as $k => $v) {
$result[] = $k;
}
}
return $result;
}
// 清除缓存
public function cleanup() {
if (count($this->data) == $this->totalSize) {
if ($this->type == "lfu") {
asort($this->lfu);
$keys = array_keys($this->lfu);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lfu[$k]);
}
if ($this->type == "lru") {
asort($this->lru);
$keys = array_keys($this->lru);
$k = $keys[0];
unset($this->data[$k]);
unset($this->lru[$k]);
}
}
return true;
}
/*
* HSET key field value
* 将哈希表 key 中的域 field 的值设置为 value。
* 如果 key 不存在，一个新哈希表被创建并执行 HSET 命令。
* 如果域 field 已经存在于哈希表中，旧值将被覆盖。
* 返回值：
如果 field 是哈希表中的一个新建域，并且值设置成功，返回 1 。
如果哈希表中域 field 已经存在且旧值已被新值覆盖，返回 0 。
*/
public function set($key, $field, $value) {
$this->cleanup();
$result = 0;
if ($this->data[$key]) {
if ($this->type = "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type = "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
if (!$this->data[$field]) {
$result = 1;
}
} else {
$result = 1;
}
$this->data[$key][$field] = $value;
return $result;
}
/*
* HVALS key
* 返回哈希表 key 中所有域的值。
* 当 key 不存在时，返回一个空表。
*/
public function getValues($key)
{
$this->requestNum += 1;
$result = array();
if ($this->data[$key]) {
$this->hitNum += 1;
if ($this->type = "lfu") {
$this->lfu[$key] += 1;
}
if ($this->type = "lru") {
$this->lru[$key] = date("Y-m-d H:i:s");
}
foreach ($this->data[$key] as $value) {
$result[] = $value;
}
}
return $result;
}
}