সেশন ১৫

CAP Theorem - Network ভাঙলে কোনটা ছাড়বেন

এই সেশনের লক্ষ্য: Network partition হলে কেন consistency আর availability এর মধ্যে একটা বেছে নিতে হয়, সেটা বোঝা। কোন system CP আর কোনটা AP, আর partition না থাকলেও latency আর consistency এর মধ্যে কী বাছাই থাকে (PACELC), সেটা চেনা। শেষে quorum (R + W > N) আর consistency level দিয়ে ঠিক করা, কোন data তে কতটা নিশ্চয়তা লাগবে।

০০ যে প্রশ্নগুলোর উত্তর খুঁজবো

সেশন ০৩ এ আমরা data এর copy রাখতে শিখেছিলাম। একটা primary, কয়েকটা replica। তখন একটা ছোট অস্বস্তি ছিলো: replica মাঝে মাঝে একটু পিছিয়ে থাকে (replication lag)। সেটা আমরা মেনে নিয়েছিলাম, কারণ copy গুলো একই data center এ ছিলো, আর lag ছিলো কয়েক millisecond।

এবার copy গুলো থাকবে দুইটা দেশে, মাঝে সমুদ্র। আর একদিন সেই সমুদ্রের নিচের cable কেটে যাবে। তখন system কে এমন একটা প্রশ্নের উত্তর দিতে হবে, যার কোনো নিখুঁত উত্তর নেই। এই সেশনে আমরা সেই প্রশ্নটা বুঝবো, আর শিখবো কীভাবে আগে থেকেই ঠিক করে রাখা যায় কোন data তে কী ছাড় দেওয়া চলে।

  • ১ Dhaka আর Singapore এর মাঝের cable কাটলে কী হয়? (network partition)
  • ২ CAP এ consistency আর availability বলতে ঠিক কী বোঝায়?
  • ৩ Partition এর সময় C আর A দুটো একসাথে কেন পাওয়া যায় না?
  • ৪ CP আর AP: কোন system কোনটা বেছে নেয়?
  • ৫ "CA" system কেন বাস্তবে হয় না?
  • ৬ Partition না থাকলে কি কোনো বাছাই নেই? (PACELC)
  • ৭ Quorum কী, আর R + W > N কেন কাজ করে?
  • ৮ Strong, read-your-writes, eventual: কোন consistency level কোথায়?
  • ৯ সব মিলিয়ে: সেই রাতে কী সিদ্ধান্ত হলো, আর পরে design কীভাবে বদলালো?

০১ Dhaka আর Singapore এর মাঝের cable কাটলে কী হয়?

ঈদের আগের রাত, আটটা চল্লিশ। পকেটপে নামের একটা mobile wallet এ তখন সেকেন্ডে প্রায় ১,২০০টা payment হচ্ছে। জুবায়ের সেই রাতে on-call engineer, মানে কিছু ভাঙলে তাকেই প্রথমে ডাকা হবে। সে মাত্র বাসায় ফিরে এক কাপ চা নিয়ে বসেছে। তখনই phone বেজে উঠলো: “Dhaka থেকে Singapore এ replication থেমে গেছে।” কয়েক মিনিটের মধ্যে খবর এলো, সমুদ্রের নিচের একটা cable কেটে গেছে। Team lead তানিয়া আপা call এ একটাই প্রশ্ন করলেন: “Singapore এ যে payment গুলো আসছে, সেগুলো কি নেবো, নাকি ফিরিয়ে দেবো?”

প্রশ্নটা বুঝতে আগে পকেটপে এর setup টা দেখা যাক। পকেটপে দুইটা data center (DC) চালায়: একটা Dhaka তে, একটা Singapore এ। দুই জায়গাতেই app server আছে, আর প্রত্যেকের কাছে সব user এর balance এর একটা copy আছে। প্রায় ৬০% user এর request Dhaka তে যায়, বাকি ৪০% Singapore এ। স্বাভাবিক দিনে এক জায়গায় কোনো balance বদলালে ৫০ millisecond এর মধ্যেই অন্য জায়গায় সেই খবর পৌঁছে যায়।

এখন সেই খবর যাওয়ার রাস্তাটাই বন্ধ:

user (৬০%) ঢাকায় পৌঁছায় user (৪০%) Singapore এ পৌঁছায় সমুদ্রের নিচের cable link কাটা Dhaka DC app server + database replica সুমির balance: ৫,০০০ টাকা Singapore DC app server + database replica সুমির balance: ৫,০০০ টাকা "Singapore কি down, নাকি শুধু রাস্তা বন্ধ?" "Dhaka কি down, নাকি শুধু রাস্তা বন্ধ?" দুই পাশই চালু, user ও আসছে; শুধু একে অপরের খবর পাচ্ছে না
Network partition মানে machine গুলো চালু আছে, কিন্তু তাদের মাঝের network ভেঙে গেছে। Dhaka আর Singapore দুই পাশেই user আসছে, দুই পাশেই সুমির balance এর একটা copy আছে। কিন্তু কেউ জানে না অন্য পাশে কী ঘটছে। ওপাশ down, নাকি শুধু রাস্তা বন্ধ, সেটাও বোঝার উপায় নেই।

এই অবস্থার নাম network partition। Partition মানে machine গুলো ঠিকঠাক চালু আছে, user ও আসছে, কিন্তু machine গুলোর মাঝের network ভেঙে গেছে। ফলে system দুই বা তার বেশি দলে ভাগ হয়ে যায়। প্রতিটা দল নিজের মধ্যে কথা বলতে পারে, কিন্তু অন্য দলের খবর পায় না।

সবচেয়ে অস্বস্তির ব্যাপার হলো, কোনো পাশই নিশ্চিত হতে পারে না ওপাশে কী হয়েছে। Singapore জানে না Dhaka down হয়ে গেছে, নাকি শুধু রাস্তা বন্ধ। কারণ দুই ক্ষেত্রেই ওপাশ থেকে কোনো উত্তর আসে না। আর চুপ থাকা machine এর কাছে “আমি crash করেছি” আর “আমার কথা পৌঁছাচ্ছে না” একই রকম শোনায়।

