Load Balancing Algorithms और Consistent Hashing

Server कैसे चुनें

Round robin servers में बारी-बारी घूमता है: सरल, पर अनुरोधों की लागत अलग हो तो अनुचित। Weighted रूप बड़े servers को ज़्यादा traffic देते हैं। Least connections / least load सबसे कम काम करने वाला server चुनता है, जो असमान अनुरोध अवधियों को बेहतर सँभालता है। दो विकल्पों के साथ random (दो random चुनें, कम भार वाला उपयोग करें) सस्ते में ज़्यादातर लाभ पाता है और अच्छी तरह scale होता है। Consistent hashing key (user ID, session, cache key) को servers की ring पर map करता है ताकि वही key उसी server पर पहुँचती रहे (caches और stateful backends के लिए उपयोगी), और server जोड़ने या हटाने पर keys का सिर्फ़ छोटा हिस्सा हिलता है, सादे hash % N के विपरीत जो लगभग सब कुछ फिर बाँट देता है। मरे servers को pool से हटाने के लिए किसी भी algorithm को health checks के साथ जोड़ें।

Round robin बनाम least load, चलाकर

मैंने यह सादा-Python मॉडल चलाया। आठ अनुरोध जिनमें पहले को 10 इकाई और बाक़ी को 1-1 लगती है: round robin server a को 13 इकाई काम और b को 4 देता है, जबकि least-load 10 और 7 देता है, कहीं ज़्यादा निष्पक्ष बँटवारा।

import hashlib, bisect, math, random

def round_robin(n_req, servers): return [servers[i % len(servers)] for i in range(n_req)]
def least_conn(durations, servers):
    busy = {s: 0 for s in servers}; picks = []
    for d in durations:
        s = min(servers, key=lambda x: busy[x]); picks.append(s); busy[s] += d
    return picks, busy
dur = [10, 1, 1, 1, 1, 1, 1, 1]
rr = round_robin(8, ["a", "b"]); rr_load = {s: sum(d for d, p in zip(dur, rr) if p == s) for s in "ab"}
lc, lc_load = least_conn(dur, ["a", "b"])
print("round robin load", rr_load, "| least-load load", lc_load)

Output:

round robin load {'a': 13, 'b': 4} | least-load load {'a': 10, 'b': 7}

Consistent hashing बनाम modulo, चलाकर

मैंने यह सादा-Python मॉडल चलाया। 1,000 keys के साथ 3 से 4 servers पर जाने पर: consistent hashing 257 keys हिलाता है (आदर्श 25% के क़रीब), जबकि hash % N 770 हिलाता है। Cache के लिए यह छोटी गिरावट और database पर भगदड़ का अंतर है।

import hashlib, bisect, math, random

def h(s): return int(hashlib.md5(s.encode()).hexdigest(), 16)
def ring(nodes, vnodes=100): 
    pts = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes)); return [p for p, _ in pts], [n for _, n in pts]
def lookup(r, key):
    keys, owners = r; i = bisect.bisect(keys, h(key)) % len(keys); return owners[i]
keys = [f"user-{i}" for i in range(1000)]
r3 = ring(["n1", "n2", "n3"]); r4 = ring(["n1", "n2", "n3", "n4"])
moved = sum(1 for k in keys if lookup(r3, k) != lookup(r4, k))
naive = sum(1 for k in keys if h(k) % 3 != h(k) % 4)
print("consistent moved", moved, "of 1000 | modulo moved", naive, "of 1000")

Output:

consistent moved 257 of 1000 | modulo moved 770 of 1000

त्वरित जाँच: Cache cluster के लिए consistent hashing क्यों?

• Node जोड़ने या हटाने पर keys का सिर्फ़ छोटा हिस्सा हिलता है
• यह हर key को अनोखा बनाता है
• यह hashing की ज़रूरत हटाता है
• यह keys को encrypt करता है