분산 데이터 캐 시 에서 의 일치 성 해시 알고리즘
본 고 는 일치 성 해시 알고리즘 의 원리 와 실현 을 소개 하고 서로 다른 해시 함수 가 실현 하 는 성능 데이터 대 비 를 제시 하 며 Redis 군집 의 데이터 분할 실현 등 을 연구 하고 글 끝 에 실현 되 는 구체 적 인 github 주 소 를 제시 할 것 이다.
Memcached 와 클 라 이언 트 분포 식 캐 시
Memcached 는 고성능 분포 식 캐 시 시스템 이지 만 서버 에 분포 식 기능 이 없 으 며 각 서버 는 서로 통신 하지 않 습 니 다.그것 의 분포 식 실현 은 클 라 이언 트 의 라 이브 러 리 에 의존 하 는 것 도 Memcached 의 큰 특징 이다.예 를 들 어 제3자 의 spymemcached 클 라 이언 트 는 일치 성 해시 알고리즘 을 바탕 으로 분포 식 캐 시 기능 을 실현 했다.
그 구체 적 인 절 차 는 다음 과 같다.
이 과정 에서 클 라 이언 트 의 알고리즘 은 먼저 캐 시 된 데 이 터 를 각 서버 에 고 르 게 분포 하도록 해 야 한다. 그 다음 에 개별 서버 가 오프라인 또는 온라인 일 때 데이터 이전 이 나타 나 므 로 이전 해 야 할 데이터 양 을 최대한 줄 여야 한다.
클 라 이언 트 알고리즘 은 클 라 이언 트 분포 식 캐 시 성능 의 우열 의 관건 이다.
일반적인 해시 표 알고리즘 은 일반적으로 해시 값 을 계산 한 후 나머지 작업 을 통 해 키 값 을 서로 다른 서버 에 비 추 지만 서버 수량 이 변 할 때 나머지 작업 의 나 누 기 에 변화 가 생 겨 모든 키 가 비 추 는 서버 가 거의 변 합 니 다. 이것 은 분포 식 캐 시 시스템 에 서 는 받 을 수 없습니다.
일치 성 해시 알고리즘 은 서버 수량 변화 로 인 한 캐 시 이전 을 최대한 줄 일 수 있 습 니 다.
해시 알고리즘
우선 일치 성 해시 알고리즘 은 일반적인 해시 알고리즘 에 의존한다.대부분의 학생 들 이 해시 알고리즘 에 대한 이 해 는 JDK
hashCode 함수 에 머 물 러 있 을 수 있 습 니 다.사실 해시 알고리즘 은 여러 가지 실현 이 있 는데 그들 은 서로 다른 측면 에서 우열 을 가지 고 서로 다른 장면 에 대해 서로 다른 해시 알고리즘 을 사용 하여 실현 할 수 있다.다음은 흔히 볼 수 있 는 해시 알고리즘 몇 가 지 를 소개 하고 분포 의 균일 성, 해시 충돌 확률 과 성능 등에 서 의 우열 을 알 아 보 겠 습 니 다.
MD5 알고리즘: 모두 Message - Digest Algorithm 5 라 고 부 르 며 정보 전송 이 완전 하 게 일치 하도록 합 니 다.컴퓨터 가 광범 위 하 게 사용 하 는 컴 퓨 팅 알고리즘 중 하나 로 주류 프로 그래 밍 언어 는 보편적으로 MD5 가 실현 되 었 다.MD5 의 역할 은 대 용량 정 보 를 비밀 형식 으로 압축 하 는 것 이다.일반적인 파일 의 완전 성 검 사 는 MD5 를 사용 하 는 것 입 니 다.
CRC 알고리즘: 전체 이름 은 CyclicRedundancy Check 이 고 중국어 이름 은 순환 중복 검사 입 니 다.이것 은 중요 한 것 으로 인 코딩 과 디 코딩 방법 이 간단 하고 오류 검사 와 오류 정정 능력 이 강 한 해시 알고리즘 으로 통신 분야 에서 오류 통 제 를 실현 하 는 데 널리 사용 된다.
MurmurHash 알고리즘: 높 은 연산 성능, 낮은 충돌 율, Austin Appleby 가 2008 년 에 만 들 었 고 현 재 는 Hadoop, libstdc +, nginx, libmemcached 등 오픈 소스 시스템 에 응용 되 었 습 니 다.자바 계 에 서 는 Redis, Memcached, Cassandra, HBase, Lucene, Guava 가 모두 사용 하고 있다.
FNV 알고리즘: 전체 이름 은 Fowler - Noll - vo 알고리즘 으로 세 명의 발명가 Glenn Fowler, Landon Curt Noll, Phong Vo 의 이름 으로 명명 되 었 으 며 이 르 면 1991 년 에 제기 되 었 습 니 다.FNV 는 대량의 데 이 터 를 빠르게 hash 하고 작은 충돌 율 을 유지 할 수 있 습 니 다. 고도 로 분산 되 어 hash 와 매우 비슷 한 문자열, 예 를 들 어 URL, hostname, 파일 이름, text 와 IP 주소 등 이 적 용 됩 니 다.
Ketama 알고리즘: 일치 성 해시 알고리즘 의 실현 중 하나 입 니 다. 다른 해시 알고리즘 은 통용 되 는 일치 성 해시 알고리즘 이 실현 되 었 습 니 다. 해시 맵 함 수 를 교체 한 것 에 불과 하지만 Ketama 는 전체 절차 입 니 다. 우 리 는 뒤에서 소개 할 것 입 니 다.
일치 성 해시 알고리즘
다음은 분포 식 캐 시 장면 을 예 로 들 어 일치 성 해시 알고리즘 링 의 원 리 를 분석 하 겠 습 니 다.
먼저 캐 시 서버 (ip + 포트 번호) 를 해시 하여 링 의 한 노드 로 매 핑 하여 캐 시 데이터 key 값 의 hash key 를 계산 하고 링 에 도 매 핑 하 며 가장 가 까 운 서버 노드 를 캐 시 에 저장 할 서버 로 선택 합 니 다.구체 적 으로 실현 하면 후속 적 인 장절 을 볼 수 있다.
예 를 들 어 A, B, C, D 네 개의 캐 시 서버 가 존재 할 때 키 값 이 1 인 캐 시 데이터 가 일치 성 해시 링 에 있 는 위 치 는 다음 그림 과 같 습 니 다. 최근 서버 노드 를 가 져 오 는 규칙 에 따라 이 캐 시 데 이 터 는 서버 B 에 저장 해 야 합 니 다.
키 값 이 4 인 캐 시 데 이 터 를 저장 하려 면 일치 성 해시 링 의 위 치 는 다음 과 같 기 때문에 서버 C 에 저장 해 야 합 니 다.
이와 유사 하 게 키 값 이 5, 6 인 데 이 터 는 서비스 D 에, 키 값 이 7, 8 인 데 이 터 는 서비스 A 에 저장 해 야 한다.
이때 서버 B 가 다운 되 어 서버 B 에 저 장 된 캐 시 데 이 터 를 이전 해 야 하지만 일치 성 해시 링 이 존재 하기 때문에 key 값 이 1 인 데이터 만 이전 하면 다른 데이터 의 저장 서버 는 변 하지 않 습 니 다.이것 도 일치 성 해시 알고리즘 이 나머지 맵 알고리즘 보다 뛰어난 곳 이다.
서버 B 오프라인 에서 키 값 이 1 인 데 이 터 는 시계 방향 으로 가장 가 까 운 서버 가 C 이기 때문에 데이터 저장 소 는 서버 C 로 이전 합 니 다.
현실 상황 에서 서버 가 일치 성 해시 링 에 있 는 위치 가 이렇게 고 르 게 분포 되 지 않 아 각 노드 가 실제 적 으로 링 을 차지 하 는 구간 의 크기 가 다르다.
이런 상황 에서 허 노드 를 늘 려 해결 할 수 있다.가상 노드 를 증가 시 켜 모든 노드 가 링 에 있 는 '관할' 구역 을 더욱 고 르 게 한다.이렇게 하면 노드 가 변화 할 때 데이터 분포 의 변화 에 최대한 작은 영향 을 주 는 동시에 데이터 분포 의 균일 도 확보 할 수 있다.
구체 적 실현
다음은 Memcached 분포 식 캐 시 장면 에서 의 일치 성 해시 알고리즘 을 실현 하고 구체 적 인 테스트 성능 데 이 터 를 제시 합 니 다.이 실현 은 kiritomoe 블 로그 의 실현 과 spymemcached 클 라 이언 트 코드 를 참고 했다.구체 적 인 실현 은 제 github 를 보 세 요. 주 소 는?https://github.com/ztelur/con...。
NodeLocator 분포 식 캐 시 장면 에서 일치 하 는 해시 알고리즘 의 추상 적 인 것 으로 getPrimary 함수 가 있 고 캐 시 데 이 터 를 받 는 key 값 으로 이 캐 시 데 이 터 를 저장 하 는 서버 인 스 턴 스 를 출력 합 니 다.public interface NodeLocator {
MemcachedNode getPrimary(String k);
}다음은 통용 되 는 일치 성 해시 알고리즘 의 실현 입 니 다.
TreeMap 을 일치 성 해시 링 의 데이터 구조 로 사용 합 니 다. ceilingEntry 함 수 는 링 의 가장 가 까 운 노드 를 얻 을 수 있 습 니 다.buildConsistentHashRing 함수 에는 일치 성 해시 링 을 구축 하 는 과정 이 포함 되 어 있 고 기본적으로 12 개의 가상 노드 가 추가 되 었 습 니 다.public class ConsistentHashNodeLocator implements NodeLocator {
private final static int VIRTUAL_NODE_SIZE = 12;
private final static String VIRTUAL_NODE_SUFFIX = "-";
private volatile TreeMap hashRing;
private final HashAlgorithm hashAlg;
public ConsistentHashNodeLocator(List nodes, HashAlgorithm hashAlg) {
this.hashAlg = hashAlg;
this.hashRing = buildConsistentHashRing(hashAlg, nodes);
}
@Override
public MemcachedNode getPrimary(String k) {
long hash = hashAlg.hash(k);
return getNodeForKey(hashRing, hash);
}
private MemcachedNode getNodeForKey(TreeMap hashRing, long hash) {
/* key */
Map.Entry locatedNode = hashRing.ceilingEntry(hash);
/* ， */
if (locatedNode == null) {
locatedNode = hashRing.firstEntry();
}
return locatedNode.getValue();
}
private TreeMap buildConsistentHashRing(HashAlgorithm hashAlgorithm, List nodes) {
TreeMap virtualNodeRing = new TreeMap<>();
for (MemcachedNode node : nodes) {
for (int i = 0; i < VIRTUAL_NODE_SIZE; i++) {
// ，
virtualNodeRing.put(hashAlgorithm.hash(node.getSocketAddress().toString() + VIRTUAL_NODE_SUFFIX + i), node);
}
}
return virtualNodeRing;
}
} getPrimary 함수 에서 먼저 HashAlgorithm 키 값 에 대응 하 는 해시 값 을 계산 한 다음 getNodeForKey 함수 로 TreeMap 에 대응 하 는 최근 서버 노드 인 스 턴 스 를 가 져 옵 니 다.HashAlgorithm 은 해시 알고리즘 에 대한 추상 적 이 고 일치 성 해시 알고리즘 은 CRC, MurmurHash 와 FNV 등 여러 가지 일반적인 해시 알고리즘 을 사용 할 수 있다.다음은 각종 해시 알고리즘 이 이 실현 에 가 져 온 성능 차이 점 을 비교 해 보 겠 습 니 다.성능 테스트
테스트 데 이 터 는 알고리즘 의 좋 고 나 쁨 을 평가 하 는 가장 진실 하고 효과 적 인 방법 으로 양 적 사고방식 은 반드시 있어 야 한다. 이것 도 프로그래머 가 진급 하 는 보물 중의 하나 이다.우 리 는 서로 다른 해시 함 수 를 바탕 으로 하 는 일치 성 해시 알고리즘 을 다음 네 가지 계량 화 된 기준 으로 평가 합 니 다.
구체 적 인 평가 알고리즘 은 다음 과 같다.
public class NodeLocatorTest {
/**
*
*/
@Test
public void testDistribution() {
List servers = new ArrayList<>();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
// DefaultHashAlgorithm ，
NodeLocator nodeLocator = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.NATIVE_HASH);
// 50000
List keys = new ArrayList<>();
for (int i = 0; i < 50000; i++) {
keys.add(UUID.randomUUID().toString());
}
//
AtomicLongMap atomicLongMap = AtomicLongMap.create();
for (MemcachedNode server : servers) {
atomicLongMap.put(server, 0);
}
for (String key : keys) {
MemcachedNode node = nodeLocator.getPrimary(key);
atomicLongMap.getAndIncrement(node);
}
System.out.println(StatisticsUtil.variance(atomicLongMap.asMap().values().toArray(new Long[]{})));
System.out.println(StatisticsUtil.standardDeviation(atomicLongMap.asMap().values().toArray(new Long[]{})));
}
/**
*
*/
@Test
public void testNodeAddAndRemove() {
List servers = new ArrayList<>();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
// 10 , shuffle， 0 90， 。
Collections.shuffle(servers);
List serverChanged = servers.subList(0, 90);
NodeLocator loadBalance = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.NATIVE_HASH);
NodeLocator changedLoadBalance = new ConsistentHashNodeLocator(serverChanged, DefaultHashAlgorithm.NATIVE_HASH);
// 50000
List keys = new ArrayList<>();
for (int i = 0; i < 50000; i++) {
keys.add(UUID.randomUUID().toString());
}
int count = 0;
for (String invocation : keys) {
MemcachedNode origin = loadBalance.getPrimary(invocation);
MemcachedNode changed = changedLoadBalance.getPrimary(invocation);
//
if (!origin.getSocketAddress().equals(changed.getSocketAddress())) count++;
}
System.out.println(count / 50000D);
}
static String[] ips = {...};
} JMH 의 테스트 스 크 립 트 는 다음 과 같다.
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Thread)
public class JMHBenchmark {
private NodeLocator nodeLocator;
private List keys;
@Benchmark
public void test() {
for (String key : keys) {
MemcachedNode node = nodeLocator.getPrimary(key);
}
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(JMHBenchmark.class.getSimpleName())
.forks(1)
.warmupIterations(5)
.measurementIterations(5)
.build();
new Runner(opt).run();
}
@Setup
public void prepare() {
List servers = new ArrayList<>();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
nodeLocator = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.MURMUR_HASH);
// 50000
keys = new ArrayList<>();
for (int i = 0; i < 50000; i++) {
keys.add(UUID.randomUUID().toString());
}
}
@TearDown
public void shutdown() {
}
static String[] ips = {...};
}
각각 JDK 해시 알고리즘, FNV 132 알고리즘, CRC 알고리즘, MurmurHash 알고리즘 과 Ketama 알고리즘 을 테스트 하여 각각
DefaultHashAlgorithm 의 NATIVE_HASH, FNV1_32_HASH, CRC_HASH, MURMUR_HASH 과 KETAMA_HASH 에 대응 했다.구체 적 인 데 이 터 는 다음 과 같다.가상 슬롯 파 티 션
레 디 스 클 러 스 터 는 일치 성 해시 알고리즘 을 사용 하지 않 고 가상 슬롯 파 티 션 알고리즘 을 사용 했다 는 글 도 있다.그러나 외부 네트워크 (주 소 는 문 말 참조) 에 서 는 Redis 가 사용 하 는 가상 슬롯 구역 은 일치 성 해시 알고리즘 의 변종 일 뿐 가상 슬롯 은 Redis 동적 확장 을 허용 할 수 있다 고 말 했다.
레 디 스 의 소스 코드 를 알 아 봐 야 이 문제 에 대해 정확 한 대답 을 할 수 있 을 지도 모른다.알 고 계 신 분 들 은 적극적으로 댓 글로 답 해 주세요. 감사합니다.
github 주소:https://github.com/ztelur/con...redis분산 토론 의 주소:https://www.reddit.com/r/redi...
레 퍼 런 스
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
해시란 무엇입니까?해시 함수는 단순히 임의 길이의 입력 X를 고정 길이 n의 출력 h(x)에 매핑하는 함수입니다. ” The input to a hash function is called a pre-image, the message,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
