1<?php
2
3/*
4 * This file is part of the Predis package.
5 *
6 * (c) Daniele Alessandri <suppakilla@gmail.com>
7 *
8 * For the full copyright and license information, please view the LICENSE
9 * file that was distributed with this source code.
10 */
11
12namespace Predis\Cluster\Distributor;
13
14/**
15 * This class implements an hashring-based distributor that uses the same
16 * algorithm of libketama to distribute keys in a cluster using client-side
17 * sharding.
18 *
19 * @author Daniele Alessandri <suppakilla@gmail.com>
20 * @author Lorenzo Castelli <lcastelli@gmail.com>
21 */
22class KetamaRing extends HashRing
23{
24    const DEFAULT_REPLICAS = 160;
25
26    /**
27     * @param mixed $nodeHashCallback Callback returning a string used to calculate the hash of nodes.
28     */
29    public function __construct($nodeHashCallback = null)
30    {
31        parent::__construct($this::DEFAULT_REPLICAS, $nodeHashCallback);
32    }
33
34    /**
35     * {@inheritdoc}
36     */
37    protected function addNodeToRing(&$ring, $node, $totalNodes, $replicas, $weightRatio)
38    {
39        $nodeObject = $node['object'];
40        $nodeHash = $this->getNodeHash($nodeObject);
41        $replicas = (int) floor($weightRatio * $totalNodes * ($replicas / 4));
42
43        for ($i = 0; $i < $replicas; ++$i) {
44            $unpackedDigest = unpack('V4', md5("$nodeHash-$i", true));
45
46            foreach ($unpackedDigest as $key) {
47                $ring[$key] = $nodeObject;
48            }
49        }
50    }
51
52    /**
53     * {@inheritdoc}
54     */
55    public function hash($value)
56    {
57        $hash = unpack('V', md5($value, true));
58
59        return $hash[1];
60    }
61
62    /**
63     * {@inheritdoc}
64     */
65    protected function wrapAroundStrategy($upper, $lower, $ringKeysCount)
66    {
67        // Binary search for the first item in ringkeys with a value greater
68        // or equal to the key. If no such item exists, return the first item.
69        return $lower < $ringKeysCount ? $lower : 0;
70    }
71}
72