一致性哈希(Consistent Hashing)算法的PHP完成ITeye - 牛牛娱乐

一致性哈希(Consistent Hashing)算法的PHP完成ITeye

2019年03月13日09时49分06秒 | 作者: 思璇 | 标签: 节点,效劳,算法 | 浏览: 1312

memcache虽然是散布式的应用效劳,但散布的原则是由client端的api来决议的,api依据存储用的key以及已知的效劳器列表,依据key的hash核算将指定的key存储到对应的效劳器列表上。
一般运用的散列办法是依据 key的hash值%效劳器数取余数的办法来决议当时这个key的内容发往哪一个memcache效劳器。但这样的算法在效劳实例自身发作变化的时分,效劳列表的变化会构成简直大部分数据都会需求迁移到别的的效劳实例上。这样在大型效劳在线时,瞬时对后端数据库/硬盘照成的压力很可能导致整个效劳的crash。
在此能够选用一致性哈希(Consistent Hashing)来处理这个问题,处理效劳器的挑选不再只是依靠key的hash自身而是将效劳实例(节点)的装备也进行hash运算。

一致性哈希(Consistent Hashing)算法简述如下:
1. 求出每个效劳节点的hash,并将其装备到一个0~2^32的圆环(continuum)区间上。
2. 运用相同的办法求出你所需求存储的key的hash,也将其装备到这个圆环(continuum)上。
3. 从数据映射到的方位开端顺时针查找,将数据保存到找到的第一个效劳节点上。假如超越2^32依然找不到效劳节点,就会保存到第一个效劳节点上。

整个数据的图例:

当增加效劳器节点时:


这样做能够最大程度的避免了key在效劳节点列表上的从头散布,一起还增加了虚拟效劳节点的办法,也就是一个效劳节点在环上有多个映射点,这样就能按捺散布不均匀,最大极限地减小效劳节点增减时的缓存从头散布。具体来说,只要在圆环上增加效劳节点的方位为逆时针方向的第一个效劳节点上的键会受到影响。

以下部分为一致性哈希算法的一种PHP完成。

from: http://paul.annesley.cc/
comment: http://blog.csdn.net/mayongzhan/

?php
/**
* Flexihash - A simple consistent hashing implementation for PHP.
*
* The MIT License
*
* Copyright (c) 2008 Paul Annesley
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*
* @author Paul Annesley
* @link http://paul.annesley.cc/
* @copyright Paul Annesley, 2008
* @comment by MyZ (http://blog.csdn.net/mayongzhan/)
*/

