구현

가상 노드를 갖춘 해시 링을 Python bisect로 만들고 C++·Java·TypeScript로 옮깁니다. 네 언어의 해시가 같아서 같은 키는 어디서나 같은 노드로 갑니다.

Python

Python 내장 hash()는 문자열 해시가 실행마다 바뀌므로(PYTHONHASHSEED) 쓰면 안 됩니다. 여기서는 64비트 FNV-1a 뒤에 MurmurHash3의 마무리 단계 fmix64를 붙여 node#1, node#2처럼 비슷한 이름도 고르게 퍼지게 했습니다.

import bisect

MASK = (1 << 64) - 1


def hash64(text: str) -> int:
    x = 0xCBF29CE484222325  # FNV-1a offset basis
    for b in text.encode("utf-8"):
        x = ((x ^ b) * 0x100000001B3) & MASK
    x ^= x >> 33  # fmix64 finalizer
    x = (x * 0xFF51AFD7ED558CCD) & MASK
    x ^= x >> 33
    x = (x * 0xC4CEB9FE1A85EC53) & MASK
    return x ^ (x >> 33)


class HashRing:
    def __init__(self, vnodes: int = 100):
        self.vnodes = vnodes
        self.points: list[int] = []  # sorted positions
        self.owner: dict[int, str] = {}  # position -> node

    def add(self, node: str) -> None:
        for i in range(self.vnodes):
            p = hash64(f"{node}#{i}")
            bisect.insort(self.points, p)
            self.owner[p] = node

    def remove(self, node: str) -> None:
        for i in range(self.vnodes):
            p = hash64(f"{node}#{i}")
            del self.owner[p]
            self.points.pop(bisect.bisect_left(self.points, p))

    def get(self, key: str) -> str:
        if not self.points:
            raise LookupError("ring is empty")
        i = bisect.bisect_left(self.points, hash64(key))
        if i == len(self.points):  # wrap around
            i = 0
        return self.owner[self.points[i]]

• hash64: 바이트마다 XOR하고 FNV 소수를 곱한 뒤 & MASK로 64비트만 남깁니다. C++·Java의 정수 넘침과 같은 효과입니다.
• points, owner: 정렬된 위치 목록과 위치에서 노드로 가는 사전입니다.
• add: 이름 뒤에 #0, #1...을 붙여 가상 노드 위치를 만들고 insort로 정렬을 지키며 넣습니다.
• remove: 같은 이름으로 위치를 다시 계산하므로 노드별 점 목록을 따로 저장하지 않아도 됩니다.
• get: bisect_left가 키 위치 이상인 첫 점을 찾고, 끝을 넘으면 0번으로 감쌉니다.

64비트 위치 충돌은 점이 백만 개여도 수천만분의 1 수준이라 생략했습니다.

C++

std::map은 정렬된 트리라서 lower_bound가 곧 시계 방향 탐색입니다.

#include <cstdint>
#include <map>
#include <stdexcept>
#include <string>

std::uint64_t hash64(const std::string& text) {
    std::uint64_t x = 0xCBF29CE484222325ULL;
    for (unsigned char b : text) x = (x ^ b) * 0x100000001B3ULL;
    x ^= x >> 33; x *= 0xFF51AFD7ED558CCDULL;
    x ^= x >> 33; x *= 0xC4CEB9FE1A85EC53ULL;
    return x ^ (x >> 33);
}

class HashRing {
public:
    explicit HashRing(int vnodes = 100) : vnodes_(vnodes) {}
    void add(const std::string& node) {
        for (int i = 0; i < vnodes_; ++i) ring_[hash64(node + "#" + std::to_string(i))] = node;
    }
    void remove(const std::string& node) {
        for (int i = 0; i < vnodes_; ++i) ring_.erase(hash64(node + "#" + std::to_string(i)));
    }
    const std::string& get(const std::string& key) const {
        if (ring_.empty()) throw std::runtime_error("ring is empty");
        auto it = ring_.lower_bound(hash64(key));
        return (it == ring_.end() ? ring_.begin() : it)->second;
    }
private:
    int vnodes_;
    std::map<std::uint64_t, std::string> ring_;
};

Java

부호 없는 long이 없으므로 TreeMap에 Long::compareUnsigned 비교기를 주고, ceilingEntry로 이상인 첫 항목을 찾습니다.

import java.nio.charset.StandardCharsets;
import java.util.Map;
import java.util.TreeMap;

public class HashRing {
    private final int vnodes;
    private final TreeMap<Long, String> ring = new TreeMap<>(Long::compareUnsigned);

    public HashRing(int vnodes) { this.vnodes = vnodes; }

    static long hash64(String text) {
        long x = 0xCBF29CE484222325L;
        for (byte b : text.getBytes(StandardCharsets.UTF_8)) x = (x ^ (b & 0xFF)) * 0x100000001B3L;
        x ^= x >>> 33; x *= 0xFF51AFD7ED558CCDL;
        x ^= x >>> 33; x *= 0xC4CEB9FE1A85EC53L;
        return x ^ (x >>> 33);
    }

    public void add(String node) {
        for (int i = 0; i < vnodes; i++) ring.put(hash64(node + "#" + i), node);
    }

    public void remove(String node) {
        for (int i = 0; i < vnodes; i++) ring.remove(hash64(node + "#" + i));
    }

    public String get(String key) {
        if (ring.isEmpty()) throw new IllegalStateException("ring is empty");
        Map.Entry<Long, String> e = ring.ceilingEntry(hash64(key));
        return (e != null ? e : ring.firstEntry()).getValue();
    }
}

TypeScript

64비트 곱셈에 bigint를 쓰고 이진 탐색은 직접 씁니다.

const MASK = (1n << 64n) - 1n;

function hash64(text: string): bigint {
  let x = 0xcbf29ce484222325n;
  for (const b of new TextEncoder().encode(text)) x = ((x ^ BigInt(b)) * 0x100000001b3n) & MASK;
  x ^= x >> 33n; x = (x * 0xff51afd7ed558ccdn) & MASK;
  x ^= x >> 33n; x = (x * 0xc4ceb9fe1a85ec53n) & MASK;
  return x ^ (x >> 33n);
}

class HashRing {
  private points: bigint[] = [];
  private owner = new Map<bigint, string>();
  constructor(private readonly vnodes = 100) {}

  private lowerBound(h: bigint): number {
    let lo = 0, hi = this.points.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.points[mid] < h) lo = mid + 1; else hi = mid;
    }
    return lo;
  }
  add(node: string): void {
    for (let i = 0; i < this.vnodes; i++) {
      const p = hash64(`${node}#${i}`);
      this.points.splice(this.lowerBound(p), 0, p);
      this.owner.set(p, node);
    }
  }
  remove(node: string): void {
    for (let i = 0; i < this.vnodes; i++) {
      const p = hash64(`${node}#${i}`);
      if (this.owner.delete(p)) this.points.splice(this.lowerBound(p), 1);
    }
  }
  get(key: string): string {
    if (this.points.length === 0) throw new Error("ring is empty");
    const i = this.lowerBound(hash64(key));
    return this.owner.get(this.points[i === this.points.length ? 0 : i])!;
  }
}

정리

• 링은 정렬된 위치와 위치별 주인, 두 자료로 충분합니다.
• 조회는 이상인 첫 위치를 찾고 끝이면 처음으로 감싸는 것입니다.
• 해시는 실행과 언어가 달라도 같은 값을 내야 합니다.
• 정렬 트리(map, TreeMap)를 쓰면 점 추가·삭제가 O(log n)입니다.