Partition বিরল ঘটনা নয়

শুধু cable কাটা নয়। একটা router নষ্ট হলে, কেউ ভুল firewall rule দিলে, বা একটা server কয়েক সেকেন্ডের জন্য আটকে গেলেও একই অবস্থা হয়। মেশিন যত বেশি, আর তাদের মাঝের দূরত্ব যত বেশি, partition তত বেশি ঘটে। তাই প্রশ্নটা “partition হবে কিনা” নয়। প্রশ্নটা হলো, “হলে আপনার system কী করবে?”

০২ CAP এ consistency আর availability বলতে ঠিক কী বোঝায়?

CAP theorem তিনটা শব্দের প্রথম অক্ষর দিয়ে নাম পেয়েছে: Consistency, Availability আর Partition tolerance। ২০০০ সালে Eric Brewer প্রথম এই ধারণাটা বলেন, আর ২০০২ সালে দুইজন গবেষক এটা গাণিতিকভাবে প্রমাণ করেন। কিন্তু এখানে শব্দগুলোর মানে আমাদের রোজকার মানে থেকে একটু আলাদা, তাই আগে সেগুলো পরিষ্কার করে নেওয়া যাক।

একটা জিনিস গুলিয়ে ফেলবেন না। Database এর ACID এর মধ্যেও একটা C আছে। সেই C এর মানে হলো data সবসময় নিয়ম মেনে চলবে, যেমন balance কখনো minus হবে না। CAP এর C এর মানে আলাদা: সব copy থেকে একই, সর্বশেষ উত্তর পাওয়া।

সুমির উদাহরণে দেখা যাক। সুমি পকেটপে এর একজন user, তার balance ৫,০০০ টাকা। Cable কাটার ঠিক এক মিনিট পরে সে Dhaka দিয়ে মাকে ৪,০০০ টাকা পাঠালো। দুই সেকেন্ড পরে সে আবার app খুললো, আর এবার তার request গেলো Singapore এ:

Dhaka node Singapore node ৮:৪১:০১ write balance ৫,০০০ থেকে ১,০০০ copy পাঠাতে চায় পৌঁছায় না ৮:৪১:০৩ read সুমির app এবার Singapore এ C মানলে A মানলে সঠিক উত্তর, নাহলে error নতুন balance জানা নেই, তাই error "একটু পরে আবার চেষ্টা করুন" উত্তর দেবেই, পুরোনো হলেও স্ক্রিনে দেখায় ৫,০০০ টাকা আসলে আছে ১,০০০ টাকা
সুমি Dhaka তে ৪,০০০ টাকা পাঠালো। খবরটা Singapore এ পৌঁছানোর আগেই cable কাটা। দুই সেকেন্ড পরে সুমির app balance চাইলো Singapore এর কাছে। Consistency মানলে Singapore সোজা বলে দেয় "এখন বলতে পারছি না"। Availability মানলে উত্তর দেয় ঠিকই, কিন্তু সেটা পুরোনো ৫,০০০ টাকা।

Singapore এর সামনে দুইটা পথ। সে বলতে পারে, “এখন balance দেখাতে পারছি না।” তাহলে Consistency রক্ষা হলো, কারণ ভুল কিছু বলেনি। কিন্তু Availability গেলো, কারণ একটা চালু machine error দিলো। অথবা সে নিজের কাছে থাকা ৫,০০০ টাকা দেখিয়ে দিতে পারে। তাহলে Availability রক্ষা হলো, কিন্তু Consistency গেলো, কারণ উত্তরটা পুরোনো।

০৩ Partition এর সময় C আর A দুটো একসাথে কেন পাওয়া যায় না?

Balance দেখানো নিয়ে ভুল হলে সুমি একটু বিভ্রান্ত হবে। কিন্তু টাকা খরচের বেলায় ভুলের দাম অনেক বেশি। এবার সেটাই দেখুন।

সুমির internet bill প্রতি মাসে auto-pay হয়, ৩,০০০ টাকা। এই কাজটা চলে Singapore এর server থেকে। কপাল খারাপ, ঠিক যে মুহূর্তে সুমি Dhaka দিয়ে মাকে ৪,০০০ টাকা পাঠালো, সেই মুহূর্তেই Singapore এ bill টা কাটার সময় হলো:

সুমির balance: ৫,০০০ টাকা cable কাটার আগে দুই DC তে একই Dhaka: মাকে ৪,০০০ দেখে ৫,০০০, তাই approve করে Singapore: bill ৩,০০০ এখানেও দেখে ৫,০০০ Singapore এখন কী করবে? A বেছে নিলে (AP) C বেছে নিলে (CP) AP: দুটোই approve খরচ ৭,০০০, আছে ৫,০০০ cable জুড়লে: -২,০০০ টাকা CP: Singapore refuse করে bill পরে আবার চেষ্টা হবে balance ঠিক থাকে: ১,০০০ CP এর দাম: partition যতক্ষণ চলে, Singapore এর payment ততক্ষণ বন্ধ
একই মুহূর্তে দুই পাশে দুইটা payment। দুই পাশই জানে balance ৫,০০০। Singapore approve করলে (AP) মোট ৭,০০০ টাকা খরচ হয়ে যায়, আর cable জোড়া লাগার পর হিসাব মেলাতে গিয়ে দেখা যায় balance minus ২,০০০। Singapore refuse করলে (CP) হিসাব ঠিক থাকে, কিন্তু সেই সময়টা ওপাশের user রা payment করতে পারে না।

Singapore approve করলে মোট ৭,০০০ টাকা খরচ হয়ে গেলো, অথচ সুমির ছিলো ৫,০০০। Cable জোড়া লাগার পর দুই পাশের হিসাব মেলাতে গিয়ে দেখা যাবে, balance minus ২,০০০ টাকা। এই টাকাটা কোম্পানিকে নিজের পকেট থেকে দিতে হবে, নাহলে সুমির কাছ থেকে আদায় করতে হবে। দুটোই কষ্টের।

