Building Blocks১০ মিনিট পাঠ

ক্যাপ থিওরেম (CAP Theorem)

আপনি সব কিছু একসাথে পাবেন না — তিনটির মধ্যে যেকোনো দুটি বেছে নিন
scope:বিল্ডিং ব্লকdifficulty:মাঝারি

অসম্ভব ত্রিভুজ (The Impossible Triangle)

কল্পনা করুন আপনি সারা দেশে মিষ্টির দোকানের একটি চেইন চালাচ্ছেন। আপনি তিনটি জিনিস চান:

  1. প্রতিটি শপে সব সময় একেবারে একই মেনু থাকবে (Consistency বা ধারাবাহিকতা)
  2. প্রতিটি শপ সব সময় খোলা থাকবে, যাই হোক না কেন (Availability বা লভ্যতা)
  3. শপগুলোর মধ্যে যোগাযোগের লাইন বিচ্ছিন্ন হয়ে গেলেও শপগুলো কাজ করতে থাকবে (Partition Tolerance বা বিভাজন সহনশীলতা)

CAP থিওরেম বলে: আপনি একই সময়ে এই তিনটির মধ্যে শুধুমাত্র দুটির গ্যারান্টি দিতে পারেন।

এটি ২০০০ সালে এরিক ব্রুয়ার (Eric Brewer) দ্বারা প্রথম উপস্থাপিত হয় এবং ২০০২ সালে গিলবার্ট ও লিঞ্চ (Gilbert and Lynch) দ্বারা আনুষ্ঠানিকভাবে প্রমাণিত হয়। ডিস্ট্রিবিউটেড সিস্টেমের ক্ষেত্রে এটি অন্যতম গুরুত্বপূর্ণ একটি থিওরেম, এবং প্রায় প্রতিটি সিস্টেম ডিজাইন ইন্টারভিউতেই এটি আলোচিত হয়।

▸ তিনটি CAP প্রপার্টি

C, A, এবং P — এর ব্যাখ্যা

Consistency (C) বা ধারাবাহিকতা — প্রতিটি রিড (read) রিকোয়েস্ট সর্বসাম্প্রতিক রাইট (write) করা ডেটা পাবে। যদি Anika সার্ভার ১-এ তার প্রোফাইল ছবি আপডেট করে এবং ১ মিলিসেকেন্ড পর Rafi সার্ভার ২ থেকে রিড করে, তবে Rafi নতুন ছবিটাই দেখতে পাবে। সবাই একই সময়ে একই ডেটা দেখতে পায়।

Availability (A) বা লভ্যতা — প্রতিটি রিকোয়েস্ট একটি রেসপন্স (এরর ছাড়া) পাবে, যদিও সেখানে সর্বসাম্প্রতিক ডেটা নাও থাকতে পারে। সিস্টেমটি সর্বদা ব্যবহারযোগ্য থাকবে। কোনো রিকোয়েস্ট অপূরণীয় থাকবে না।

Partition Tolerance (P) বা বিভাজন সহনশীলতা — সার্ভারগুলোর মধ্যে নেটওয়ার্ক যোগাযোগ বিচ্ছিন্ন হলেও সিস্টেমটি কাজ চালিয়ে যায়। নোডগুলোর মধ্যে মেসেজ হারিয়ে যেতে পারে বা বিলম্বিত হতে পারে। বাস্তব জগতে, নেটওয়ার্ক পার্টিশন সব সময়ই ঘটে — ক্যাবল কাটা পড়তে পারে, সুইচ ফেইল করতে পারে, ডেটা সেন্টার কানেক্টিভিটি হারাতে পারে।

যেহেতু ডিস্ট্রিবিউটেড সিস্টেমে নেটওয়ার্ক পার্টিশন অনিবার্য, তাই আপনাকে অবশ্যই P বেছে নিতে হবে। আসল পছন্দটি হলো একটি পার্টিশনের সময় C এবং A এর মধ্যে যেকোনো একটি বেছে নেওয়া:

  • CP সিস্টেম: যখন কোনো পার্টিশন ঘটে, তখন সিস্টেমটি Availability বিসর্জন দেয়। কিছু রিকোয়েস্ট ফেইল করতে পারে বা অপেক্ষায় থাকতে পারে, কিন্তু আপনি কখনই পুরানো (stale) ডেটা পাবেন না।
  • AP সিস্টেম: যখন কোনো পার্টিশন ঘটে, তখন সিস্টেমটি Consistency বিসর্জন দেয়। সব রিকোয়েস্ট রেসপন্স পাবে, কিন্তু কিছু ক্ষেত্রে পুরানো ডেটা রিটার্ন হতে পারে।