/**
* A simple consistent hashing implementation with pluggable hash algorithms.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
class Flexihash {

    /**
    * The number of positions to hash each target to.
    *
    * @var int
    * @comment 虚拟节点数,处理节点散布不均的问题
    */
    private $_replicas = 64;

    /**
    * The hash algorithm, encapsulated in a Flexihash_Hasher implementation.
    * @var object Flexihash_Hasher
    * @comment 运用的hash办法 : md5,crc32
    */
    private $_hasher;

    /**
    * Internal counter for current number of targets.
    * @var int
    * @comment 节点记数器
    */
    private $_targetCount = 0;

    /**
    * Internal map of positions (hash outputs) to targets
    * @var array { position = target, ... }
    * @comment 方位对应节点,用于lookup中依据方位断定要拜访的节点
    */
    private $_positionToTarget = array();

    /**
    * Internal map of targets to lists of positions that target is hashed to.
    * @var array { target = [ position, position, ... ], ... }
    * @comment 节点对应方位,用于删去节点
    */
    private $_targetToPositions = array();

    /**
    * Whether the internal map of positions to targets is already sorted.
    * @var boolean
    * @comment 是否已排序
    */
    private $_positionToTargetSorted = false;

    /**
    * Constructor
    * @param object $hasher Flexihash_Hasher
    * @param int $replicas Amount of positions to hash each target to.
    * @comment 结构函数,断定要运用的hash办法和需拟节点数,虚拟节点数越多,散布越均匀,但程序的散布式运算越慢
    */
    public function __construct(Flexihash_Hasher $hasher = null, $replicas = null) {
        $this- _hasher = $hasher ? $hasher : new Flexihash_Crc32Hasher();
        if (!emptyempty($replicas)) {
            $this- _replicas = $replicas;
        }
    }

    /**
    * Add a target.
    * @param string $target
    * @chainable
    * @comment 增加节点,依据虚拟节点数,将节点散布到多个虚拟方位上
    */
    public function addTarget($target) {
        if (isset($this- _targetToPositions[$target])) {
            throw new Flexihash_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;
    }

    /**
    * Add a list of targets.
    * @param array $targets
    * @chainable
    */
    public function addTargets($targets) {
        foreach ($targets as $target) {
            $this- addTarget($target);
        }

        return $this;
    }

    /**
    * Remove a target.
    * @param string $target
    * @chainable
    */
    public function removeTarget($target) {
        if (!isset($this- _targetToPositions[$target])) {
            throw new Flexihash_Exception("Target $target does not exist.");
        }

        foreach ($this- _targetToPositions[$target] as $position) {
            unset($this- _positionToTarget[$position]);
        }

        unset($this- _targetToPositions[$target]);

        $this- _targetCount;

        return $this;
    }

    /**
    * A list of all potential targets
    * @return array
    */
    public function getAllTargets() {
        return array_keys($this- _targetToPositions);
    }

    /**
    * Looks up the target for the given resource.
    * @param string $resource
    * @return string
    */
    public function lookup($resource) {
        $targets = $this- lookupList($resource, 1);
        if (emptyempty($targets)) {
            throw new Flexihash_Exception(No targets exist);
        }
        return $targets[0];
    }

    /**
    * Get a list of targets for the resource, in order of precedence.
    * Up to $requestedCount targets are returned, less if there are fewer in total.
    *
    * @param string $resource
    * @param int $requestedCount The length of the list to return
    * @return array List of targets
    * @comment 查找当时的资源对应的节点,
    *          节点为空则回来空,节点只要一个则回来该节点,
    *          对当时资源进行hash,对一切的方位进行排序,在有序的方位列上寻觅当时资源的方位
    *          当悉数没有找到的时分,将资源的方位断定为有序方位的第一个(构成一个环)
    *          回来所找到的节点
    */
    public function lookupList($resource, $requestedCount) {
        if (!$requestedCount) {
            throw new Flexihash_Exception(Invalid count requested);
        }

        // handle no targets
        if (emptyempty($this- _positionToTarget)) {
            return array();
        }

        // optimize single target
        if ($this- _targetCount 1) {
            return array_unique(array_values($this- _positionToTarget));
        }

        // hash resource to a position
        $resourcePosition = $this- _hasher- hash($resource);

        $results = array();
        $collect = false;

        $this- _sortPositionTargets();

        // search values above the resourcePosition
        foreach ($this- _positionToTarget as $key = $value) {
            // start collecting targets after passing resource position
            if (!$collect $key $resourcePosition) {
                $collect = true;
            }

            // only collect the first instance of any target
            if ($collect !in_array($value, $results)) {
                $results []= $value;
            }

            // return when enough results, or list exhausted
            if (count($results) $requestedCount || count($results) $this- _targetCount) {
                return $results;
            }
        }

        // loop to start - search values below the resourcePosition
        foreach ($this- _positionToTarget as $key = $value) {
            if (!in_array($value, $results)) {
                $results []= $value;
            }

            // return when enough results, or list exhausted
            if (count($results) $requestedCount || count($results) $this- _targetCount) {
                return $results;
            }
        }

        // return results after iterating through both "parts"
        return $results;
    }

    public function __toString() {
        return sprintf(
            %s{targets:[%s]},
            get_class($this),
            implode(,, $this- getAllTargets())
        );
    }

    //
    // private methods

    /**
    * Sorts the internal mapping (positions to targets) by position
    */
    private function _sortPositionTargets() {
        // sort by key (position) if not already
        if (!$this- _positionToTargetSorted) {
            ksort($this- _positionToTarget, SORT_REGULAR);
            $this- _positionToTargetSorted = true;
        }
    }

}

/**
* Hashes given values into a sortable fixed size address space.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
interface Flexihash_Hasher {

    /**
    * Hashes the given string into a 32bit address space.
    *
    * Note that the output may be more than 32bits of raw data, for example
    * hexidecimal characters representing a 32bit value.
    *
    * The data must have 0xFFFFFFFF possible values, and be sortable by
    * PHP sort functions using SORT_REGULAR.
    *
    * @param string
    * @return mixed A sortable format with 0xFFFFFFFF possible values
    */
    public function hash($string);

}


/**
* Uses CRC32 to hash a value into a signed 32bit int address space.
* Under 32bit PHP this (safely) overflows into negatives ints.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
class Flexihash_Crc32Hasher
    implements Flexihash_Hasher {

    /* (non-phpdoc)
    * @see Flexihash_Hasher::hash()
    */
    public function hash($string) {
        return crc32($string);
    }

}


/**
* Uses CRC32 to hash a value into a 32bit binary string data address space.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
class Flexihash_Md5Hasher
    implements Flexihash_Hasher {

    /* (non-phpdoc)
    * @see Flexihash_Hasher::hash()
    */
    public function hash($string) {
        return substr(md5($string), 0, 8); // 8 hexits = 32bit

        // 4 bytes of binary md5 data could also be used, but
        // performance seems to be the same.
    }

}


/**
* An exception thrown by Flexihash.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
class Flexihash_Exception extends Exception {
}
版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表牛牛娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章

阅读排行

  • 1
  • 2
  • 3

    Java中字符串的使用ITeye

    字符串,字符,比较
  • 4
  • 5

    UTLITeye

    数据,目录,文件
  • 6
  • 7
  • 8

    java与函数式编程ITeye

    函数,编程,一些
  • 9
  • 10