Singapore refuse করলে হিসাব ঠিক থাকে। কিন্তু partition যতক্ষণ চলে, Singapore এ আসা সব payment ততক্ষণ ফেরত যায়। পকেটপে এর হিসাবে সেটা অনেক: সেকেন্ডে প্রায় ৪৮০টা payment (১,২০০ এর ৪০%)। দশ মিনিট চললে প্রায় তিন লাখ ফেরত যাওয়া payment, আর তিন লাখ বিরক্ত user।

তৃতীয় কোনো পথ নেই। Singapore যদি ঠিক উত্তর দিতে চায়, তাকে Dhaka কে জিজ্ঞেস করতে হবে। কিন্তু Dhaka পর্যন্ত কোনো message যাচ্ছে না। তাই হয় তাকে অপেক্ষা করতে বা error দিতে হবে (A ছাড়া), নয়তো নিজের পুরোনো তথ্য দিয়েই সিদ্ধান্ত নিতে হবে (C ছাড়া)। CAP theorem এই কথাটাই বলে।

CAP এর আসল কথা

Network partition চলার সময় একটা distributed system দুইটার একটা পারে। হয় সবসময় সঠিক উত্তর দেবে, দরকার হলে error দিয়ে (consistency)। নয়তো সবসময় উত্তর দেবে, পুরোনো হলেও (availability)। দুটো একসাথে পারে না, কারণ সঠিক উত্তর জানতে যে message দরকার, partition সেটাই আটকে রেখেছে।

০৪ CP আর AP: কোন system কোনটা বেছে নেয়?

Partition এর সময় consistency রাখে, দরকার হলে availability ছেড়ে দেয়, এমন system কে বলে CP। আর partition এর সময় availability রাখে, দরকার হলে পুরোনো data দেখায়, এমন system কে বলে AP।

কোনটা ভালো, সেটা নির্ভর করে ভুলের দাম আর অপেক্ষার দামের উপর। টাকার হিসাবে ভুল হলে সেটা ফেরত আনা কঠিন, তাই সেখানে মানুষ একটু অপেক্ষা মেনে নেয়। কিন্তু একটা social media feed এ একটা like দুই সেকেন্ড পরে দেখালে কারো ক্ষতি নেই, অথচ feed না খুললে user বিরক্ত হয়।

CPAP
Partition এ আচরণযে পাশ নিশ্চিত হতে পারে না, সে error দেয় বা অপেক্ষা করেদুই পাশই উত্তর দেয়, পরে copy গুলো মিলিয়ে নেয়
ঝুঁকিকিছু সময় কিছু user সেবা পায় নাকিছু user পুরোনো বা পরস্পরবিরোধী data দেখে
কোথায় মানায়টাকা, stock এর শেষ item, seat booking, lockFeed, like count, product review, shopping cart, DNS
উদাহরণHBase, ZooKeeper, etcd, MongoDB (default setting এ)Cassandra, DynamoDB (default read এ), CouchDB, DNS

উদাহরণের নামগুলো নিয়ে দুই কথা। HBase, MongoDB, Cassandra, DynamoDB আর CouchDB হলো অনেক machine জুড়ে data রাখার database। ZooKeeper আর etcd ছোট কিন্তু খুব জরুরি data রাখে, যেমন কোন server এখন primary, বা পুরো system এর configuration। এমন data ভুল হলে পুরো system ভুল পথে চলে, তাই এরা CP। আর DNS (সেশন ০৬) AP, কারণ একটু পুরোনো address পাওয়া কোনো address না পাওয়ার চেয়ে ভালো।

একটা কথা মনে রাখবেন। এই label গুলো পুরো product এর গায়ে চিরদিনের জন্য লাগানো থাকে না। অনেক database এ প্রতিটা request এর জন্য আলাদা setting দেওয়া যায়। যেমন DynamoDB তে সাধারণ read একটু পুরোনো data দিতে পারে, কিন্তু চাইলে “strongly consistent read” চাওয়া যায়। Cassandra তেও প্রতিটা query তে বলে দেওয়া যায় কতগুলো copy থেকে উত্তর লাগবে। এই হিসাবটা আমরা quorum এর section এ দেখবো।

একটা app এ দুইটাই থাকে

পকেটপে পুরোপুরি CP বা পুরোপুরি AP নয়। Payment আর টাকা পাঠানো CP হওয়া দরকার, কারণ ভুল হলে টাকা হারায়। কিন্তু cashback offer এর list বা notification count AP হলেই চলে। তাই CAP এর প্রশ্নটা পুরো system এর জন্য একবার নয়, প্রতিটা feature এর জন্য আলাদা করে করুন।

০৫ “CA” system কেন বাস্তবে হয় না?

CAP theorem অনেক সময় একটা ত্রিভুজ দিয়ে বোঝানো হয়। তিন কোণায় C, A আর P। বলা হয়, “যেকোনো দুইটা বেছে নিন।” তাহলে তো মনে হয় CA বেছে নিলেই হয়: সবসময় সঠিক, সবসময় উত্তর, শুধু partition সামলাবো না। কিন্তু এই ছবিটা ভুল পথে নিয়ে যায়।

প্রচলিত ছবি আসল ছবি CA CP AP C A P "তিনটার যেকোনো দুইটা বেছে নিন" মনে হয় CA ও একটা option, আসলে নয় একাধিক machine + network এটাই distributed system network কখনো না কখনো ভাঙবে cable কাটা, router নষ্ট, ভুল configuration P বাদ দেওয়ার উপায় নেই আসল প্রশ্ন: partition হলে C নাকি A?
বাঁয়ের ত্রিভুজটা বলে, তিনটা থেকে যেকোনো দুইটা নিন। শুনে মনে হয় CA (partition ছাড়া) বেছে নেওয়া যায়। কিন্তু একাধিক machine থাকলেই মাঝে network থাকে, আর network একদিন না একদিন ভাঙবেই। তাই P কোনো option নয়, এটা বাস্তবতা। বেছে নেওয়ার প্রশ্ন একটাই: partition হলে C রাখবেন, নাকি A।

