The example in this article describes the PHP implementation method of memcache consistent hashing. Share it with everyone for your reference. The details are as follows:
Recently, I have been reading some articles on distribution, so I used PHP to implement consistent hashing to practice. In the past, the most primitive hash modulus was generally used for distribution. When adding or deleting a memcache during the production process It will cause all data to become invalid. Consistent hashing is to solve this problem and reduce the invalid data to a minimum. You can google the relevant information!
There is a certain lack of efficiency in PHP implementation. If you want high efficiency, it is better to write extensions
After testing, 5 memcache, each memcache generates 100 virtual nodes, set and get 1000 times, which is 5 times slower than direct set and get of a single memcache, so the efficiency is average and needs to be optimized!
Before reading this article, it is best to know the binary search method.
Implementation process:
The configuration of memcache is ip+port+virtual node serial number. For hashing, crc32 is used to form a closed loop.
Perform crc32 on the key to be operated
Dichotomy to find the nearest virtual node in the virtual node ring
Extract the real memcache IP and port from the virtual node and make a single connection
The code is as follows:
class memcacheHashMap {
private $_node = array();
private $_nodeData = array();
private $_keyNode = 0;
private $_memcache = null;
//The number of virtual nodes generated by each physical server [Note: The more nodes there are, the better the uniformity of cache distribution. At the same time, the set get operation consumes more resources. For 10 physical servers, 200 is more reasonable]
private $_virtualNodeNum = 200;
private function __construct() {
$config = array(//Five memcache servers
'127.0.0.1:11211',
'127.0.0.1:11212',
'127.0.0.1:11213',
'127.0.0.1:11214',
'127.0.0.1:11215'
);
if (!$config) throw new Exception('Cache config NULL');
foreach ($config as $key => $value) {
for ($i = 0; $i < $this->_virtualNodeNum; $i++) {
$this->_node[sprintf("%u", crc32($value . '_' . $i))] = $value . '_' . $i;//Loop creates 200 for each memcache server Virtual Node
}
}
ksort($this->_node);//The 1000 virtual nodes created are sorted from small to large according to the key name
}
//Instantiate this class
static public function getInstance() {
static $memcacheObj = null;
if (!is_object($memcacheObj)) {
$memcacheObj = new self();
}
return $memcacheObj;
}
//Find the location of the corresponding virtual node according to the passed key
private function _connectMemcache($key) {
$this->_nodeData = array_keys($this->_node);//Array of keys of all virtual nodes
$this->_keyNode = sprintf("%u", crc32($key));//Calculate the hash value of the key
$nodeKey = $this->_findServerNode();//Find the corresponding virtual node
//If it exceeds the ring, use the dichotomy method from the beginning to find the closest one, and then make a judgment at the beginning and end of the ring, and take the closest node
if ($this->_keyNode > end($this->_nodeData)) {
$this->_keyNode -= end($this->_nodeData);
$nodeKey2 = $this->_findServerNode();
if (abs($nodeKey2 - $this->_keyNode) < abs($nodeKey - $this->_keyNode)) $nodeKey = $nodeKey2;
}
var_dump($this->_node[$nodeKey]);
list($config, $num) = explode('_', $this->_node[$nodeKey]);
if (!$config) throw new Exception('Cache config Error');
if (!isset($this->_memcache[$config])) {
$this->_memcache[$config] = new Memcache;
list($host, $port) = explode(':', $config);
$this->_memcache[$config]->connect($host, $port);
}
return $this->_memcache[$config];
}
//The binary method finds the nearest virtual node position based on the given value
private function _findServerNode($m = 0, $b = 0) {
$total = count($this->_nodeData);
if ($total != 0 && $b == 0) $b = $total - 1;
if ($m < $b){
$avg = intval(($m+$b) / 2);
if ($this->_nodeData[$avg] == $this->_keyNode) return $this->_nodeData[$avg];
elseif ($this->_keyNode < $this->_nodeData[$avg] && ($avg-1 >= 0)) return $this->_findServerNode($m, $avg-1);
else return $this->_findServerNode($avg+1, $b);
}
if (abs($this->_nodeData[$b] - $this->_keyNode) < abs($this->_nodeData[$m] - $this->_keyNode)) return $this-> ;_nodeData[$b];
else return $this->_nodeData[$m];
}
public function set($key, $value, $expire = 0) {
return $this->_connectMemcache($key)->set($key, json_encode($value), 0, $expire);
}
public function add($key, $value, $expire = 0) {
return $this->_connectMemcache($key)->add($key, json_encode($value), 0, $expire);
}
public function get($key) {
return json_decode($this->_connectMemcache($key)->get($key), true);
}
public function delete($key) {
return $this->_connectMemcache($key)->delete($key);
}
}
$runData['BEGIN_TIME'] = microtime(true);
//Test 10,000 times set plus get
for($i=0;$i<10000;$i++) {
$key = md5(mt_rand());
$b = memcacheHashMap::getInstance()->set($key, time(), 10);
}
var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));
$runData['BEGIN_TIME'] = microtime(true); $m= new Memcache;
$m->connect('127.0.0.1', 11211);
for($i=0;$i<10000;$i++) {
$key = md5(mt_rand());
$b = $m->set($key, time(), 0, 10);
}
var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));
?>
I hope this article will be helpful to everyone’s PHP programming design.