Note: এখানে মূল বিষয়টি হলো, যা বেশিরভাগ মানুষ ভুল করে: CAP শুধুমাত্র একটি নেটওয়ার্ক পার্টিশনের (network partition) সময় প্রযোজ্য হয়। যখন নেটওয়ার্ক সুস্থ থাকে, তখন আপনি তিনটিই পেতে পারেন। থিওরেমটি মূলত সেই পরিস্থিতি নিয়ে যখন কিছু ভুল হয় তখন আপনি কোনটি বিসর্জন দেবেন তা নির্ধারণ করে — এবং ডিস্ট্রিবিউটেড সিস্টেমে সব সময়ই মাঝে মাঝে ভুল বা সমস্যা দেখা দেয়।
▸ নেটওয়ার্ক পার্টিশন দেখা দিলে

প্রমাণের ধারণা (Proof Intuition)

চলুন এটিকে আরেকটু স্পষ্টভাবে বুঝি। আপনার দুটি ডেটাবেস সার্ভার রয়েছে, সার্ভার A এবং সার্ভার B, যারা একে অপরের মধ্যে ডেটা রেপ্লিকেট (replicate) করে। একটি নেটওয়ার্ক পার্টিশন তাদের মধ্যে সংযোগ বিচ্ছিন্ন করে দেয়।

একজন ক্লায়েন্ট সার্ভার A তে x = 5 রাইট করলো। এখন অন্য একজন ক্লায়েন্ট সার্ভার B থেকে x রিড করতে চায়।

বিকল্প ১ (Consistency বেছে নেওয়া): সার্ভার B জানে যে এর কাছে সর্বসাম্প্রতিক মান আছে কি না, তা সে যাচাই করতে পারবে না (কারণ এটি সার্ভার A এর সাথে যোগাযোগ করতে পারছে না)। তাই এটি রিড রিকোয়েস্ট প্রত্যাখ্যান করে — এরর রিটার্ন করে। ডেটা কনসিস্টেন্ট, কিন্তু সিস্টেমটি সার্ভার B তে রিড করার জন্য অ্যাভেইলেবল নয়।

বিকল্প ২ (Availability বেছে নেওয়া): সার্ভার B এর কাছে x এর যে মানটি রয়েছে তা রিটার্ন করে (হয়তো পুরানো মান, x = 3)। সিস্টেমটি অ্যাভেইলেবল — ক্লায়েন্ট একটি রেসপন্স পেয়েছে — কিন্তু ডেটা ইনকনসিস্টেন্ট বা অসামঞ্জস্যপূর্ণ (সার্ভার A বলে 5, সার্ভার B বলে 3)।

এখানে জাদুকরী কোনো তৃতীয় বিকল্প নেই। আপনাকে অবশ্যই একটি বেছে নিতে হবে।

▸ CP বেছে নেওয়া — Availability এর চেয়ে Consistency কে বেশি গুরুত্ব দেওয়া
Click chart to zoom
CAP ডিসিশন ট্রি: যখন একটি নেটওয়ার্ক পার্টিশন ঘটে, আসল পছন্দ হবে CP এবং AP এর মধ্যে

CP বনাম AP সিস্টেমের আচরণ

class CPDatabase:
    """Consistency + Partition Tolerance.
    During a partition, it refuses requests rather than serving stale data."""


    def __init__(self):
        self.data = {}
        self.can_reach_leader = True


    def write(self, key, value):
        if not self.can_reach_leader:
            raise Exception("503 Service Unavailable — cannot confirm write")
        self.data[key] = value


    def read(self, key):
        if not self.can_reach_leader:
            raise Exception("503 Service Unavailable — cannot guarantee consistency")
        return self.data.get(key)




class APDatabase:
    """Availability + Partition Tolerance.
    During a partition, it serves possibly stale data but never refuses requests."""


    def __init__(self):
        self.data = {}
        self.can_reach_leader = True


    def write(self, key, value):
        self.data[key] = value  # Writes locally, syncs later
        if self.can_reach_leader:
            pass  # Replicate to other nodes
        else:
            pass  # Queue for later replication (eventual consistency)


    def read(self, key):
        # Always returns something, even if it might be stale
        return self.data.get(key, None)




# Simulate a partition
cp = CPDatabase()
cp.data["balance"] = 100
cp.can_reach_leader = False  # Partition!
try:
    print(cp.read("balance"))  # Throws error — refuses to serve
except Exception as e:
    print(f"CP: {e}")


ap = APDatabase()
ap.data["balance"] = 100
ap.can_reach_leader = False  # Partition!
print(f"AP: balance = {ap.read('balance')}")  # Returns 100 (might be stale)
Output
CP: 503 Service Unavailable — cannot guarantee consistency
AP: balance = 100
▸ AP বেছে নেওয়া — Consistency এর চেয়ে Availability কে বেশি গুরুত্ব দেওয়া