সমস্যা হলো, partition আপনার বেছে নেওয়ার জিনিস নয়। Data দুইটা machine এ রাখলেই মাঝে একটা network থাকে। আর network এর উপর আপনার পুরো নিয়ন্ত্রণ নেই: cable কাটে, router নষ্ট হয়, কেউ ভুল configuration push করে। “আমরা partition সামলাবো না” বলার মানে শুধু এই যে partition এলে system কী করবে, সেটা আগে থেকে ঠিক করা নেই। তখন system হয়তো C আর A দুটোই হারাবে।

তাহলে CA বলে কি কিছুই নেই? আছে, কিন্তু সেটা একটা machine এ চলা database, যেমন একটা PostgreSQL server যার কোনো replica নেই। সেখানে network partition হওয়ার মতো দুইটা পাশই নেই। কিন্তু সেই machine টা down হলে সব কিছুই বন্ধ, তাই সেটাকেও সত্যিকারের “সবসময় available” বলা যায় না। আর এটা distributed system ও নয়, যেটা নিয়ে CAP কথা বলে।

সঠিকভাবে বলুন

Distributed system এ P বাদ দেওয়া যায় না। তাই CAP theorem কে “তিনটার দুইটা” না বলে এভাবে বলুন: partition হলে আপনাকে C আর A এর মধ্যে একটা বেছে নিতে হবে। Partition না থাকলে C আর A দুটোই পাওয়া সম্ভব।

০৬ Partition না থাকলে কি কোনো বাছাই নেই? (PACELC)

পকেটপে এর cable বছরে হয়তো দুই একবার কাটে, মোট কয়েক ঘণ্টা। বাকি সময়টা সব ঠিকঠাক চলে। তাহলে কি বাকি সময়টায় কোনো কঠিন সিদ্ধান্ত নেই? আছে। আর সেটা প্রতিটা request এ।

সুমি Dhaka দিয়ে টাকা পাঠালো। Dhaka এখন সুমিকে “সফল” বলবে কখন? দুইটা উপায় আছে।

Async (EL) copy পরে যায় copy পরে Singapore এ যায়; user কে অপেক্ষা করতে হয় না ৫ms user OK (৫ms) Sync (EC) copy শেষে OK ৫ms Singapore এ copy করে ack আনা: round trip ~৪০ms user OK (৪৫ms) 0 5ms 45ms সময় (ms) ঈদের রাতে সেকেন্ডে ১,২০০ payment। Sync হলে প্রতিটায় +৪০ms। আর Singapore একটু ধীর হলে Dhaka র প্রতিটা write ও ততটাই ধীর।
Cable ঠিক থাকলেও একটা বাছাই আছে। Async copy তে Dhaka নিজে লিখেই user কে OK বলে দেয় (৫ms), Singapore পরে copy পায়। তাই Singapore থেকে কিছুক্ষণ পুরোনো data পড়া যেতে পারে। Sync copy তে Singapore এর ack আসা পর্যন্ত অপেক্ষা (৪৫ms), বিনিময়ে দুই জায়গার data সবসময় এক। এটাই PACELC এর "E" অংশ: latency নাকি consistency।

Async copy: Dhaka নিজের database এ লিখেই সুমিকে “সফল” বলে দেয়, প্রায় ৫ms এ। Singapore copy টা পরে পায়। এতে payment দ্রুত হয়। কিন্তু সেই কয়েক millisecond এ কেউ Singapore থেকে পড়লে পুরোনো balance পাবে। এটাই সেশন ০৩ এর replication lag।

Sync copy: Dhaka লেখে, তারপর Singapore এ copy পাঠায়, Singapore এর “পেয়েছি” (ack) আসা পর্যন্ত অপেক্ষা করে। Dhaka থেকে Singapore এ message গিয়ে ফিরে আসতে প্রায় ৪০ms লাগে। তাই প্রতিটা payment এ সময় লাগে প্রায় ৪৫ms। বিনিময়ে দুই জায়গার data সবসময় এক।

২০১০ সালে Daniel Abadi এই বাছাইটা CAP এর সাথে জুড়ে দিয়ে একটা নতুন নাম দেন: PACELC। পুরো কথাটা হলো: Partition (P) হলে Availability (A) নাকি Consistency (C)? Else (E), মানে partition না থাকলে, Latency (L) নাকি Consistency (C)?

এই মুহূর্তে partition চলছে? হ্যাঁ (P) না (E, মানে Else) Availability নাকি Consistency? বছরে হয়তো কয়েক ঘণ্টা Latency নাকি Consistency? বাকি সব সময়, প্রতিটা request এ PA উত্তর দেয়, পুরোনো হলেও PC error দেয়, ভুল উত্তর নয় EL দ্রুত উত্তর, একটু পুরোনো হতে পারে EC অপেক্ষা করে, সর্বশেষটা দেয় Cassandra, DynamoDB (default): PA/EL · HBase, Google Spanner: PC/EC
PACELC দুইটা প্রশ্ন একসাথে করে। Partition (P) চললে: Availability (A) নাকি Consistency (C)? আর Else (E), মানে সব ঠিক থাকলে: Latency (L) নাকি Consistency (C)? প্রথম প্রশ্নটা বছরে কয়েক ঘণ্টার। দ্বিতীয়টা প্রতিটা request এর।

এভাবে একটা system কে দুই অক্ষরের জোড়া দিয়ে বর্ণনা করা যায়। Cassandra আর DynamoDB এর default setting হলো PA/EL: partition এ উত্তর দিয়ে যায়, আর স্বাভাবিক সময়েও দ্রুত উত্তরকে আগে রাখে। HBase আর Google Spanner হলো PC/EC: partition এ error দেয়, আর স্বাভাবিক সময়েও সর্বশেষ data দেওয়ার জন্য একটু বেশি সময় নেয়।

কেন PACELC বেশি কাজের

