memcached 완전 해부 3 - 분포 식 알고리즘

memcached 의 분포 식
첫 번 째 에서 소개 한 바 와 같이 memcached 는 '분포 식' 캐 시 서버 라 고 부 르 지만 서버 쪽 에는 '분포 식' 기능 이 없습니다.서버 엔 드 는 2 차, 3 차 전 사 카 가 소개 한 메모리 저장 기능 만 포함 되 어 있어 간단 하 다.memcached 의 분포 식 은 클 라 이언 트 라 이브 러 리 에서 이 루어 집 니 다.이런 분포 식 은 memcached 의 가장 큰 특징 이다.
memcached 의 분포 식 은 무슨 뜻 입 니까?
이곳 에 서 는 '분포 식' 이라는 단 어 를 여러 차례 사 용 했 지만 상세 한 설명 은 하지 않 았 다.지금부터 그 원 리 를 간단하게 소개 하 겠 습 니 다. 각 클 라 이언 트 의 실현 은 기본적으로 같 습 니 다.
다음은 memcached 서버 에 node 1 ~ node 3 대가 있다 고 가정 합 니 다. 응용 프로그램 은 키 이름 이 'tokyo', 'kanagawa', 'chiba', 'saitama', 'gunma' 인 데 이 터 를 저장 해 야 합 니 다.
그림 1 분포 식 소개: 준비
먼저 memcached 에 'tokyo' 를 추가 합 니 다.'tokyo' 를 클 라 이언 트 라 이브 러 리 에 전송 하면 클 라 이언 트 가 실현 하 는 알고리즘 은 '키' 에 따라 데 이 터 를 저장 하 는 memcached 서버 를 결정 합 니 다.서버 가 선택 하면 'tokyo' 와 그 값 을 저장 하 라 고 명령 합 니 다.
그림 2 분포 식 소개: 추가 시
마찬가지 로 '카 나 가와', '치 바', '사이 타 마', 'gunma' 는 서버 를 먼저 선택 하고 저장 합 니 다.
다음 에 저 장 된 데 이 터 를 가 져 옵 니 다.가 져 올 때 도 가 져 올 키 'tokyo' 를 함수 라 이브 러 리 에 전달 해 야 합 니 다.함수 라 이브 러 리 는 데이터 저장 시 와 같은 알고리즘 을 통 해 '키' 에 따라 서버 를 선택 합 니 다.사용 하 는 알고리즘 이 같 으 면 저장 할 때 와 같은 서버 를 선택 하고 get 명령 을 보 낼 수 있 습 니 다.데이터 가 어떤 이유 로 삭제 되 지 않 았 다 면 저 장 된 값 을 얻 을 수 있 습 니 다.
그림 3 분포 식 소개: 가 져 올 때
이렇게 하면 서로 다른 키 를 서로 다른 서버 에 저장 하면 memcached 의 분포 식 을 실현 합 니 다.memcached 서버 가 증가 하면 키 가 분 산 됩 니 다. memcached 서버 가 고장 이 나 서 연결 할 수 없 더 라 도 다른 캐 시 에 영향 을 주지 않 고 시스템 은 계속 실 행 될 수 있 습 니 다.
다음은 첫 번 째 에서 언급 한 Perl 클 라 이언 트 함수 라 이브 러 리 Cache: Memcached 가 실현 하 는 분포 식 방법 을 소개 합 니 다.
Cache:: Memcached 의 분포 식 방법
Perl 의 memcached 클 라 이언 트 함수 라 이브 러 리 Cache: Memcached 는 memcached 의 작가 Brad Fitzpatrick 의 작품 으로 원래 의 함수 라 이브 러 리 라 고 할 수 있 습 니 다.

Cache::Memcached – search.cpan.org

이 함수 라 이브 러 리 는 분포 식 기능 을 실현 하 였 으 며, memcached 표준 분포 식 방법 입 니 다.
나머지 에 따라 분산 을 계산 하 다
Cache:: Memcached 의 분포 식 방법 은 쉽게 말 하면 '서버 대수 에 따라 분산' 입 니 다.키 의 정수 해시 값 을 구하 고 서버 데스크 톱 수 를 나 누 어 나머지 숫자 에 따라 서버 를 선택 합 니 다.
다음은 Cache:: Memcached 를 다음 펄 스 크 립 트 로 간략화 하여 설명 합 니 다.

