어떻게 PHP 로 분포 알고리즘 의 일치 성 해시 알고리즘 을 실현 합 니까?

전통 알고리즘 결함
서버 분포 에 대해 우리 가 고려 해 야 할 것 은 다음 과 같은 세 가지 가 있다.데이터 의 평균 분포,위치 추적 이 정확 하고 다운 의 영향 을 낮 춘 다.
전통 적 인 알고리즘 은 일반적으로 데이터 의 키 를 알고리즘 으로 숫자 를 비 추어 서버 수량 으로 모델 링 을 하고 결과 에 따라 저장 할 서버 를 선택한다.데이터 의 평균 분포 와 포 지 셔 닝 정확 한 요 구 를 달성 할 수 있 고 알고리즘 이 간단 하 며 액세스 할 때의 계 산 량 이 비교적 적다(데이터 가 매우 클 때 만 뚜렷 하 다)는 장점 이 있다.
그러나 한 서버 가 다운 된 후의 영향 이 매우 크다 는 치 명 적 인 단점 이 있 습 니 다.우 리 는 한 서버 가 다운 된 후의 영향 을 추산 할 수 있 습 니 다.
4.567917.기 존의 데 이 터 는 대부분 분실 되 었 습 니 다.서버 수량 이 한 대 줄 어 들 고 모드 수 감소 1 로 인해 모드 값 이 잘못 되 었 습 니 다.만약 에 예전 에 N 대의 서버 가 있 었 다 면 다운 된 데 이 터 는 1/(n*(n-1)의 데이터 만 정확하게 찾 을 수 있 습 니 다4.567917.부하 가 균형 을 이 루 지 못 해 단체 지연 을 초래 합 니 다.만약 에 지연 되 는 서버 를 제때에 처리 하지 않 으 면 그의 저장 임 무 는 순서대로 다음 서버 에 쌓 일 것 입 니 다.그러면 다음 서버 도 곧 다운 되 고 서버 팀 은 곧 단체 로 다운 될 것 입 니 다알고리즘 사상
일치 성 해시 알고리즘 은 일정한 해시 알고리즘 을 사용 하여 대량의 데 이 터 를 서로 다른 저장 목표 에 평균 적 으로 투사 하여 정확성 을 확보 하 는 동시에 그 중의 한 저장 목표 가 효력 을 잃 었 을 때 다른 저장 목표 가 책임 저장 내용 에 대한 부하 균형 도 고려 해 야 한다.
일치 성 해시 알고리즘 의 실현 사상 은 이해 하기 어렵 지 않다.그림 과 같다.

1.일정한 해시 알고리즘(해시 함수 등)으로 한 서버 의 여러 개(수량 자체 설정)노드 를 무 작위 로 0-232 사이 에 분산 시 키 고 무 작위 분포 로 인해 데이터 의 평균 분포 특징 을 확보한다.
2.같은 알고리즘 으로 데 이 터 를 저장 할 키 를 계산 하고 서버 노드 에 따라 저 장 된 서버 노드 를 확인한다.매번 같은 알고리즘 으로 계산 하기 때문에 얻 은 결 과 는 똑 같 아서 포 지 셔 닝 을 정확하게 찾 도록 한다.
3.데 이 터 를 찾 을 때 같은 알고리즘 으로 키 를 계산 하고 서버 의 데이터 노드 를 찾 습 니 다.
4.만약 에 서버 가 다운 되면 서버 의 결산 점 을 없 애고 데 이 터 를 다음 결산 점 에 놓는다.랜 덤 노드 위치의 랜 덤 성 때문에 데 이 터 는 다른 서버 에 의 해 평균 적 으로 부하 되 고 다운 의 영향 을 낮 춘 다.
주의해 야 할 것 은 이 링 공간 은 가상 공간 일 뿐 서버 가 저장 하 는 범위 와 데이터 의 타 점 을 표시 할 뿐 저장 할 때 우 리 는 찾 은 타 점 을 통 해 데 이 터 를 해당 하 는 서버 에 넣 어 수정 해 야 한 다 는 것 이다.
알고리즘 구현
프로 그래 밍 언어 우 리 는 PHP 를 사용 하여 일치 성 해시 알고리즘 을 실현 합 니 다.
우 리 는 주로 다음 과 같은 함 수 를 사용한다.
int crc32 ( string $str )
str 의 32 비트 순환 중복 검사 코드 다항식 을 생 성 합 니 다.이것 은 보통 전 송 된 데이터 가 완전 한 지 검사 하 는 데 쓰 인 다.
string sprintf ( string $format [, mixed $args [, mixed $... ]] )
들 어 오 는 형식 을 통 해 문자열 의 특정한 형식 형 태 를 만 듭 니 다.
다음 과 같이 구현:

class Consistance
{
    protected $num=24;          //            ，    ，                ，          。
    protected $nodes=array();   //           。

    //          ，      
    public function make_hash($data)
    {
        return sprintf('%u',crc32($data));
    }

    //             ，      /      
    public function set_loc($data)
    {
        $loc=self::make_hash($data);
        foreach ($this->nodes as $key => $val)
        {
            if($loc<=$key)
            {
                return $val;
            }
        }
    }

    //       ，                 。
    public function add_host($host)
    {
        for($i=0;$i<$this->num;$i++)
        {
            $key=sprintf('%u',crc32($host.'_'.$i));
            $this->nodes[$key]=$host;   
        }
        ksort($this->nodes);        //     ，      。
    }

    //       ，                    。
    public function remove_host($host)
    {
        for($i=0;$i<$this->num;$i++)
        {
            $key=sprintf('%u',crc32($host.'_'.$i));
            unset($this->nodes[$key]);
        }
    }
}

우 리 는 다음 코드 로 테스트 를 진행한다.

결 과 는 다음 과 같다.

총결산
알고리즘 의 실현 은 여기까지 입 니 다.우 리 는 또한 알고리즘 을 최적화 할 수 있 습 니 다.예 를 들 어 서버 수량 과 모든 서버 노드 수가 많은 상황 에서 결점 을 찾 는 과정 을 최적화 할 수 있 습 니 다.정렬 이 잘 되 어 있 기 때문에 이분법 으로 찾 고 조회 효율 을 가속 화 할 수 있 습 니 다.이런 것들 은 인 지 는 각자 볼 수 있 습 니 다.
또한 nginx 서버 에 일치 성 알고리즘 이 있 는 플러그 인,memcache 와 redis 에 도 해당 하 는 플러그 인 이 있 습 니 다.MySQL 의 미들웨어 는 해당 하 는 통합 이 있 지만 일치 성 해시 알고리즘 을 이해 하 는 것 도 의미 가 있 습 니 다.그리고 우 리 는 파일 등 을 분포 식 으로 관리 하 는 등 유연 하 게 사용 할 수 있다.
이상 은 어떻게 PHP 로 분포 알고리즘 의 일치 성 해시 알고리즘 을 실현 하 는 지 에 대한 상세 한 내용 입 니 다.더 많은 PHP 로 분포 알고리즘 의 일치 성 해시 알고리즘 을 실현 하 는 데 관 한 자 료 는 우리 의 다른 관련 글 을 주목 하 시기 바 랍 니 다!