CAP শুধু partition এর কয়েক ঘণ্টার কথা বলে। PACELC বাকি সব সময়ের কথাও বলে। বছরে partition হয়তো তিন ঘণ্টা, কিন্তু latency আর consistency এর বাছাই হয় বছরের প্রতিটা সেকেন্ডে, প্রতিটা request এ। তাই design এর সময় দুইটা প্রশ্নই করুন।

০৭ Quorum কী, আর R + W > N কেন কাজ করে?

এতক্ষণ আমরা দুইটা চরম পথ দেখলাম। হয় শুধু একটা copy তে লিখে চলে যাওয়া (দ্রুত, কিন্তু পুরোনো data এর ঝুঁকি)। নয়তো সব copy তে লেখা শেষ হওয়া পর্যন্ত অপেক্ষা করা (নিশ্চিত, কিন্তু ধীর, আর একটা copy down হলেই write আটকে যায়)। মাঝামাঝি একটা পথ আছে, তার নাম quorum।

Quorum শব্দটা এসেছে সভা থেকে। একটা কমিটির সভায় সিদ্ধান্ত নিতে সব সদস্যের থাকা লাগে না, একটা নির্দিষ্ট সংখ্যক থাকলেই চলে। Data এর ক্ষেত্রেও তাই। তিনটা সংখ্যা দিয়ে নিয়মটা লেখা হয়:

ধরুন N=3, W=2, R=2। সুমির নতুন balance ১,০০০ টাকা লেখা হলো। Replica A আর B ack দিলো, তাই write সফল। Replica C তখনো পুরোনো ৫,০০০ ধরে আছে। এখন কেউ balance পড়তে চাইলে দুইটা replica কে জিজ্ঞেস করা হবে:

Write: balance ১,০০০ version v2 · W=2 (দুইটা ack লাগবে) Read: balance কত? R=2 (দুইটা replica কে জিজ্ঞেস) A: v2 ১,০০০ B: v2 ১,০০০ C: v1 ৫,০০০ (পুরোনো) Reader পায় v2 (B থেকে) আর v1 (C থেকে) বড় version টা নেয়: balance ১,০০০ W + R = 2 + 2 = 4, যা N = 3 এর চেয়ে বেশি; তাই দুই দলে অন্তত একটা replica common
তিনটা replica (N=3)। Write সফল ধরা হয় দুইটা replica ack দিলে (W=2), তাই A আর B তে নতুন balance আছে, C তে এখনো পুরোনোটা। Read দুইটা replica কে জিজ্ঞেস করে (R=2)। যে দুইটাই বাছুক, অন্তত একটা নতুন value জানে। প্রতিটা value এর সাথে version থাকে, তাই reader বড় version টাই নেয়।

Reader যেকোনো দুইটা replica বেছে নিক না কেন, তাদের অন্তত একটা A বা B হবেই। কারণ তিনটার মধ্যে দুইটা লিখেছে, আর দুইটা পড়ছে। দুই আর দুই মিলে চার, যা তিনের চেয়ে বেশি। তাই দুই দলের মধ্যে অন্তত একটা replica common থাকতেই হবে। প্রতিটা value এর সাথে একটা version number থাকে, তাই reader দুইটা উত্তরের মধ্যে বড় version টা নেয়।

এটাই বিখ্যাত শর্ত: R + W > N হলে প্রতিটা read অন্তত একটা এমন replica ছুঁয়ে যায়, যে সর্বশেষ write জানে। কয়েকটা setting পাশাপাশি দেখুন:

N = মোট replica · W = কয়টা ack পেলে write সফল · R = কয়টা replica থেকে read

N=3  W=2  R=2    2+2 = 4 > 3   নতুন value পাবেই; ১টা replica down হলেও read, write দুটোই চলে
N=3  W=1  R=1    1+1 = 2 ≤ 3   সবচেয়ে দ্রুত; কিন্তু read এ পুরোনো value আসতে পারে
N=3  W=3  R=1    3+1 = 4 > 3   read খুব দ্রুত; কিন্তু ১টা replica down হলেই write বন্ধ
N=5  W=3  R=3    3+3 = 6 > 5   ২টা replica down হলেও read, write দুটোই চলে

write চলতে পারে যতক্ষণ down replica ≤ N-W
read  চলতে পারে যতক্ষণ down replica ≤ N-R

খেয়াল করুন, এখানেও সেই পুরোনো বাছাই ফিরে এসেছে। W বাড়ালে write ধীর হয়, আর কয়েকটা replica down হলে write বন্ধ হয়ে যায়। W কমালে write দ্রুত হয়, কিন্তু R বাড়াতে হয়, নাহলে পুরোনো data আসে। N=3, W=2, R=2 জনপ্রিয়, কারণ এতে একটা replica down থাকলেও read আর write দুটোই চলে।

Partition এ quorum কী করে

এবার quorum কে cable কাটার রাতে বসিয়ে দেখি। ধরুন পকেটপে তিনটা replica রাখে: দুইটা Dhaka তে, একটা Singapore এ। N=3, W=2, R=2:

Dhaka পাশ Singapore পাশ কথা চলছে Dhaka-1 Dhaka-2 Sing-1 ৩টার ২টা replica: majority আছে W=2, R=2 দুটোই মেলে payment চলছে, হিসাব ঠিক ৩টার ১টা replica quorum নেই payment refuse
নতুন design এ প্রতিটা balance এর তিনটা copy: দুইটা Dhaka তে, একটা Singapore এ। Cable কাটার পর Dhaka পাশে এখনো দুইটা replica একে অপরের সাথে কথা বলতে পারে, তাই W=2 আর R=2 মেলে। Singapore পাশে একটাই replica, quorum হয় না, তাই সে নিজে থেকেই payment refuse করে। CP আচরণটা কাউকে হাতে চালু করতে হয় না, quorum এর নিয়ম থেকেই আসে।

