পাঠ্যক্রম খুলুন

মধ্যবর্তী পর্যায়

Consistent Hashing: server বদলালে কম key সরানো

Consistent Hashing

এই পাঠের কুইজ ↓৫ মিনিট পড়াPHP 8.3+ · Laravel 12

আগে পড়ে নিনPartitioning ও Sharding: ডেটা ভাগ করার নকশা ↗

এই পাঠের সূচিপত্র

এই পাঠে যা শিখবেন

Modulo remapping সমস্যা
Hash ring, virtual nodes ও rendezvous hashing
Placement বনাম data migration

সমস্যা দিয়ে শুরু

Cache server তিনটি থেকে চারটি হলো। hash(key) % nodeCount routing বদলানোয় অনেক key অন্য server-এ গেল, যদিও শুধু একটি node যোগ হয়েছে। Cache miss wave database-এ surge আনল। Consistent placement techniques membership change-এর সময় remapping সীমিত করতে সাহায্য করে। তবে key কোথায় যাবে জানা আর existing data সরানো এক কাজ নয়।

সহজ করে বুঝি

Consistent hash ring-এ node ও key hash space-এ point পায়; key পরের owner node-এ যায়। Virtual nodes একটি physical node-কে বহু point দেয়, balance উন্নত করতে পারে। Rendezvous বা highest-random-weight hashing প্রতিটি key-node pair-এর deterministic score করে highest score-কে owner বেছে নেয়। Node add/remove-এ প্রধানত ownership সংশ্লিষ্ট subset বদলায়। Traffic cost uneven হলে uniform key count হলেও workload balanced নাও হয়।

পরিচিত একটি উপমা

একটি circular পাড়ায় parcel nearest next collection desk-এ যায়। একটি নতুন desk খুললে কেবল তার আগের অঞ্চলের parcel assignment বদলায়। তবে পুরোনো desk-এর parcel নতুন desk-এ physically পাঠাতে হবে; map বদলালেই parcel নড়ে না।

নকশাটি দেখুন

Diagram লোড হচ্ছে…

সব caller একই key encoding, node IDs ও membership version ব্যবহার করে।

Diagram-এর text flow দেখুন

flowchart TD
 K[Stable resource key] --> H[Deterministic placement function]
 M[Same membership map on all clients] --> H
 H --> N1[Node A owner]
 H --> N2[Node B owner]
 H --> N3[Node C owner]
 N2 --> R[Migration or cache refill on change]

সব caller একই key encoding, node IDs ও membership version ব্যবহার করে। Function owner বেছে নেয়। Membership disagreement হলে একই key দুই node-এ route হতে পারে। Cache-এ duplicate refill সহ্য হতে পারে, authoritative database-এ split ownership বিপজ্জনক। Diagram-এর refill/migration step placement-এর বাইরের operational কাজ।

PHP ও Laravel-এ প্রয়োগ

নিচের pure PHP function simplified rendezvous hashing demo, ring algorithm নয়। Stable node IDs ও normalized string key দিন। সমান দৈর্ঘ্যের SHA-256 hex digest lexicographic order-এ তুলনা করে deterministic ranking করা হয়েছে; weighted routing ও production migration এখানে নেই।

function chooseNode(string $key, array $nodes): string
{
    if ($nodes === []) {
        throw new \InvalidArgumentException('At least one node is required.');
    }
    $winner = null;
    $best = null;
    foreach ($nodes as $node) {
        $score = hash('sha256', $key."\0".$node);
        if ($best === null || strcmp($score, $best) > 0) {
            $best = $score;
            $winner = $node;
        }
    }
    return $winner;
}

$owner = chooseNode('product:42', ['cache-a', 'cache-b', 'cache-c']);

সুবিধা, সীমাবদ্ধতা ও trade-off

Consistent placement membership changes-এ remapping কমাতে পারে এবং cache locality দেয়। Virtual nodes metadata ও tuning বাড়ায়। Rendezvous simple implementation-এ প্রতি lookup node count অনুযায়ী hashing cost দেয়। Hashing data size, request frequency বা hot key cost জানে না। One hot key এক owner-এই থাকতে পারে; replication/local cache বা domain partition strategy আলাদা concern।

সাধারণ ভুল

Hash owner বদলালেই data automatically moved ভাবা।
Node ID হিসেবে changing IP/boot ID ব্যবহার।
Uncoordinated membership list দিয়ে durable write route করা।

আরও একটু গভীরে

Placement version migration-এ old/new owner dual-read strategy থাকতে পারে, কিন্তু concurrent write consistency design করতে হবে। Redis Cluster নিজস্ব slot mapping ব্যবহার করে; এখানে লেখা function দিয়ে Laravel Redis Cluster client routing override করবেন না। Rebalancing throttle source ও destination load সীমিত রাখে। Distribution test-এ key count, byte volume এবং request frequency তিনটি আলাদা metric দেখুন।

মনে রাখুন

Consistent hashing remapping কমানোর placement family। Actual migration, replication ও ownership protocol আলাদা। Stable IDs ও shared membership contract ছাড়া deterministic functionও ভুল route দিতে পারে।

নিজে চেষ্টা করুন

এক হাজার synthetic key তিন node-এ assign করুন। চতুর্থ node যোগ করে কত assignment বদলায় তা গণনা করুন এবং modulo routing-এর সঙ্গে তুলনা করুন। এই ফল synthetic experiment, production balance guarantee নয়—assumption লিখুন।

নিজের বোঝা যাচাই করুন

1. Modulo কেন বেশি বদলায়?

Divisor বদলালে বহু key-এর remainder বদলে যায়। নতুন node-এর অংশ ছাড়াও অন্য assignment remap হতে পারে।

2. Virtual node কেন?

এক physical node-এর বহু positions finer-grained distribution দেয়। Uniform key count হলেও hot key load আলাদা সমস্যা।

3. Rendezvous ring?

না। Related placement goal-এর অন্য algorithm; key-node score-এর সর্বোচ্চ node বেছে নেয়। Example সেটিই দেখায়।

4. ডেটা নিজে move হয়?

না। Placement function শুধু destination বলে। Copy, catch-up, cutover ও verification আলাদা process।

5. Redis Cluster-এ function লাগাব?

না। Supported cluster-aware client ও slot protocol ব্যবহার করুন। Homemade mapping product routing contract ভাঙতে পারে।

এই পাঠের কুইজ

এই পাঠ থেকে ২টি প্রশ্ন। উত্তর দিয়ে ব্যাখ্যা দেখুন; অধ্যায়ের কুইজ আলাদাভাবে দিতে হবে।

এই পাঠের ২টি প্রশ্নের উত্তর দিন। পাস করতে দুটিই সঠিক হতে হবে।

জমা দেওয়ার পর সঠিক উত্তর ও ব্যাখ্যা দেখবেন। ফলাফল এই ব্রাউজারে সংরক্ষিত থাকবে। অনুশীলনের ফল অধ্যায় সম্পন্নের হিসাবে যোগ হয় না।

সব বিষয় মিলিয়ে অনুশীলন করুন →

অগ্রগতি এই ব্রাউজারে সংরক্ষিত থাকে। শুধু পাঠ খুললে সম্পন্ন হয় না।