출시·고도화 중
일관된 해시 안내서 · 6/6
일관된 해시는 1997년 MIT의 Karger 등이 웹 캐시 분산을 위해 발표한 논문에서 시작되었고, 이 연구는 콘텐츠 전송 네트워크(CDN) Akamai의 기반 기술로 이어졌습니다. 지금은 분산 캐시, 키-값 저장소, 로드 밸런서에서 흔히 볼 수 있습니다. 다만 "샤딩을 한다"고 모두 일관된 해시를 쓰는 것은 아니므로 시스템마다 실제 방식을 확인해야 합니다.
Memcached 서버들은 서로를 알지 못하고, 어떤 키를 어느 서버에 둘지는 클라이언트가 정합니다. 2007년 last.fm이 공개한 ketama는 서버마다 링 위에 여러 점을 두는 방식으로, libmemcached를 비롯한 여러 클라이언트와 프록시(twemproxy 등)가 ketama 호환 분산을 지원합니다. 캐시 서버 한 대를 늘려도 대부분의 키가 같은 서버로 가므로 적중률이 크게 떨어지지 않습니다.
Redis Cluster는 일관된 해시 링을 쓰지 않습니다. 키를 CRC16(key) mod 16384로 16,384개 해시 슬롯 중 하나에 넣고, 슬롯을 노드에 명시적으로 배정합니다. 노드를 추가하면 운영자가 일부 슬롯을 옮기므로 이동량은 비슷하게 적지만 원리는 다릅니다.
2007년 Amazon의 Dynamo 논문은 일관된 해시 링, 가상 노드, 시계 방향으로 이어지는 N개 노드에 복제하는 선호 목록(preference list)을 함께 소개해 큰 영향을 주었습니다. 논문은 또 링을 같은 크기의 고정 파티션으로 나눠 노드에 배정하는 전략이 균형과 운영 면에서 더 낫다고 보고합니다. 참고로 AWS의 DynamoDB 서비스는 이 논문에서 영향을 받았지만 내부 구조는 다른 별개의 시스템입니다.
num_tokens)을 갖고, 기본 파티셔너는 Murmur3 해시를 씁니다. 복제 전략은 링을 따라 다음 노드를 고르되, NetworkTopologyStrategy는 데이터센터와 랙을 고려합니다.같은 사용자나 같은 URL을 계속 같은 백엔드로 보내면 캐시와 세션을 재사용할 수 있습니다. Nginx는 hash 지시어에 consistent를 붙이면 ketama 방식의 일관된 해시를 씁니다.
upstream cache_backend {
hash $request_uri consistent;
server 10.0.0.11:8080;
server 10.0.0.12:8080;
server 10.0.0.13:8080;
}HAProxy는 hash-type consistent로 같은 일을 하며, hash-balance-factor를 주면 한 서버의 부하가 평균의 일정 배수를 넘지 않게 제한하는 bounded-load 일관된 해시를 씁니다. 150은 평균의 1.5배를 뜻합니다.
backend cache_servers
balance uri
hash-type consistent
hash-balance-factor 150
server c1 10.0.0.11:8080 check
server c2 10.0.0.12:8080 checkEnvoy는 RING_HASH와 MAGLEV 부하 분산 정책을 제공합니다. Maglev는 2016년 Google이 발표한 소프트웨어 로드 밸런서의 방식으로, 링 대신 고정 크기 조회표를 채워 O(1)로 조회합니다.
핫 키가 몰리면 한 노드가 과부하됩니다. Mirrokni 등이 제안한 bounded loads 방식은 각 노드의 용량을 평균의 c배로 정하고, 주인이 꽉 찼으면 시계 방향 다음 노드로 넘깁니다. 아래는 구현 장의 HashRing을 쓴 간단한 형태입니다.
import bisect, math
def get_bounded(ring, key, load, total, c=1.25):
nodes = set(ring.owner.values())
cap = math.ceil(c * (total + 1) / len(nodes)) # per-node capacity
pts = ring.points
start = bisect.bisect_left(pts, hash64(key))
for step in range(len(pts)):
node = ring.owner[pts[(start + step) % len(pts)]]
if load.get(node, 0) < cap:
load[node] = load.get(node, 0) + 1
return node
raise RuntimeError("no capacity")hash()처럼 실행마다 바뀌는 해시를 쓰면 재시작할 때마다 모든 키가 옮겨 갑니다.node#i)을 바꾸면 사실상 링 전체를 새로 만드는 셈입니다.def read(key, new_ring, old_ring, stores):
value = stores[new_ring.get(key)].get(key)
if value is None: # not migrated yet
value = stores[old_ring.get(key)].get(key)
return value
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.
첫 댓글을 남겨 보세요.