Dhaka পাশে দুইটা replica আছে, তারা একে অপরের সাথে কথা বলতে পারছে। তাই W=2 আর R=2 দুটোই মেলে, payment চলতে থাকে। Singapore পাশে একটাই replica। সে দুইটা ack কোথাও থেকে জোগাড় করতে পারবে না, তাই write নিজে থেকেই fail করে। Singapore এর কাউকে কোনো সিদ্ধান্ত নিতে হলো না। Quorum এর নিয়মই system কে CP বানিয়ে দিলো। আর যে পাশে বেশিরভাগ replica (majority) আছে, সেই পাশটা চালু থাকলো।

একটা সতর্কতা। Cassandra বা DynamoDB এর মতো system এ R + W > N হলেও কিছু বিরল ক্ষেত্রে পুরোনো data আসতে পারে, যেমন দুইটা write একদম একই সময়ে হলে। সবগুলো machine কে একদম নিখুঁতভাবে একমত করাতে আরো শক্ত নিয়ম লাগে, তার নাম consensus। সেটা আমরা সেশন ১৬ তে দেখবো।

কোথায় replica রাখবেন, সেটাও একটা সিদ্ধান্ত

Dhaka তে দুইটা replica রাখায় Dhaka র write খুব দ্রুত হয়। দুইটা ack ই আসে Dhaka র ভেতর থেকে, কয়েক millisecond এ, Singapore এর ৪০ms এর অপেক্ষা লাগে না। কিন্তু উল্টো দিকও আছে। পুরো Dhaka DC down হলে Singapore একা quorum পাবে না, তখন payment পুরোপুরি বন্ধ। কোন জায়গা হারানোর ঝুঁকি বেশি, সেটা ভেবে replica সাজাতে হয়।

০৮ Strong, read-your-writes, eventual: কোন consistency level কোথায়?

Consistency শুধু “আছে” বা “নেই” নয়। মাঝে কয়েকটা ধাপ আছে। প্রতিটা ধাপ একটু কম নিশ্চয়তা দেয়, কিন্তু বিনিময়ে একটু বেশি speed আর availability দেয়। এই সেশনে তিনটা ধাপ জানলেই চলবে।

পকেটপে এর কোন feature এ কোন level লাগে, দেখুন:

বেশি নিশ্চয়তা বেশি speed আর availability Strong সবাই সর্বশেষটা দেখে payment এর আগে balance check primary বা quorum থেকে read; একটু ধীর, partition এ error Read-your-writes নিজের লেখা নিজে দেখবেনই টাকা পাঠানোর পর নিজের history সুমি নিজে সাথে সাথে দেখে; অন্যরা একটু পরে দেখলেও চলে Eventual একটু পরে সবাই মিলবে cashback offer, বন্ধুর profile ছবি কাছের যেকোনো replica; সবচেয়ে দ্রুত, partition এও চলে
একটা app এর সব data এর জন্য একই level লাগে না। টাকা কাটার আগে balance পড়তে হয় strong consistency তে। নিজের history তে read-your-writes যথেষ্ট। আর cashback offer একটু পুরোনো হলে কারো ক্ষতি নেই, তাই eventual। উপরে উঠলে নিশ্চয়তা বাড়ে, নিচে নামলে speed আর availability বাড়ে।

Read-your-writes এর দরকারটা সবচেয়ে সহজে বোঝা যায় একটা ভুল থেকে। সুমি বন্ধুকে ৫০০ টাকা পাঠালো। তারপর history খুললো। History এর read গেলো এমন একটা replica তে, যেখানে copy তখনো পৌঁছায়নি। সুমি দেখলো তার পাঠানো টাকা history তে নেই। ভয় পেয়ে সে আবার ৫০০ টাকা পাঠালো। সেশন ০৩ এর profile ছবির উদাহরণে ঠিক এই ভুলটাই দেখেছিলেন।

সমাধানও সেখানে দেখেছিলেন। কেউ write করার পর কিছুক্ষণ (ধরুন ১০ সেকেন্ড) তার নিজের read primary থেকে পড়ানো হয়। আরেকটা উপায় হলো, write এর পর user এর app কে একটা version number দেওয়া। App পরের read এ সেটা পাঠায়, আর server এমন replica থেকে পড়ে যার কাছে অন্তত ঐ version আছে। দুই উপায়েই অন্য সবার read কাছের replica থেকেই দ্রুত হয়।

বাছাইয়ের সহজ প্রশ্ন

প্রতিটা data এর জন্য নিজেকে জিজ্ঞেস করুন: “এটা কয়েক সেকেন্ড পুরোনো দেখালে কার কী ক্ষতি?” টাকা কাটা যায় বা দুইজন একই seat পায়, এমন হলে strong। শুধু যে লিখেছে সে বিভ্রান্ত হয়, এমন হলে read-your-writes। কারো তেমন কোনো ক্ষতি নেই, এমন হলে eventual।

০৯ সব মিলিয়ে: সেই রাতে কী সিদ্ধান্ত হলো, আর পরে design কীভাবে বদলালো?

এবার জুবায়েরের রাতে ফিরে যাই। সেই সময় পকেটপে দুই DC তেই নিজে নিজে payment approve করতো, আর copy পাঠাতো async ভাবে। মানে system টা ছিলো AP, যদিও কেউ সেটা ভেবেচিন্তে বেছে নেয়নি।

৮:৪০ cable কাটা replication থেমে যায় দুই পাশই চালু ৮:৪১ alert জুবায়েরের phone বাজে "replication lag বাড়ছে" ৮:৪৬ সিদ্ধান্ত Singapore এ payment বন্ধ balance শুধু দেখা যায় ৮:৫৬ DNS বদল Singapore এর user রা Dhaka তে আসতে থাকে ৯:২২ link ফেরে অন্য পথে traffic চলে Singapore copy মেলায়
সেই রাতের ৪২ মিনিট। ছয় মিনিটের মাথায় সিদ্ধান্ত: Singapore আর নিজে থেকে payment নেবে না (CP)। তবে balance আর history দেখা যাবে, সাথে "সর্বশেষ আপডেট" এর সময়। তারপর DNS বদলে Singapore এর user দের Dhaka তে পাঠানো হলো। শেষে অন্য পথে link ফিরলে Singapore এর copy আবার Dhaka র সাথে মিলে গেলো।

