Consistent Hashing

နားလည်ထားရမယ့် အချက်

Server N ခုကို sharding လုပ်ဖို့ naive method ကတော့ `hash(key) % N` ဖြစ်ပြီး key တွေကို ညီညာစွာ ဖြန့်ပေးပါတယ် — ဒါပေမဲ့ N ပြောင်းလိုက်တဲ့ချိန် (scale လုပ်ဖို့ server ထပ်ထည့်လိုက်တာ ဒါမှမဟုတ် ဖြုတ်လိုက်တာ) modulus ပြောင်းသွားလို့ key နီးပါးအားလုံးရဲ့ mapping က server မတူတော့ပါဘူး။ Cache ဒါမှမဟုတ် sharded database မှာ ဒါက disruptive reshuffle ကြီးတစ်ခု ဖြစ်စေပါတယ် — data နီးပါးအားလုံးကို ရွှေ့ရမှာဖြစ်ပြီး cache တွေကလည်း တစ်ချိန်တည်း သိပ်ဗလာဖြစ်သွားနိုင်ပါတယ်။ Consistent hashing ကတော့ server နဲ့ key နှစ်ခုစလုံးကို numeric space ဝိုင်း (ring) တစ်ခုတည်းပေါ်မှာ hash လုပ်ကာ key တစ်ခုစီကို ၎င်းရဲ့ position ကနေ clockwise ဦးဆုံးတွေ့တဲ့ server ဆီ assign လုပ်ပေးပါတယ်။ Server အသစ်ထည့်လိုက်ရင် ၎င်းနဲ့ clockwise neighbor ကြားက key တွေကိုပဲ ယူသွားပါတယ် — ကျန်တဲ့ assignment တွေက မထိပါဘူး — ဒါကြောင့် key နီးပါးအားလုံးအစား ပျမ်းမျှအားဖြင့် key ၁/N ပဲ ရွှေ့ရပါတယ်။ ဒါကြောင့် DynamoDB၊ Cassandra နဲ့ CDN/load balancer အများစုက ဒါကို သုံးကြတာပါ — horizontal scaling ကို တစ်ခါတည်း migration ကြီးအစား incremental disruption နည်းတဲ့ operation ဖြစ်စေပါတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ cache layer (render လုပ်ထားတဲ့ lesson page, popular quiz result) ကြီးထွားလာတဲ့အခါ cache entry တွေကို cache server အများစုအတွင်း ဖြန့်ကျက်ပါတယ်။ Naive hash % N သုံးရင် traffic spike ဖြစ်တဲ့အချိန် cache server တစ်ခု ထပ်ထည့်လိုက်ရင် cache လုပ်ထားတဲ့ lesson နီးပါးအားလုံးက server မတူတော့ဘဲ site က cache အလိုအရှိဆုံးအချိန်မှာပဲ cache-miss storm ဖြစ်စေပါတယ်။ Consistent hashing ကို ပြောင်းလိုက်ရင်တော့ peak load အချိန် cache server ထပ်ထည့်လိုက်တာက key အနည်းငယ်ကိုပဲ ပြန်assign လုပ်ရပြီး ကျန်တဲ့ cache တွေက warm ဆက်နေနိုင်ပါတယ် — platform ဟာ ကိုယ့်ဘာသာ downtime ဖန်တီးမနေဘဲ cache tier ကို scale လုပ်နိုင်ပါတယ်။

• Naive hash % N က server အရေအတွက် N ပြောင်းတိုင်း key နီးပါးအားလုံးကို ပြန်assign လုပ်ရပါတယ်။
• Consistent hashing က server နှင့် key နှစ်ခုစလုံးကို ring တစ်ခုပေါ် hash လုပ်ပြီး key ကို clockwise ဦးဆုံးတွေ့တဲ့ server ဆီ assign ပါတယ်။
• Server အသစ်ထပ်ထည့်ရင် key ၁/N ခန့်ကိုသာ ပြန်assign ရပြီး ကျန် mapping တွေက မထိတာက disruption ကို အလွန်လျှော့ချပေးပါတယ်။

အတူတူ စမ်းရေးကြည့်မယ်

import bisect
import hashlib

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % (2**32)

class ConsistentHashRing:
    def __init__(self, servers):
        self.ring = []  # sorted list of (hash, server) pairs
        for s in servers:
            self.add_server(s)

    def add_server(self, server):
        point = h(server)
        bisect.insort(self.ring, (point, server))

    def get_server(self, key):
        point = h(key)
        hashes = [p for p, _ in self.ring]
        idx = bisect.bisect(hashes, point) % len(self.ring)
        return self.ring[idx][1]

# Demo: how many keys move when we add a server
keys = [f"lesson-{i}" for i in range(1000)]

ring = ConsistentHashRing(["cache-A", "cache-B", "cache-C"])
before = {k: ring.get_server(k) for k in keys}

ring.add_server("cache-D")
after = {k: ring.get_server(k) for k in keys}

moved = sum(1 for k in keys if before[k] != after[k])
print(f"{moved} of {len(keys)} keys moved ({moved/len(keys):.1%})")

Server 3 ခုမှ 4 ခုသို့ ထပ်ထည့်လိုက်တဲ့အခါ key 1000 ထဲက 310 ခု (31.0%) ရွှေ့ရကြောင်း ပရင့်ထုတ်ပါတယ် — 1/N = 25% ခန့်နှင့် အနီးစပ်ဆုံး ဖြစ်ပြီး naive hash % N ဆီက ကျန်ရစ်ခဲ့မယ့် key နီးပါးအားလုံး ရွှေ့ရမယ့် အခြေအနေနှင့် စာရင် များစွာနည်းပါးပါတယ် (server တစ်ခုစီ ring ပေါ်မှာ point တစ်ခုတည်းသာ ရှိနေတာကြောင့် 25% နှင့် အတိအကျ မကိုက်ညီခြင်းဖြစ်ပြီး ဒီ lesson ရဲ့ ပထမ pitfall မှာ ရှင်းပြထားပါတယ်)။

Wikipedia — Consistent hashing — System Design