use strict; use warnings; use String::CRC32; my @nodes = ('node1','node2','node3'); my @keys = ('tokyo', 'kanagawa', 'chiba', 'saitama', 'gunma'); foreach my $key (@keys) { my $crc = crc32($key); # CRC  my $mod = $crc % ( $#nodes + 1 ); my $server = $nodes[ $mod ]; #           printf "%s => %s
", $key, $server; } 

Cache:: Memcached 는 해시 값 을 구 할 때 CRC 를 사 용 했 습 니 다.

String::CRC32 – search.cpan.org

먼저 문자열 의 CRC 값 을 구하 고, 이 값 을 서버 노드 수로 나 눈 나머지 에 따라 서버 를 결정 합 니 다.위의 코드 를 실행 한 후 다음 결 과 를 입력 하 십시오:

tokyo => node2 kanagawa => node3 chiba => node2 saitama => node1 gunma => node1 

이 결과 에 따 르 면 '토 키 오' 는 node 2, '카 나 가와' 는 node 3 등 으로 분산 됐다.한 마디 더 하 자 면 선택 한 서버 가 연결 되 지 않 을 때 Cache: Memcached 는 연결 횟수 를 키 에 추가 한 후 해시 값 을 다시 계산 하고 연결 을 시도 합 니 다.이 동작 을 rehash 라 고 합 니 다.rehash 를 원 하지 않 을 때 Cache:: Memcached 대상 을 만 들 때 "rehash = > 0" 옵션 을 지정 할 수 있 습 니 다.
나머지 에 따라 분 산 된 단점 을 계산 하 다.
나머지 계산 방법 은 간단 하고 데이터 의 분산 성도 우수 하지만 단점 도 있다.서버 를 추가 하거나 제거 할 때 캐 시 재 편의 대가 가 상당히 크다 는 것 이다.서버 를 추가 하면 나머지 는 큰 변화 가 생 겨 저장 할 때 와 같은 서버 를 가 져 올 수 없어 캐 시 명중률 에 영향 을 줍 니 다.Perl 로 세그먼트 코드 를 써 서 그 대 가 를 검증 합 니 다.

use strict; use warnings; use String::CRC32; my @nodes = @ARGV; my @keys = ('a'..'z'); my %nodes; foreach my $key ( @keys ) { my $hash = crc32($key); my $mod = $hash % ( $#nodes + 1 ); my $server = $nodes[ $mod ]; push @{ $nodes{ $server } }, $key; } foreach my $node ( sort keys %nodes ) { printf "%s: %s
", $node, join ",", @{ $nodes{$node} }; } 

이 Perl 스 크 립 트 는 "a" 에서 "z" 키 를 memcached 에 저장 하고 접근 하 는 상황 을 보 여 줍 니 다.mod. pl 로 저장 하고 실행 합 니 다.
우선, 서버 가 세 대 밖 에 없 을 때:

$ mod.pl node1 node2 nod3 node1: a,c,d,e,h,j,n,u,w,x node2: g,i,k,l,p,r,s,y node3: b,f,m,o,q,t,v,z 

결 과 는 위 와 같이 node 1 은 a, c, d, e 를 저장 하고 node 2 는 g, i, k 를 저장 하 며 서버 마다 8 개 에서 10 개의 데 이 터 를 저장 합 니 다.
다음은 memcached 서버 를 추가 합 니 다.

$ mod.pl node1 node2 node3 node4 node1: d,f,m,o,t,v node2: b,i,k,p,r,y node3: e,g,l,n,u,w node4: a,c,h,j,q,s,x,z 

node 4 가 추가 되 었 습 니 다.이 를 통 해 알 수 있 듯 이 d, i, k, p, r, y 만 명중 했다.이렇게 노드 를 추가 한 후 키 가 분 산 된 서버 에 큰 변화 가 생 길 수 있다.26 개의 키 중 6 개 만 이 원래 서버 에 접근 하고 나머지 는 모두 다른 서버 로 옮 겼 다.적중률 이 23% 로 낮 아 졌 다.웹 프로그램 에서 memcached 를 사용 할 때 memcached 서버 를 추가 하 는 순간 캐 시 효율 이 크게 떨 어 지고 부하 가 데이터베이스 서버 에 집중 되 어 정상 적 인 서 비 스 를 제공 하지 못 하 는 상황 이 발생 할 수 있 습 니 다.
mixi 의 웹 응용 프로그램 운용 에 도 이 문제 가 있어 memcached 서버 를 추가 할 수 없습니다.그러나 새로운 분포 식 방법 을 사 용 했 기 때문에 이 제 는 memcached 서버 를 쉽게 추가 할 수 있 습 니 다.이런 분포 식 방법 을 Consistent Hashing 이 라 고 부른다.
Consistent Hashing
Consistent Hashing 의 사상, mixi 주식회사 의 개발 블 로그 등 여러 곳 에서 소 개 했 는데 간단하게 설명 할 수 있 습 니 다.

mixi Engineers' Blog

ConsistentHashing – テ テ 법

Consistent Hashing 의 간단 한 설명
Consistent Hashing 은 다음 과 같 습 니 다. 먼저 memcached 서버 (노드) 의 해시 값 을 구하 고 0 ～ 2SUP (32) 의 원 (continuum) 에 설정 합 니 다.그리고 같은 방법 으로 데 이 터 를 저장 하 는 키 의 해시 값 을 구하 고 원 에 투사 합 니 다.그리고 데이터 가 비 친 위치 부터 시계 방향 으로 찾 아 첫 번 째 서버 에 데 이 터 를 저장 합 니 다.2SUP (32) 을 넘 어도 서버 를 찾 지 못 하면 첫 번 째 memcached 서버 에 저 장 됩 니 다.
그림 4 일관성 Hashing: 기본 원리
위의 그림 상태 에서 memcached 서버 를 추가 합 니 다.나머지 분산 알고리즘 은 키 를 저장 하 는 서버 에 큰 변화 가 생 겨 캐 시 명중률 에 영향 을 주지 만, Consistent Hashing 에 서 는 continuum 에 서버 의 지점 을 시계 반대 방향 으로 추가 하 는 첫 번 째 서버 의 키 만 영향 을 받는다.
그림 5 Consistent Hashing: 서버 추가
따라서 Consistent Hashing 은 키 의 재 분 포 를 최대한 억제 했다.그리고 일부 Consistent Hashing 의 실현 방법 은 가상 노드 의 사상 도 채택 했다.일반적인 hash 함 수 를 사용 하면 서버 의 맵 지점 분포 가 매우 고 르 지 않 습 니 다.따라서 가상 노드 의 사상 을 사용 하여 모든 물리 노드 (서버) 에 continuum 에서 100 ~ 200 개의 점 을 분배 한다.이렇게 하면 분포 불 균형 을 억제 하고 서버 증감 시의 캐 시 재 분 포 를 최대한 줄 일 수 있다.
다음 글 에서 소개 한 Consistent Hashing 알고리즘 을 사용 한 memcached 클 라 이언 트 함수 라 이브 러 리 를 통 해 테스트 한 결과 서버 대수 (n) 와 증가 한 서버 대수 (m) 로 서버 를 증가 시 킨 명중률 계산 공식 은 다음 과 같다.

(1 - n/(n+m)) * 100 

Consistent Hashing 을 지원 하 는 함수 라 이브 러 리
이 연재 에서 여러 차례 소 개 된 Cache:: Memcached 는 Consistent Hashing 을 지원 하지 않 지만 몇 개의 클 라 이언 트 함수 라 이브 러 리 가 이러한 새로운 분포 식 알고리즘 을 지원 합 니 다.첫 번 째 로 Consistent Hashing 과 가상 노드 를 지원 하 는 memcached 클 라 이언 트 함수 라 이브 러 리 는 libketama 라 는 PHP 라 이브 러 리 로 last. fm 에서 개발 되 었 습 니 다.

libketama – a consistent hashing algo for memcache clients – RJ ブログ – Users at Last.fm

Perl 클 라 이언 트 에 대해 연 재 된 첫 번 째 Cache:: Memcached:: Fast 와 Cache:: Memcached:: libmemcached 는 Consistent Hashing 을 지원 합 니 다.

Cache::Memcached::Fast – search.cpan.org

Cache::Memcached::libmemcached – search.cpan.org

두 개의 인 터 페 이 스 는 모두 Cache:: Memcached 와 거의 같 습 니 다. Cache:: Memcached 를 사용 하고 있다 면 편리 하 게 교체 할 수 있 습 니 다.Cache:: Memcached:: Fast 가 libketama 를 다시 실 현 했 습 니 다. Consistent Hashing 을 사용 하여 대상 을 만 들 때 ketama 를 지정 할 수 있 습 니 다.points 옵션.

my $memcached = Cache::Memcached::Fast->new({ servers => ["192.168.0.1:11211","192.168.0.2:11211"], ketama_points => 150 }); 

또한, Cache:: Memcached:: libmemcached 는 Brain Aker 가 개발 한 C 함수 라 이브 러 리 libmemcached 를 사용 한 Perl 모듈 입 니 다.libmemcached 자 체 는 몇 가지 분포 식 알고리즘 을 지원 하고 Consistent Hashing 도 지원 하 며 Perl 바 인 딩 도 Consistent Hashing 을 지원 합 니 다.

Tangent Software: libmemcached

총결산
이번 에는 memcached 의 분포 식 알고리즘 을 소 개 했 는데 주로 memcached 의 분포 식 은 클 라 이언 트 함수 라 이브 러 리 에서 이 루어 지고 데 이 터 를 효율적으로 분산 시 키 는 Consistent Hashing 알고리즘 이 있다.다음 에는 mixi 가 memcached 응용 분야 에서 의 경험 과 관련 된 호 환 응용 프로그램 을 소개 합 니 다.
다음으로 이동:http://tech.idv2.com/2008/07/24/memcached-004/comment-page-2/#comment-457314