ছয় মিনিটের মাথায় তানিয়া আপা আর জুবায়ের সিদ্ধান্ত নিলো: Singapore আর কোনো payment approve করবে না। জুবায়ের Singapore কে read-only mode এ দিলো। সেখানকার user রা balance আর history দেখতে পারছিলো, পাশে লেখা ছিলো “সর্বশেষ আপডেট: ৮:৪০”। কিন্তু টাকা পাঠাতে গেলে বার্তা আসছিলো, “একটু পরে আবার চেষ্টা করুন।” দশ মিনিট পরে DNS বদলে সেই user দের Dhaka তে পাঠানো শুরু হলো। পুরোপুরি সরতে আরো কিছুক্ষণ লাগলো, কারণ phone গুলো পুরোনো DNS উত্তর কিছুক্ষণ মনে রাখে (TTL, সেশন ০৬)। ৯:২২ এ অন্য পথে link ফিরলো, আর Singapore এর copy আবার Dhaka র সাথে মিলে গেলো।

তবে প্রথম ছয় মিনিটের হিসাব মেলাতে গিয়ে একটা অস্বস্তিকর সংখ্যা বের হলো। ঐ ছয় মিনিটে দুই পাশে একই account থেকে টাকা খরচ হয়েছে ৩৭টা account এ। সব মিলিয়ে প্রায় ১ লাখ ২০ হাজার টাকা বেশি খরচ হয়ে গেছে। ঈদের রাতে customer দের বিরক্ত না করে পকেটপে সেই টাকা নিজেই বহন করলো।

পরের সপ্তাহে team design বদলালো:

  1. Payment এ quorum: প্রতিটা balance এর তিনটা replica, দুইটা Dhaka তে আর একটা Singapore এ। W=2, R=2। Partition হলে majority পাশটা চলবে, আর অন্য পাশ নিজে থেকেই refuse করবে। কাউকে রাতে বসে সিদ্ধান্ত নিতে হবে না।
  2. Feature অনুযায়ী level: টাকা কাটার আগের balance check strong। History তে read-your-writes। Offer, notification আর rewards এর data eventual।
  3. Partition এর সময় user কে পরিষ্কার বার্তা: CP পাশে error এর বদলে বোঝার মতো বার্তা, আর পুরোনো data দেখালে পাশে “সর্বশেষ আপডেট” এর সময়।
সবচেয়ে গুরুত্বপূর্ণ শিক্ষা

আপনি C আর A এর মধ্যে বেছে না নিলে, partition এর রাতে system নিজেই একটা বেছে নেবে। আর সেটা সাধারণত আপনার পছন্দের হয় না। তাই প্রতিটা feature এর জন্য আগেই ঠিক করুন: partition এ কোনটা ছাড়বেন, আর স্বাভাবিক দিনে latency আর consistency এর মধ্যে কোনটা আগে।

১০ মগজে প্রেশার দিন

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

প্রশ্ন ১: Interview তে জিজ্ঞেস করা হলো, "CAP theorem কী?" আপনি কী বলবেন?
উত্তর দেখুন আগে নিজে ভাবুন

সবাই যেভাবে ভাবে

“CAP মানে Consistency, Availability আর Partition tolerance। একটা distributed system এই তিনটার যেকোনো দুইটা পেতে পারে। তাই system হয় CA, CP, নয়তো AP।”

সংজ্ঞাগুলো ঠিক আছে। কিন্তু “যেকোনো দুইটা” কথাটা ভুল ধারণা দেয়।

যে জায়গাটা যোগ করা দরকার

Distributed system এ partition হবেই, তাই P কোনো বাছাই নয়। আসল কথা হলো: partition চলার সময় consistency আর availability এর মধ্যে একটা ছাড়তে হয়। Partition না থাকলে দুটোই পাওয়া যায়। এর সাথে PACELC এর কথা বললে উত্তরটা আরো পূর্ণ হয়: স্বাভাবিক সময়েও latency আর consistency এর মধ্যে বাছাই থাকে।

শেষে একটা বাস্তব উদাহরণ দিন। যেমন: “Wallet এর payment CP, কারণ ভুল হলে টাকা হারায়। কিন্তু একই app এর notification AP।”

এক লাইনে

Partition এর সময় সঠিক উত্তর নাকি সবসময় উত্তর, এই দুইয়ের একটা। আর সেই বাছাই হয় প্রতিটা feature এর জন্য আলাদা করে।

প্রশ্ন ২: একটা data এর ৫টা replica (N=5)। Read অনেক বেশি হয়, তাই read দ্রুত চাই, আবার পুরোনো data ও চাই না। R আর W কত দেবেন?
উত্তর দেখুন আগে নিজে ভাবুন

সবাই যেভাবে ভাবে

“R=1 দিই, তাহলে read সবচেয়ে দ্রুত। R + W > N রাখতে W=5। তাহলে ১ + ৫ = ৬, যা ৫ এর চেয়ে বেশি। কাজ শেষ।”

হিসাব ঠিক, read ও দ্রুত। কিন্তু একটা বড় ঝুঁকি চোখ এড়িয়ে গেছে।

যে জায়গাটা যোগ করা দরকার

W=5 মানে প্রতিটা write এ পাঁচটা replica র ack লাগবে। একটা replica down হলে, বা partition এ একটা replica আলাদা হয়ে গেলেই, আর কোনো write হবে না। Write চলতে পারে যতক্ষণ down replica N-W এর বেশি না হয়, এখানে সেটা শূন্য।

ভালো উত্তর হলো R=2, W=4। তাতে ২ + ৪ = ৬, যা ৫ এর চেয়ে বেশি। Read এ দুইটা replica লাগে, তাও দ্রুত। আর একটা replica down থাকলেও write চলে। Read আর write এর ভার সমান হলে R=3, W=3 ভালো, তখন দুইটা replica down হলেও দুটোই চলে।