বাস্তব জগতের উদাহরণ

CP সিস্টেম (Availability এর চেয়ে Consistency কে বেশি গুরুত্ব দেয়):

  • ZooKeeper — ডিস্ট্রিবিউটেড সিস্টেমে কোরিডিনেশনের জন্য ব্যবহৃত হয়। কনসিস্টেন্ট ডেটার গ্যারান্টি দিতে না পারলে এটি সার্ভ করতে আপত্তি জানায়। ভুল তথ্য দেওয়ার চেয়ে আন-অ্যাভেইলেবল থাকাই শ্রেয়।
  • HBase — একটি কনসিস্টেন্ট কলাম-ফ্যামিলি স্টোর (column-family store)। রাইটস একটি সিঙ্গেল লিডারের কাছে যায়; লিডারকে পাওয়া না গেলে রাইটস ফেইল করে।
  • MongoDB (মেজরিটি রাইট কনসার্ন সহ) — মেজরিটি নোড দ্বারা রাইট স্বীকার করানোর মাধ্যমে Consistency-কে অগ্রাধিকার দেওয়ার জন্য কনফিগার করা যেতে পারে।
  • ব্যাংকিং সিস্টেম — আপনার ব্যাংক ব্যালেন্স অবশ্যই সঠিক হতে হবে। সিস্টেম যদি সঠিকতার গ্যারান্টি দিতে না পারে, তবে ভুল ব্যালেন্স দেখানোর চেয়ে সাময়িকভাবে "temporarily unavailable" দেখানো ভালো।

AP সিস্টেম (Consistency এর চেয়ে Availability কে বেশি গুরুত্ব দেয়):

  • Cassandra — সর্বদা রাইটস গ্রহণ করে, এমনকি পার্টিশনের সময়ও। কনসিস্টেন্ট হ্যাশিং-এর মাধ্যমে ডেটা বণ্টন করে। পরে সিঙ্ক করার জন্য এটি eventual consistency ব্যবহার করে।
  • DynamoDB — অ্যামাজনের কী-ভ্যালু স্টোর, এটি অন্যতম একটি NoSQL ডেটাবেস। সর্বদা রিড/রাইট করা যায় এমনভাবে ডিজাইন করা হয়েছে। "Add to cart" যেন কখনই ফেইল না করে, এমনকি কার্টটি সাময়িকভাবে ইনকনসিস্টেন্ট হলেও।
  • DNS — ইন্টারনেটের ফোনবুক। এটি পুরানো মান ক্যাশ করে রাখে এবং একসময় আপডেট করে। আংশিক পুরনো DNS রেকর্ড থাকাটা কোনো DNS রেকর্ড না থাকার চেয়ে ভালো।
  • সোশ্যাল মিডিয়া ফিড — আপনার ইনস্টাগ্রাম ফিড ৫ সেকেন্ড পিছিয়ে থাকলে কেউ খুব একটা লক্ষ্য করবে না। তবে ইনস্টাগ্রাম ডাউন থাকলে সবাই লক্ষ্য করবে।
▸ বাস্তব জগতের CP এবং AP সিস্টেম

ইভেনচুয়াল কনসিস্টেন্সি (Eventual Consistency)

অনেক AP সিস্টেম আপস হিসেবে ইভেনচুয়াল কনসিস্টেন্সি ব্যবহার করে। এর লক্ষ্য হলো: পার্টিশন সেরে যাওয়ার পর, সব নোড একসময় একই ডেটাতে একত্রিত হবে। এখানে অসামঞ্জস্যতার একটি উইন্ডো বা গ্যাপ থাকতে পারে, তবে এটি অস্থায়ী।

বাস্তবে এটি কীভাবে কাজ করে?

  • রিড রিপেয়ার (Read repair): যখন কোনো রিড রিকোয়েস্ট রেপ্লিকাগুলোর মধ্যে অসামঞ্জস্যতা শনাক্ত করে, তখন এটি ব্যাকগ্রাউন্ডে রেপ্লিকাগুলোর মধ্যে সিংকনোনাইজেশন আপডেট ট্রিগার করে।
  • অ্যান্টি-এনট্রপি (মার্কল ট্রি) (Anti-entropy using Merkle trees): নোডগুলো হ্যাশ গাছের মাধমে তাদের ডেটা নিয়মিত তুলনা করে এবং পার্থক্যগুলো বিনিময় করে নেয়।
  • কনফ্লিক্ট রেজোলিউশন (Conflict resolution): যখন দুটি নোডে সাংঘর্ষিক রাইট (write) থাকে, তখন সিস্টেম তাদের সমাধান করে। লাস্ট-রাইট-উইনস (LWW) হলো সবচেয়ে সহজ কৌশল। ভেক্টর ক্লক বা CRDT হলো আরও উন্নত পদ্ধতি।

