第五周作业

<?php
class Testhash
{
    /**
     * @var int
     * @comment 虚拟节点数,解决节点分布不均的问题
     */
    private $_replicas = 64;
    /**
     * @var object
     * @comment 使用的hash方法 : md5,crc32
     */
    private $_hasher;
    /**
     * @var int
     * @comment 节点记数器
     */
    private $_targetCount = 0;
    /**
     * @var array { position => target, ... }
     * @comment 位置对应节点,用于lookup中根据位置确定要访问的节点
     */
    private $_positionToTarget = array();
    /**
     * @var array { target => [ position, position, ... ], ... }
     * @comment 节点对应位置,用于删除节点
     */
    private $_targetToPositions = array();
    /**
     * @var boolean
     * @comment 是否已排序
     */
    private $_positionToTargetSorted = false;
    /**
     * @param object $hasher
     * @param int $replicas
     * @comment 构造函数,确定要使用的hash方法和需拟节点数,虚拟节点数越多,分布越均匀,但程序的分布式运算越慢
     */
    public function __construct(Testhash_Hasher $hasher = null, $replicas = null)
    {
        $this->_hasher = $hasher ? $hasher : new Testhash_Crc32Hasher();
        if (!empty($replicas)) $this->_replicas = $replicas;
    }
    /**
     * @param string $target
     * @comment 添加节点,根据虚拟节点数,将节点分布到多个虚拟位置上
     */
    public function addTarget($target)
    {
        if (isset($this->_targetToPositions[$target]))
        {
            throw new Testhash_Exception("Target '$target' already exists.");
        }
        $this->_targetToPositions[$target] = array();
        // hash the target into multiple positions
        for ($i = 0; $i < $this->_replicas; $i++)
        {
            $position = $this->_hasher->hash($target . $i);
            $this->_positionToTarget[$position] = $target; // lookup
            $this->_targetToPositions[$target] []= $position; // target removal
        }
        $this->_positionToTargetSorted = false;
        $this->_targetCount++;
        return $this;
    }
    /**
     * @param array $targets
     * @comment 添加多个节点
     */
    public function addTargets($targets)
    {
        foreach ($targets as $target)
        {
            $this->addTarget($target);
        }
        return $this;
    }
    /**
     * @param string $target
     * @comment 删除节点
     */
    public function removeTarget($target)
    {
        if (!isset($this->_targetToPositions[$target]))
        {
            throw new Testhash_Exception("Target '$target' does not exist.");
        }
        foreach ($this->_targetToPositions[$target] as $position)
        {
            unset($this->_positionToTarget[$position]);
        }
        unset($this->_targetToPositions[$target]);
        $this->_targetCount--;
        return $this;
    }
    /**
     * @return array
     * @comment 获取所有节点
     */
    public function getAllTargets()
    {
        return array_keys($this->_targetToPositions);
    }
    /**
     * @return array
     */
    public function getAll()
    {
        return array(
            "targers"=>$this->_positionToTarget,
            "positions"=>$this->_targetToPositions);
    }
    /**
     * 查找匹配节点
     * @param string $resource
     * @return string
     */
    public function lookup($resource)
    {
        $targets = $this->lookupList($resource, 1);
        if (empty($targets)) throw new Testhash_Exception('No targets exist');
        return $targets[0]; //0表示返回离资源位置最近的机器节点
    }
    /**
     * @param string $resource
     * @param int $requestedCount 返回节点列表长度
     * @return array 节点列表
     * @comment 查找当前的资源对应的节点,
     *          节点为空则返回空,节点只有一个则返回该节点,
     *          对当前资源进行hash,对所有的位置进行排序,在有序的位置列上寻找当前资源的位置
     *          当全部没有找到的时候,将资源的位置确定为有序位置的第一个(形成一个环)
     *          返回所找到的节点
     */
    public function lookupList($resource, $requestedCount)
    {
        if (!$requestedCount)
            throw new Testhash_Exception('Invalid count requested');
        // 没有处理节点
        if (empty($this->_positionToTarget))
            return array();
        // 优化单一节点
        if ($this->_targetCount == 1)
            return array_unique(array_values($this->_positionToTarget));
        // 哈希资源到某一节点
        $resourcePosition = $this->_hasher->hash($resource);
        $results = array();
        $collect = false;
        $this->_sortPositionTargets();
        foreach ($this->_positionToTarget as $key => $value)
        {
            if (!$collect && $key > $resourcePosition)
            {
                $collect = true;
            }
            // 只收集任何节点的第一个实例
            if ($collect && !in_array($value, $results))
            {
                $results []= $value;
                //var_dump($results);
            }
            // 当结果足够或列表用尽，就返回
            //var_dump(count($results));
            //var_dump($requestedCount);
            if (count($results) == $requestedCount || count($results) == $this->_targetCount)
            {
                return $results;
            }
        }
        foreach ($this->_positionToTarget as $key => $value)
        {
            if (!in_array($value, $results))
            {
                $results []= $value;
            }
            if (count($results) == $requestedCount || count($results) == $this->_targetCount)
            {
                return $results;
            }
        }
        return $results;
    }
    public function __toString()
    {
        return sprintf(
            '%s{targets:[%s]}',
            get_class($this),
            implode(',', $this->getAllTargets())
        );
    }
    /**
     * 内部节点位置排序
     */
    private function _sortPositionTargets()
    {
        if (!$this->_positionToTargetSorted)
        {
            ksort($this->_positionToTarget, SORT_REGULAR);
            $this->_positionToTargetSorted = true;
        }
    }
}
interface Testhash_Hasher
{
    public function hash($string);
}
class Testhash_Crc32Hasher implements Testhash_Hasher
{
    public function hash($string)
    {
        return crc32($string);
    }
}
class Testhash_Md5Hasher implements Testhash_Hasher
{
    public function hash($string)
    {
        return substr(md5($string), 0, 8);
    }
}
class Testhash_Exception extends Exception
{
}

// 10个实体节点
$targets=array(
    "192.168.1.1:11011",
    "192.168.1.1:11012",
    "192.168.1.1:11013",
    "192.168.1.1:11014",
    "192.168.1.1:11015",
    "192.168.1.1:11016",
    "192.168.1.1:11017",
    "192.168.1.1:11018",
    "192.168.1.1:11019",
    "192.168.1.1:11020",
);
// 100万KV数据
$kv = 1000000;
//记录起始时间
$start_time = time();
$hasher = new Testhash_Crc32Hasher();
//可变参数 哈希方法和虚拟节点
$hash = new Testhash($hasher,64);
$point_array = [];
foreach ($targets as $v) {
    $point_array[$v] = [];
}
$hash->addTargets($targets);
for ($i=0; $i < $kv; $i++) {
    $resource = sprintf("image %d",$i);
    $hasher = $hash->lookup($resource);
    var_dump($resource." --> ".$hasher);
    $point_array[$hasher][] = $resource;
}
//记录结束时间
$end_time = time();
$cost_time = $end_time-$start_time;
$point_counter = [];
foreach ($point_array as $key=>$value) {
    $point_counter[] = count($value);
    var_dump($key."-->".count($value));
}
var_dump('标准差：'.getVariance($point_counter),'耗时：'.$cost_time.'秒');