মনে রাখার উপায়

R + W > N দেয় নতুন data এর নিশ্চয়তা। N-W বলে কয়টা replica হারালেও write চলবে, N-R বলে read এর জন্য সেই সংখ্যা। তিনটা হিসাব একসাথে না করলে উত্তর অসম্পূর্ণ।

প্রশ্ন ৩: "Wallet এ টাকার ব্যাপার, তাই partition হলে পুরো system বন্ধ করে দেওয়াই নিরাপদ।" আপনি কি একমত?
উত্তর দেখুন আগে নিজে ভাবুন

সবাই যেভাবে ভাবে

“হ্যাঁ। টাকার ক্ষেত্রে consistency সবার আগে। কিছুক্ষণ সব বন্ধ থাকলে user রাগ করবে, কিন্তু টাকা তো হারাবে না।”

টাকার জন্য CP ঠিক আছে। কিন্তু “পুরো system বন্ধ” দরকারের চেয়ে অনেক বেশি ছাড়।

যে জায়গাটা যোগ করা দরকার

প্রথমত, পুরো system নয়, শুধু যে পাশে majority নেই সে পাশে write বন্ধ করলেই চলে। Quorum থাকলে majority পাশ স্বাভাবিকভাবে payment নিতে থাকে। পকেটপে এর ক্ষেত্রে ৬০% user এর কোনো সমস্যাই হয় না।

দ্বিতীয়ত, একই পাশেও সব কাজ বন্ধ করার দরকার নেই। Balance আর history “সর্বশেষ আপডেট” এর সময়সহ দেখানো যায়। Offer আর notification চলতে পারে। শুধু টাকা কাটার কাজটাই আটকাতে হয়।

তৃতীয়ত, ব্যবসাও একটা সীমা ঠিক করতে পারে। কিছু payment system ঝুঁকি মেপে খুব ছোট payment partition এর সময়েও নিয়ে নেয়। যেমন ২০০ টাকা পর্যন্ত। সবচেয়ে খারাপ ক্ষেত্রে ক্ষতি কত হবে, সেটা আগে থেকে জানা থাকে, আর সেই ক্ষতি ব্যবসা মেনে নিতে রাজি থাকে।

আসল কথা

CAP এর বাছাই পুরো system এর জন্য একটা switch নয়। প্রতিটা operation এর জন্য আলাদা করে ভাবুন: কোনটা আটকালে ক্ষতি বেশি, আর কোনটা ভুল হলে ক্ষতি বেশি।

১১ যে টার্মগুলো শিখলাম

টার্মমানে
Network partitionMachine গুলো চালু আছে, কিন্তু তাদের মাঝের network ভেঙে system কয়েকটা দলে ভাগ হয়ে গেছে।
CAP theoremPartition চলার সময় একটা distributed system consistency আর availability দুটো একসাথে দিতে পারে না।
Consistency (CAP অর্থে)যেকোনো machine থেকে read করলে সর্বশেষ write টাই পাওয়া যায়, নাহলে error। পুরোনো উত্তর কখনো নয়।
Availability (CAP অর্থে)চালু থাকা প্রতিটা machine প্রতিটা request এ একটা আসল উত্তর দেয়, error নয়। উত্তরটা পুরোনো হতে পারে।
Partition toleranceNetwork ভাঙলেও system চলতে থাকে। Distributed system এ এটা বাছাই নয়, বাধ্যতামূলক।
CPPartition এর সময় consistency রাখে, দরকার হলে error দেয়। যেমন HBase, ZooKeeper, etcd।
APPartition এর সময় availability রাখে, দরকার হলে পুরোনো data দেয়। যেমন Cassandra, DynamoDB (default)।
PACELCPartition হলে A নাকি C, আর না হলে (Else) latency নাকি consistency।
Quorumসফল ধরার জন্য সব replica নয়, একটা নির্দিষ্ট সংখ্যক replica র সাড়া লাগবে, এই নিয়ম।
N, W, Rমোট replica, write সফল হতে কয়টা ack লাগবে, আর read এ কয়টা replica কে জিজ্ঞেস করা হবে।
R + W > Nএই শর্ত মানলে প্রতিটা read অন্তত একটা এমন replica ছোঁয় যে সর্বশেষ write জানে।
Majorityঅর্ধেকের বেশি replica। Partition এ যে পাশে majority থাকে, quorum সেই পাশেই মেলে।
Strong consistencyসবাই সবসময় সর্বশেষ write দেখে।
Read-your-writesনিজে যা লিখেছেন, পরে পড়লে সেটা অবশ্যই দেখবেন। অন্যরা একটু পরে দেখতে পারে।
Eventual consistencyএখন replica গুলো আলাদা কথা বলতে পারে, কিন্তু নতুন write না এলে কিছুক্ষণ পরে সবাই মিলে যায় (সেশন ০৩)।

১২ শর্ট সামারি

  1. Network partition হলে machine গুলো চালু থাকে, কিন্তু একে অপরের খবর পায় না। তখন প্রতিটা machine কে বেছে নিতে হয়: error দিয়ে হলেও সঠিক থাকবে (CP), নাকি পুরোনো হলেও উত্তর দেবে (AP)।
  2. Distributed system এ partition এড়ানো যায় না, তাই “CA” বাস্তব কোনো option নয়। আর PACELC মনে করিয়ে দেয়, partition না থাকলেও প্রতিটা request এ latency আর consistency এর মধ্যে বাছাই থাকে।
  3. Quorum এ R + W > N রাখলে প্রতিটা read অন্তত একটা নতুন replica ছুঁয়ে যায়। Partition এ শুধু majority পাশ চলে, তাই system নিজে থেকেই CP আচরণ করে।
  4. সব data এর জন্য একই নিশ্চয়তা লাগে না। টাকার জন্য strong, নিজের history র জন্য read-your-writes, আর offer বা notification এর জন্য eventual consistency যথেষ্ট।

১৩ মনে রাখুন