ইভেনচুয়াল কনসিস্টেন্সির ক্ষেত্রে মূল প্রশ্ন হলো: এই "ইভেনচুয়াল" বা চূড়ান্ত পর্যায়টা বাস্তবে কতটা সময় নেয়? বাস্তবে এটি মিলিসেকেন্ড থেকে কয়েক সেকেন্ড পর্যন্ত সময় নিতে পারে। তবে খারাপ পার্টিশনের সময় এটি কয়েক মিনিট বা পরীক্ষামূলক দীর্ঘ সময় নিতে পারে।

CAP-এর বাইরে: PACELC থিওরেম

CAP শুধুমাত্র পার্টিশন চলাকালীন আচরণ বর্ণনা করে। কিন্তু স্বাভাবিক অবস্থায় কী হয়? ঠিক এখানেই PACELC (উচ্চারণ "পাস-এলক") এর ভূমিকা আসে।

PACELC বলে: যদি কোনো পার্টিশন (P) থাকে, তবে Availability (A) এবং Consistency (C) এর মধ্যে যেকোনো একটি বেছে নিন। অন্যথায় (E), সিস্টেমটি যখন স্বাভাবিকভাবে চলছে, তখন Latency (L) এবং Consistency (C) এর মধ্যে একটি বেছে নিন।

  • PA/EL — পার্টিশন চলাকালীন: Availability বেছে নিন। স্বাভাবিক অবস্থায়: লো-ল্যাটেনসি বেছে নিন। উদাহরণ: Cassandra, DynamoDB। এগুলো ইভেনচুয়াল কনসিস্টেন্সি সহকারে দ্রুত এবং সর্বদা ব্যবহারযোগ্য।
  • PC/EC — পার্টিশন চলাকালীন: Consistency বেছে নিন। স্বাভাবিক অবস্থায়: তবুও Consistency বেছে নিন (এমনকি ল্যাটেনসির মূল্যে হলেও)। উদাহরণ: গতানুগতিক RDBMS যেমন PostgreSQL, ZooKeeper।
  • PA/EC — পার্টিশন চলাকালীন: Availability বেছে নিন। স্বাভাবিক অবস্থায়: Consistency বেছে নিন। উদাহরণ: MongoDB (ডিফল্ট কনফিগারেশন)। এটি একটি সাধারণ এবং বাস্তবসম্মত ট্রেড-অফ।

PACELC সিস্টেমটি ভালো এবং খারাপ দুই সময়ে কীরকম আচরণ করে তার একটি সম্পূর্ণ চিত্র দেয়।

Note: সাক্ষাৎকারের টিপস: যখন কেউ CAP সম্পর্কে জিজ্ঞাসা করে, শুধু সংজ্ঞা আওড়াবেন না। ব্যাখ্যা করুন যে আসল পছন্দ হলো পার্টিশনের সময় CP এবং AP এর মধ্যে (যেহেতু P ডিস্ট্রিবিউটেড সিস্টেমগুলোতে বাধ্যতামূলক)। এরপরে PACELC এর উল্লেখ করে বোঝান যে আপনি সিস্টেমের স্বাভাবিক পরিস্থিতির ট্রেড-অফগুলোও ভালো বোঝেন। এটি আপনার গভীর বোঝাপড়া প্রদর্শন করে।

Key Metrics

CP রিড (পার্টিশনের সময়)
পুরানো রিড প্রত্যাখ্যান করে
এরর / টাইমআউট —
AP রিড (পার্টিশনের সময়)
সম্ভাব্য পুরানো ডেটা রিটার্ন করে
~১-৫ ms \(O(1)\)
ইভেনচুয়াল কনসিস্টেন্সি উইন্ডো
সিস্টেম এবং লোডের ওপর নির্ভর করে
~১০-১০০০ ms —
স্ট্রং কনসিস্টেন্সি ল্যাটেনসি
CoreQuorum এর মাধ্যমে নিশ্চিত করতে হবে
+৫-৫০ ms —
কোরাম রিড (Quorum read, N=3, R=2)
৩ টি রেপ্লিকার মধ্যে ২ টির জন্য অপেক্ষা করুন
~৫-২০ ms —

ছোট কুইজ

একটি ডিস্ট্রিবিউটেড সিস্টেমে নেটওয়ার্ক পার্টিশন ঘটেছে। আপনার সিস্টেমটি সব রিকোয়েস্ট সার্ভ করে যাচ্ছে তবে কিছু রেসপন্সে পুরানো ডেটা থাকতে পারে। এটি কোন ধরনের সিস্টেম?

পড়া চালিয়ে যান