۱1 خطی‌پذیری (Linearizability)Linearizability
۱.۱. یک نسخه از داده، یک تضمین تازگی1.1. One copy of the data, one freshness guarantee
خطی‌پذیری یعنی رفتارِ چند نسخهٔ داده برای یک عملیات، شبیه یک نسخهٔ واحد باشد: خواندنی که پس از پایانِ نوشتن شروع می‌شود باید آن نوشتن یا تغییرِ بعدی را ببیند.
مثال فنی: پس از پاسخ موفق
وضعیت اولیه: SET x=1 کامل شده؛ سپس کلاینت دیگری GET x را آغاز می‌کند و نوشتن تازه‌ای وجود ندارد.
اجرای مرحله‌به‌مرحله: خواندنِ خطی‌پذیر باید ۱ ببیند؛ replicaِ عقب‌مانده که ۰ می‌دهد این قرارداد را نقض می‌کند.
نتیجه و دلیل: خطی‌پذیری ترتیبِ زمان واقعیِ عملیاتِ غیرهم‌پوشان را رعایت می‌کند، نه صرفاً همگرایی نهایی را.
When data spreads across replicas (Chapter 6), inconsistency looms: a read may hit a lagging replica and return stale results. Two philosophies exist: eventual consistency (the application copes with conflicts itself) and strong consistency (the system behaves as if it were one node). Linearizability — also called atomic consistency or external consistency — is the precise definition of that second philosophy.
تعریف در یک جمله: به محض آنکه یک نوشته با موفقیت تمام شد، همه‌ی خواندن‌های بعدی (از هر کلاینتی)
باید مقدارِ جدید یا جدیدتر را ببینند. به این می‌گویند تضمینِ تازگی (recency guarantee).
مثالِ کتاب: دو نفر که نتیجه‌ی یک بازی را نگاه می‌کنند؛ نفرِ اول صفحه را رفرش می‌کند و نتیجه را می‌بیند و به نفرِ دوم می‌گوید؛
نفرِ دوم رفرش می‌کند ولی به replica عقب‌افتاده می‌رسد و هنوز «بازی ادامه دارد» می‌بیند.
اگر هر دو هم‌زمان رفرش کرده بودند، جوابِ متفاوت عجیب نبود؛ اما نفرِ دوم بعد از شنیدنِ خبر رفرش کرده —
و این دقیقاً نقضِ خطی‌پذیری است.
The one-sentence definition: as soon as a write completes successfully, every later read (from any client) must see the new value or a newer one. This is the recency guarantee. The book's example: two people watching a match score; the first refreshes, sees the result and tells the second; the second refreshes but lands on a lagging replica and still sees “match in progress”. Had both refreshed simultaneously, different answers would be unsurprising; but the second refreshed after hearing the news — and that is exactly a linearizability violation.
۱.۲. چه چیزی یک سیستم را خطی‌پذیر می‌کند؟1.2. What makes a system linearizable?
در خطی‌پذیری، می‌توان هر عملیات را در یک لحظه میان شروع و پایانش قرار داد و ترتیبِ سازگار ساخت. عملیات‌های هم‌پوشان ممکن است ترتیب‌های مجازِ متفاوتی داشته باشند.
مثال فنی: عملیات هم‌پوشان
وضعیت اولیه: خواندن x زمانی شروع می‌شود که نوشتن x=1 هنوز پاسخ نداده است؛ مقدار قبلی ۰ است.
اجرای مرحله‌به‌مرحله: بسته به نقطهٔ خطی‌شدن، خواندن می‌تواند ۰ یا ۱ برگرداند؛ پس از دیدن نوشتنِ کامل‌شده، خواندنِ بعدی بدون نوشتن جدید به ۰ برنمی‌گردد.
نتیجه و دلیل: باید کل تاریخچه با ترتیب لحظه‌ایِ معتبر سازگار باشد؛ معیار، ساعتِ برچسب‌خوردهٔ کلاینت‌ها نیست.
To be precise, we draw operations as timeline bars: bar start = request sent, bar end = response received. The client never knows exactly when processing happened; only that it was somewhere in between. If two bars overlap, those operations are concurrent from the system's view and any order is allowed.
اما «خواندنِ هم‌زمان هر جوابی بدهد» کافی نیست: وگرنه مقدار می‌توانست چند بار بینِ ۰ و ۱ بپرَد و برگردد!
قانونِ دوم این است: تصور کنید نقطه‌ای بینِ شروع و پایانِ نوشته هست که مقدار در آن لحظه atomically از ۰ به ۱ می‌پرَد
(به آن می‌گویند linearization point). خطی که این نقطه‌ها را به هم وصل می‌کند
باید همیشه به جلو برود، هرگز به عقب. یعنی به محض آنکه خواندنی مقدارِ جدید را دید، همه‌ی خواندن‌های بعدی هم باید همان یا جدیدتر را ببینند.
But “concurrent reads may return anything” is not enough: otherwise the value could bounce between 0 and 1 forever! The second rule: imagine a point between the write's start and end where the value flips atomically from 0 to 1 (called the linearization point). The line connecting these points must always move forward, never back. Once a read sees the new value, every later read must see it or something newer.
روایت مدرس — نمودار ۱ را با صدای بلند بخوانیمTeacher narration
مثال فنی برای خواندنِ نمودار: عملیات هم‌پوشان
وضعیت اولیه: خواندن x زمانی شروع می‌شود که نوشتن x=1 هنوز پاسخ نداده است؛ مقدار قبلی ۰ است.
اجرای مرحله‌به‌مرحله: بسته به نقطهٔ خطی‌شدن، خواندن می‌تواند ۰ یا ۱ برگرداند؛ پس از دیدن نوشتنِ کامل‌شده، خواندنِ بعدی بدون نوشتن جدید به ۰ برنمی‌گردد.
نتیجه و دلیل: باید کل تاریخچه با ترتیب لحظه‌ایِ معتبر سازگار باشد؛ معیار، ساعتِ برچسب‌خوردهٔ کلاینت‌ها نیست.
نمودار دو بند دارد. بندِ بالا با عنوانِ «یک اجرای خطی‌پذیر» شروع می‌شود: سه ردیفِ رنگی داریم به نام‌های
client A و client B و client C.
روی ردیفِ C یک نوارِ بنفش است به نام write(x, 1) ⇒ OK — یعنی C دارد مقدارِ x را از ۰ به ۱ تغییر می‌دهد.
روی ردیفِ A دو نوارِ خواندن می‌بینی: اولی read(x) ⇒ 0 که تمام و کمال قبل از شروعِ نوشته قرار گرفته،
پس حتماً باید مقدارِ کهنه یعنی ۰ را برگرداند. دومی read(x) ⇒ 1 که با نوشته هم‌پوشانی دارد.
حالا خطِ عمودیِ خط‌چینِ زرد را دنبال کن: از بالای بند تا پایینِ نوارِ C کشیده شده و زیرش نوشته
«نقطه‌ی خطی‌سازی — x در همین‌جا به‌طور اتمی ۱ می‌شود». این نقطه داخلِ نوارِ نوشته است — جایی بینِ شروع و پایانش.
نوارِ اولِ A سمتِ چپِ این خط است (پس ۰)، نوارِ دومِ A از روی آن می‌گذرد (و ۱ برمی‌گرداند)،
و نوارِ سبزِ read(x) ⇒ 1 روی ردیفِ B کاملاً سمتِ راستِ آن است.
پیوندِ مهم همان فلشِ سبزِ کوچک بینِ انتهای نوارِ دومِ A و ابتدای نوارِ B است که کنارش نوشته «ترتیبِ زمانیِ واقعی»:
خواندنِ B بعد از تمام‌شدنِ خواندنِ A شروع شده، پس حتی اگر نوشته هنوز تمام نشده باشد، B هم باید ۱ ببیند.
بندِ پایین همان قانون را به‌شکلِ یک نقض نشان می‌دهد: خواننده‌ی ۱ نوارِ read(x) ⇒ 1 دارد؛
بعد فلشِ صورتی به سمتِ نوارِ قرمزِ خواننده‌ی ۲ می‌رود که رویش نوشته read(x) ⇒ 0 — STALE
و کنارِ فلش جمله‌ی «۲ بعد از شنیدنِ نتیجه توسط ۱ دوباره خواند». این همان اشتباهِ معروف است: خواندن به عقب برگشته.
جعبه‌ی سمتِ راست قاعده را جمع می‌کند: «تا وقتی مقدارِ جدیدی بازنویسی نشده، هیچ خواندنِ بعدی نباید از آنچه قبلاً دیده‌ایم کهنه‌تر باشد.»
Read the top half as one linearizable execution across three rows, client A, client B and client C. C's purple bar write(x, 1) ⇒ OK flips x from 0 to 1. A's first read read(x) ⇒ 0 sits entirely before the write, so it must return the old value 0; the second read read(x) ⇒ 1 overlaps the write.
The dashed yellow vertical line is the linearization point — the instant x atomically becomes 1, somewhere inside the write bar. A's first bar is left of it (hence 0), the second crosses it (hence 1), and B's green read(x) ⇒ 1 is fully right of it. The small green arrow between A's second bar and B's bar marks real-time order: B started after A's read finished, so B must see 1 too, even if the write hasn't finished.
The bottom half shows the violation: reader 1 returns read(x) ⇒ 1, then a pink arrow leads to reader 2's red read(x) ⇒ 0 — STALE bar — reader 2 re-read after hearing reader 1's result. Time moved backward. The rule box on the right sums it up: once a new value is visible, no later read may return anything older.
۱.۳. خطی‌پذیری در برابر سریال‌پذیری1.3. Linearizability vs serializability
خطی‌پذیری دربارهٔ سازگاریِ عملیات با زمان واقعی است؛ سریال‌پذیری دربارهٔ نتیجهٔ تراکنش‌های چندعملیاتی است. داشتن یکی، خودبه‌خود دیگری را ثابت نمی‌کند.
مثال فنی: تراکنش serial با خواندن کهنه
وضعیت اولیه: دو تراکنش انتقال را می‌توان به یک ترتیب serial توضیح داد.
اجرای مرحله‌به‌مرحله: اما خواندن جداگانه‌ای که بعد از پاسخ commit آغاز شده، ممکن است از replica قدیمی بیاید، اگر سیستم فقط serializability وعده داده باشد.
نتیجه و دلیل: serializability دربارهٔ تداخل تراکنش‌هاست؛ linearizability ترتیب زمان واقعیِ عملیات را می‌خواهد. ترکیب مناسب به strict serializability می‌رسد.
The two words sound alike but belong to different axes, and confusing them is a classic interview mistake.
| Linearizability | Serializability |
|---|
| درباره‌ی چیست |
تضمینِ تازگی برای یک شیء (register: یک کلید، یک سطر، یک سند) |
سطحِ ایزوله‌سازیِ تراکنش‌ها؛ هر تراکنش می‌تواند چند شیء را بخواند و بنویسد |
| چه چیزی را تضمین می‌کند |
اگر عملیاتِ A قبل از شروعِ B تمام شود، B باید وضعیتِ هم‌تازه‌ی A یا جدیدتر را ببیند |
نتیجه‌ی تراکنش‌ها انگار به‌صورتِ سریال اجرا شده‌اند؛ ترتیبِ سریال می‌تواند با ترتیبِ واقعی فرق کند |
| چه چیزی را حل نمی‌کند |
مشکلاتِ چندشیء‌ای مثل write skew را حل نمی‌کند |
خواندنِ کهنه را ممنوع نمی‌کند؛ یک اجرای serializable می‌تواند داده‌ی قدیمی برگرداند |
| Linearizability | Serializability |
|---|
| About |
A recency guarantee for one object (register: one key, one row, one document) |
Transaction isolation level; each transaction may read and write many objects |
| Guarantees |
If operation A finishes before B starts, B must see A's state or newer |
Transactions look as if executed serially; the serial order may differ from real time |
| Does not fix |
Multi-object problems like write skew |
Does not forbid stale reads; a serializable execution may return old data |
ترکیبِ هر دو یعنی strict serializability (یا strong-1SR).
پایگاه‌داده‌های single-node معمولاً خطی‌پذیرند؛ اما در دنیای توزیع‌شده قضیه جالب می‌شود:
CockroachDB هم سریال‌پذیری می‌دهد و هم مقداری تضمینِ تازگی، اما نه strict serializability —
چون هماهنگیِ بینِ تراکنشی گران تمام می‌شود. در مقابل، Spanner و
FoundationDB strict serializability می‌دهند. و جالب اینکه می‌توانی سطحِ ایزوله‌سازی و مدلِ سازگاری را
تقریباً مستقل از هم انتخاب کنی.
Combining both gives strict serializability (or strong-1SR). Single-node databases are usually linearizable; in the distributed world it gets interesting: CockroachDB offers serializability plus some freshness, but not strict serializability — cross-transaction coordination is too costly. Spanner and FoundationDB do offer strict serializability. And you can pick isolation level and consistency model almost independently.
۱.۴. کجا واقعاً لازمش داریم؟1.4. Where do we really need it?
این تضمین وقتی اهمیت دارد که دیدنِ مقدار قدیمی یا تصمیمِ هم‌زمانِ ناسازگار، قانونِ برنامه را بشکند. نوع عملیات هم مهم است؛ خواندنِ تازه جای عملیاتِ شرطیِ اتمیک را نمی‌گیرد.
مثال فنی: رقابت برای نام کاربری
وضعیت اولیه: A و B هر دو می‌خواهند sara را ثبت کنند.
اجرای مرحله‌به‌مرحله: هر دو روی یک مرجع هماهنگ compare-and-set(empty, owner) یا درج با قید مناسب انجام می‌دهند؛ فقط یکی موفق می‌شود.
نتیجه و دلیل: خواندن «خالی است» و سپس نوشتن مستقل روی دو replica، یکتایی را تضمین نمی‌کند.
Watching a match score is not serious! But there are places where the system genuinely breaks without linearizability:
-
قفل و انتخابِ رهبر: سیستمِ تک‌رهبری باید مطمئن شود فقط یک رهبر دارد (نه split brain).
مکانیزمِ lease — هر نودی که lease بگیرد رهبر است — باید خطی‌پذیر باشد:
نباید ممکن باشد دو نود هم‌زمان lease بگیرند. سرویس‌هایی مثل ZooKeeper و
etcd دقیقاً برای همین ساخته شده‌اند.
Oracle RAC حتی برای هر صفحه‌ی دیسک قفلِ خطی‌پذیر دارد و برای همین شبکه‌ی اختصاصیِ بینِ نودها می‌سازد.
-
قیدهای uniqueness: نامِ کاربری یکتا، مسیرِ فایل یکتا، موجودیِ منفی‌نشدنیِ حساب، فروشِ بیش از موجودیِ انبار،
رزروِ هم‌زمانِ یک صندلی. اگر بخواهی این قید هنگامِ نوشته‌شدن اعمال شود (یکی از دو نفرِ هم‌زمان خطا بگیرد)،
به خطی‌پذیری نیاز داری — درست مثلِ قفل: «ثبتِ نامِ کاربری» یعنی گرفتنِ قفلِ آن نام، یعنی یک CAS.
البته قیدِ نرم (مثلاً overbooking پرواز و جبران با غرامت) می‌تواند خطی‌پذیر نباشد؛
ولی قیدِ سختِ کلاسیکِ پایگاه‌داده‌های رابطه‌ای حتماً خطی‌پذیری می‌خواهد.
-
وابستگیِ زمانیِ کانال‌های موازی: وقتی دو مسیرِ ارتباطیِ متفاوت بینِ دو سیستم باشد،
سریع‌تر بودنِ یکی از دیگری یعنی مسابقه. این همان چیزی است که در نمودار ۲ می‌بینیم.
-
Locks and leader election: a single-leader system must have exactly one leader (no split brain).
The lease mechanism — whoever holds the lease is leader — must be linearizable:
two nodes must never hold the lease at once. Services like ZooKeeper and
etcd exist precisely for this.
Oracle RAC even holds a linearizable lock per disk page, which is why it builds a dedicated interconnect between nodes.
-
Uniqueness constraints: unique usernames, unique file paths, never-negative balances, no overselling inventory,
no double-booked seat. To enforce the constraint at write time (one of two concurrent writers errors out),
you need linearizability — just like a lock: “registering a username” means taking the lock on that name, i.e. one CAS.
A soft constraint (e.g. flight overbooking compensated later) may skip linearizability;
but the classic hard relational constraint always needs it.
-
Timing across parallel channels: when two different communication paths link the same two systems,
one being faster than the other means a race. That is exactly what Diagram 2 shows.
روایت مدرس — نمودار ۲ را با صدای بلند بخوانیمTeacher narration
مثال فنی برای خواندنِ نمودار: رقابت برای نام کاربری
وضعیت اولیه: A و B هر دو می‌خواهند sara را ثبت کنند.
اجرای مرحله‌به‌مرحله: هر دو روی یک مرجع هماهنگ compare-and-set(empty, owner) یا درج با قید مناسب انجام می‌دهند؛ فقط یکی موفق می‌شود.
نتیجه و دلیل: خواندن «خالی است» و سپس نوشتن مستقل روی دو replica، یکتایی را تضمین نمی‌کند.
این یک sequence است: پنج شرکت‌کننده از چپ به راست ردیف شده‌اند —
Web App (مرورگرِ کاربر)، Web Server (هندلرِ آپلود)،
File Storage که زیرش نوشته «replicated, lagging»، Message Queue
با برچسبِ «async channel»، و Video Transcoder کارگرِ پس‌زمینه.
بالای نمودار سه فاز می‌بینی: Store original، Queue job و Race outcome.
فازِ اول: فلشِ upload video از اپ به سرور می‌رود، بعد write video file
از سرور به storage، و پاسخِ write ack (replica lagging) برمی‌گردد — یعنی ذخیره تأیید شده
ولی replication داخلی هنوز در راه است. فازِ دوم: چون ویدیو برای صف بزرگ است، فقط «دستور» از صف می‌گذرد:
enqueue transcode job (file ref) و بعد deliver job
(هر دو خطِ خط‌چینِ asyncاند).
فازِ سوم مسابقه را لو می‌دهد: transcoder با fetch original video می‌رود سراغِ storage
و جوابِ صورتیِ stale version or missing می‌گیرد — چون مراحلِ ۳ و ۴ از replicationِ کُندِ storage جلو زدند.
نتیجه هم پایین نوشته شده: write transcoded copy of OLD video و کارتِ هشدار:
نسخه‌ی اصلی و نسخه‌ی ترنسکدشده برای همیشه ناسازگار می‌مانند.
درسِ نمودار در کارتِ آخر است: دو کانالِ ارتباطی بینِ یک جفت سیستم = مسابقه؛
مگر آنکه storage خطی‌پذیر باشد یا کانالِ اضافی «read-your-owns-writes» را تضمین کند.
این دقیقاً همان وضعیتِ دو نفرِ بندِ قبل است: آنجا هم کانالِ دوم، صدایِ نفرِ اول بود.
This is a sequence diagram with five participants left to right — Web App (the user's browser), Web Server (upload handler), File Storage tagged “replicated, lagging”, the Message Queue tagged “async channel”, and the Video Transcoder background worker — in three phases: Store original, Queue job and Race outcome.
Phase one: upload video goes from app to server, then write video file from server to storage, and write ack (replica lagging) comes back — the write is acknowledged while internal replication is still in flight. Phase two: the video is too big for the queue, so only the “instruction” travels it — enqueue transcode job (file ref), then deliver job (both dashed async lines).
Phase three exposes the race: the transcoder's fetch original video hits storage and gets the pink stale version or missing — steps 3–4 overtook storage's slow replication. The result at the bottom: write transcoded copy of OLD video, and the warning card: original and transcoded copy stay inconsistent forever. The lesson in the last card: two channels between one pair of systems = a race, unless storage is linearizable or the extra channel guarantees read-your-own-writes — the same situation as the two match-watchers above, where the second channel was the first person's voice.
۱.۵. کدام روشِ replication خطی‌پذیر است؟1.5. Which replication method is linearizable?
نامِ روش تکثیر به‌تنهایی خطی‌پذیری را تعیین نمی‌کند. مسیر خواندن، تأیید نوشتن، انتخاب رهبر و جلوگیری از فعالیتِ رهبر قدیمی باید با هم تضمین را بسازند.
مثال فنی: رهبرِ هنوز معتبر؟
وضعیت اولیه: A قبلاً رهبر بوده، اما از اکثریت جدا شده و B رهبر تازه شده است.
اجرای مرحله‌به‌مرحله: خواندن محلیِ A می‌تواند قدیمی باشد؛ پروتکل باید اعتبار رهبری و رسیدن state به نقطهٔ لازم را پیش از پاسخ خطی‌پذیر بررسی کند.
نتیجه و دلیل: single-leader بودن اسمِ معماری است؛ خواندن از هر رهبرِ سابق بدون کنترل اعتبار خطی‌پذیر نمی‌شود.
The simplest route to linearizability is having literally one copy of the data — but then you have no fault tolerance. So revisit the Chapter 6 methods and ask which can be made linearizable:
| روش | خطی‌پذیر؟ | چرا |
|---|
| تک‌رهبری |
بالقوه بله |
تا وقتی همه‌ی خواندن‌ها و نوشتن‌ها از رهبر باشد و مطمئن باشی رهبر کیست. رهبرِ توهمی = نقضِ خطی‌پذیری؛
و با replication غیرهمگام، failover می‌تواند نوشته‌ی commitشده را از بین ببرد |
| الگوریتم‌های consensus |
بله (با دقت) |
تک‌رهبری با انتخابِ رهبرِ خودکار و جلوگیری از split brain — مثل Raft در etcd و Zab در ZooKeeper.
ولی خواندنِ بدونِ بررسیِ «هنوز رهبرم؟» می‌تواند کهنه باشد |
| چندرهبری |
خیر |
نوشتنِ هم‌زمان در چند نود + replication غیرهمگام = تعارض‌هایی که باید حل شوند |
| بدون‌رهبر (Dynamo-style) |
احتمالاً خیر |
ادعا می‌شود quorum (w + r > n) کافی است؛ نیست. LWW با ساعتِ دیواری تقریباً قطعاً غیرخطی‌پذیر است |
| Method | Linearizable? | Why |
|---|
| Single-leader |
Potentially yes |
As long as all reads and writes go to the leader and you are sure who the leader is. A delusional leader violates linearizability; and with async replication, failover can lose a committed write |
| Consensus algorithms |
Yes (carefully) |
Single-leader with automatic election and no split brain — Raft in etcd, Zab in ZooKeeper. But a read that never checks “am I still leader?” can be stale |
| Multi-leader |
No |
Concurrent writes on several nodes + async replication = conflicts to resolve |
| Leaderless (Dynamo-style) |
Probably not |
Quorum (w + r > n) is claimed to suffice; it doesn't. LWW on wall-clock time is almost certainly not linearizable |
برای ساختنِ خطی‌پذیریِ واقعی در Dynamo-style باید read repair را هم‌زمان (قبل از پاسخ) انجام دهی
و نویسنده قبل از نوشتن، بیشترین timestamp را از یک quorum بخواند. Riak به‌خاطرِ هزینه این کار را نمی‌کند؛
Cassandra read repair را انجام می‌دهد ولی با ساعتِ دیواری، خطی‌پذیری را از دست می‌دهد.
و نکته‌ی مهم: فقط خواندن/نوشتنِ خطی‌پذیر را می‌توان این‌طور ساخت؛ CAS خطی‌پذیر به consensus نیاز دارد.
For true linearizability in Dynamo-style stores you must do read repair synchronously (before responding), and writers must first read the highest timestamp from a quorum. Riak skips this for cost reasons; Cassandra does read repair but with wall-clock time, losing linearizability. And the key point: only linearizable reads/writes can be built this way; linearizable CAS needs consensus.
روایت مدرس — نمودار ۳ را با صدای بلند بخوانیمTeacher narration
مثال فنی برای خواندنِ نمودار: رهبرِ هنوز معتبر؟
وضعیت اولیه: A قبلاً رهبر بوده، اما از اکثریت جدا شده و B رهبر تازه شده است.
اجرای مرحله‌به‌مرحله: خواندن محلیِ A می‌تواند قدیمی باشد؛ پروتکل باید اعتبار رهبری و رسیدن state به نقطهٔ لازم را پیش از پاسخ خطی‌پذیر بررسی کند.
نتیجه و دلیل: single-leader بودن اسمِ معماری است؛ خواندن از هر رهبرِ سابق بدون کنترل اعتبار خطی‌پذیر نمی‌شود.
بالای نمودار، ردیفِ بنفشِ writer را می‌بینی با نوارِ
write(x, 1) → sent to all three replicas (w = 3).
زیرش سه خطِ افقیِ نودها هست: replica n1 و n2 و n3.
روی هر خط یک لوزیِ بنفش است با برچسبِ x = 1 arrives — و مهم اینجاست که این لوزی‌ها
در یک نقطه نیستند: n1 زودتر مقدارِ جدید را می‌گیرد، n2 و n3 خیلی دیرتر. کنارِ خطوط هم نوشته
«هر replica در لحظه‌ای متفاوت از ۰ به ۱ می‌پرَد — replication در پرواز است».
حالا دو کلاینت. client A نوارِ read r = 2 ⇒ 1 دارد و زیرش دو چیپ:
n1: 1 و n2: 0 — از دو نود خوانده، یکی جدید و یکی کهنه؛ چون خواندنش با نوشته مسابقه داشت، ۱ قبول است.
client B اما نوارِ صورتیِ read r = 2 ⇒ 0 — STALE دارد
با چیپ‌های n2: 0 و n3: 0: هر دو نود هنوز عقب‌اند.
فلشِ صورتیِ وسطِ صحنه حکم را صادر می‌کند: «B بعد از برگشتنِ A شروع کرد، ولی مقدارِ کهنه‌تر خواند».
یعنی با اینکه قاعده‌ی quorum برقرار است (w=3 و r=2، پس w + r > n)، اجرا هنوز خطی‌پذیر نیست.
جعبه‌ی پایین راه‌ها را می‌نویسد: read repair هم‌زمان قبل از پاسخ، خواندنِ بیشترین timestamp از quorum قبل از نوشتن،
و اینکه LWW با ساعتِ دیواری هرگز خطی‌پذیر نمی‌شود و CAS خطی‌پذیر به consensus نیاز دارد.
At the top, the purple writer row carries write(x, 1) → sent to all three replicas (w = 3). Below are the three node lines replica n1, n2 and n3, each with a purple diamond x = 1 arrives — and crucially the diamonds are not aligned: n1 gets the new value early, n2 and n3 much later. The note says it plainly: each replica flips from 0 to 1 at a different moment — replication is in flight.
Now the two clients. client A's bar read r = 2 ⇒ 1 carries two chips, n1: 1 and n2: 0 — it read one fresh and one stale node; since its read raced the write, 1 is acceptable. client B's pink bar read r = 2 ⇒ 0 — STALE carries n2: 0 and n3: 0: both nodes still behind.
The pink arrow across the scene delivers the verdict: “B started after A returned, yet read something older”. Quorum holds (w=3, r=2, so w + r > n) and the execution is still not linearizable. The bottom box lists the fixes: synchronous read repair before responding, reading the highest timestamp from a quorum before writing — plus that wall-clock LWW is never linearizable and linearizable CAS needs consensus.
۱.۶. هزینه‌ی خطی‌پذیری: CAP، PACELC و سقفِ تأخیر1.6. The cost of linearizability: CAP, PACELC and the latency floor
هنگام قطع ارتباط، هماهنگ کردنِ نسخه‌ها ممکن است با پاسخ‌گوییِ همهٔ گره‌ها ناسازگار شود. حتی بدون قطعی هم هماهنگیِ راه‌دور تأخیر دارد؛ CAP و PACELC این هزینه‌ها را از دو زاویه بیان می‌کنند.
مثال فنی: بهای قطع ارتباط
وضعیت اولیه: دو مرکز داده ارتباطشان قطع شده و هر دو درخواستِ تغییر یک نام یکتا را دارند.
اجرای مرحله‌به‌مرحله: اگر هر دو مستقل موفقیت بدهند، یکتایی می‌شکند؛ مسیرِ نیازمند تصمیم واحد در بخشی از شبکه باید منتظر بماند یا خطا بدهد.
نتیجه و دلیل: CAP این انتخاب هنگام partition را توصیف می‌کند؛ در حالت سالم هم هماهنگیِ دوردست هزینهٔ تأخیر دارد.
Imagine two regions with the link between them cut (each region internally healthy). With multi-leader, each region works independently and writes sync up later. With single-leader, the leader sits in one region; the other can neither write nor take a linearizable read — unavailable for those users. This is not multi-region specific: any network fault at any scale forces the same choice.
CAP، درست فهمیده‌شدهCAP, properly understood
«سه‌تایی، دوتایش را بردار» گمراه‌کننده است: partition یک خطا است، نه یک انتخاب؛ نمی‌توانی انتخابش نکنی.
تنها راهِ «بدونِ partition» این است که شبکه نداشته باشی (یک نود) — که آن‌وقت دیگر در دسترسیِ بالا هم نداری.
فرمولِ بهتر: هنگامِ partition یا سازگار باش یا در دسترس (CP یا AP). وقتی شبکه سالم است، هر دو را می‌توانی داشت.
تعریفِ رسمیِ CAP هم خیلی محدود است: فقط linearizability و فقط partition — آن هم کمتر از ۸٪ِ حوادثِ گوگل.
تعمیمش یعنی PACELC: هنگامِ partition بینِ A و C، وگرنه (else) بینِ تأخیرِ کم (L) و C انتخاب کن.
امروزه CAP بیشتر ارزشِ تاریخی دارد و با نتایجِ دقیق‌تر جایگزین شده است.
“Pick two of three” is misleading: a partition is a fault, not a choice; you cannot opt out of it. The only “partition-free” setup is having no network (one node) — which also means no high availability. The better formula: during a partition, be consistent or available (CP or AP). With a healthy network you can have both. The formal CAP definition is also very narrow: only linearizability and only partitions — under 8% of Google's incidents. Its generalization is PACELC: during a partition choose between A and C, else choose between low latency (L) and C. Today CAP is mostly of historical value, superseded by sharper results.
نکته‌ی غافلگیرکننده‌ی پایانی: خطی‌پذیری حتی در یک کامپیوتر هم کمیاب است!
حافظه‌ی RAM روی CPU چندهسته‌ای خطی‌پذیر نیست — به‌خاطرِ cache و store buffer هر هسته —
مگر با memory barrier. آنجا دلیل، عملکرد است نه تحملِ خرابی؛
و در پایگاه‌داده‌های توزیع‌شده هم بیشترِ دلایلِ کنارگذاشتنِ خطی‌پذیری، عملکرد است.
و سرانجام یک اثباتِ مهم (Attiya & Welch): پاسخ‌زمانیِ خواندن/نوشتنِ خطی‌پذیر
دست‌کم متناسب با عدم قطعیتِ تأخیرِ شبکه است. در شبکه‌ای با تأخیرِ متغیر (یعنی همه‌ی شبکه‌ها)،
خطی‌پذیری ناگزیر کُند است؛ الگوریتمِ سریع‌ترِ خطی‌پذیر وجود ندارد — فقط مدل‌های ضعیف‌تر می‌توانند سریع باشند.
The surprising footnote: linearizability is rare even inside one computer! RAM on a multi-core CPU is not linearizable — each core's cache and store buffer see to that — except behind a memory barrier. There the motive is performance, not fault tolerance; and in distributed databases most reasons for dropping linearizability are likewise performance. Finally an important proof (Attiya & Welch): linearizable read/write latency is at least proportional to network delay uncertainty. On a variable-latency network (i.e. all networks), linearizability is unavoidably slow; a faster linearizable algorithm does not exist — only weaker models can be fast.
مفهوم مکمل — بهای خطی‌پذیری در یک نگاهExtra concept — the price of linearizability at a glance
روایت مدرس از نمودارTeacher narration
مثال فنی برای خواندنِ نمودار: بهای قطع ارتباط
وضعیت اولیه: دو مرکز داده ارتباطشان قطع شده و هر دو درخواستِ تغییر یک نام یکتا را دارند.
اجرای مرحله‌به‌مرحله: اگر هر دو مستقل موفقیت بدهند، یکتایی می‌شکند؛ مسیرِ نیازمند تصمیم واحد در بخشی از شبکه باید منتظر بماند یا خطا بدهد.
نتیجه و دلیل: CAP این انتخاب هنگام partition را توصیف می‌کند؛ در حالت سالم هم هماهنگیِ دوردست هزینهٔ تأخیر دارد.
نمودار سه وضعیت را کنار هم می‌گذارد: شبکه سالم (هم سازگار و هم در دسترس — انتخابی لازم نیست)، پارتیشن (خطا، نه انتخاب: یا CP یا AP)، و حالت سالمِ PACELC (تأخیر کم یا سازگاری — سریع یا تازه، هرگز هر دو). نوار پایین سقف را می‌گذارد: پاسخ‌زمانی خطی‌پذیر دست‌کم به‌اندازه عدم قطعیت تأخیر شبکه است و الگوریتم سریع‌تری وجود ندارد.
The diagram lays three situations side by side: a healthy network (consistent and available — no choice needed), a partition (a fault, not a choice: CP or AP), and the healthy PACELC case (low latency or consistency — fast or fresh, never both). The bottom strip sets the floor: linearizable latency is at least the network's delay uncertainty, and no faster algorithm exists.
۲2 مولد‌های شناسه و ساعت‌های منطقیID generators and logical clocks
۲.۱. شمارنده‌ی single-node و محدودیت‌هایش2.1. The single-node counter and its limits
شمارندهٔ یک گره شناسه‌های افزایشی می‌دهد، اما ظرفیت و دسترس‌پذیری به همان مسیر وابسته است. ترتیبِ گرفتن شناسه نیز الزاماً ترتیبِ تأییدِ تراکنش‌ها نیست.
مثال فنی: شمارندهٔ یکتا روی یک نود
وضعیت اولیه: سرور اعداد 100,101,102 را به‌ترتیب تخصیص می‌دهد.
اجرای مرحله‌به‌مرحله: از دست رفتن نود، بدون ذخیرهٔ پایدار و بازیابیِ درست، خطر تکرار یا توقف می‌سازد؛ صف درخواست‌ها هم ظرفیت همان مسیر را محدود می‌کند.
نتیجه و دلیل: شمارنده ساده است، اما دوام، failover و throughput آن نیاز به طراحی دارند؛ یکتا بودن با بدون‌وقفه بودن یکسان نیست.
In a single-node database, the auto-increment ID is both compact (64 bits) and preserves record-creation order: sort chat messages by ID and the conversation comes out right. The generator is really a linearizable system: each ID request is one atomic fetch-and-add. But it has three problems: it is a single point of failure, fetching an ID from another region means a round trip across the planet, and it bottlenecks under high write throughput. (Plus you must persist the counter so a restart never reissues an ID.)
۲.۲. طرح‌های توزیع‌شده‌ی شناسه2.2. Distributed ID schemes
شناسهٔ توزیع‌شده می‌تواند با تصادف، ترکیبِ زمان و شناسهٔ گره یا واگذاری بازه ساخته شود. احتمال یکتایی، ترتیب و وابستگی به ساعت در این روش‌ها یکسان نیست.
مثال فنی: یکتا لزوماً مرتب نیست
وضعیت اولیه: دو نود بازه‌های 1…1000 و 1001…2000 را گرفته‌اند.
اجرای مرحله‌به‌مرحله: نود دوم ممکن است زودتر ۱۰۰۱ بدهد و نود اول بعداً ۱ بدهد؛ شناسه‌ها هنوز یکتایند.
نتیجه و دلیل: بلوک‌گذاری هماهنگیِ هر تخصیص را کم می‌کند، ولی ترتیبِ عددیِ شناسه دیگر ترتیب زمان واقعیِ درخواست‌ها نیست.
Five alternative families exist. All give uniqueness; they differ in ordering and linearizability.
روایت مدرس — نمودار ۴ را با صدای بلند بخوانیمTeacher narration
مثال فنی برای خواندنِ نمودار: یکتا لزوماً مرتب نیست
وضعیت اولیه: دو نود بازه‌های 1…1000 و 1001…2000 را گرفته‌اند.
اجرای مرحله‌به‌مرحله: نود دوم ممکن است زودتر ۱۰۰۱ بدهد و نود اول بعداً ۱ بدهد؛ شناسه‌ها هنوز یکتایند.
نتیجه و دلیل: بلوک‌گذاری هماهنگیِ هر تخصیص را کم می‌کند، ولی ترتیبِ عددیِ شناسه دیگر ترتیب زمان واقعیِ درخواست‌ها نیست.
نمودار سه ستون دارد. ستونِ اول با عنوانِ «① Single node» دو کارت دارد:
Autoincrement counter (یکتا + ترتیبِ کامل + خطی‌پذیر، ولی SPOF و گلوگاه) و
Timestamp oracle که زیرش چند خط توضیح است: یک شمارنده با replication،
پایدارکردنِ دسته‌ای از شناسه‌ها و تحویلِ ترتیبی‌شان — اگر نود بمیرد شناسه‌ها جا می‌افتند ولی هرگز تکرار نمی‌شوند؛
و قابلِ shard کردن نیست و همه‌ی مناطق باید از یک نود بپرسند. چیپِ زردِ پایینِ ستون جمع می‌کند: «خطی‌پذیر ✓».
ستونِ دوم «② Distributed generators» است: Sharded counters (یکتا، ولی ترتیب بینِ شاردها گم می‌شود؛
«شناسه‌ی ۱۶ و ۱۷، کدام زودتر؟»)، Preallocated blocks (نود A بازه‌ی ۱ تا ۱۰۰۰ و نود B بازه‌ی ۱۰۰۱ تا ۲۰۰۰؛
یک نوشته‌ی دیرتر می‌تواند شناسه‌ی کوچک‌تر بگیرد)، Random UUID v4 (۱۲۸ بیت، محلی، بدونِ تماس؛ ولی ترتیب تصادفی است)،
و Wall-clock + sequence که مثال‌هایش UUIDv7 / ULID / Snowflake است:
تقریباً ترتیبِ زمانِ واقعی، ولی skew و جهشِ ساعت می‌تواند ترتیب را برعکس کند — پس «تقریباً قطعاً غیرخطی‌پذیر».
ستونِ سوم «③ Logical clocks» است و سه کارت: Lamport clock که جفتِ (counter, nodeID) می‌دهد،
قاعده‌اش counter := max(local, seen) + 1 است و ترتیبِ کاملِ سازگار با علّیت می‌سازد
(ولی مفهومِ زمانِ فیزیکی ندارد و خطی‌پذیر نیست)؛ Hybrid logical clock که زمانِ فیزیکی را با همان قاعده ترکیب می‌کند
و حتی با جهشِ NTP هم فقط جلو می‌رود؛ و Vector clocks که به‌ازای هر نود یک شمارنده نگه می‌دارد و
«هم‌زمان» را از «بعدی» تشخیص می‌دهد، به قیمتِ اندازه‌ی بزرگ. چیپِ زرد: «ترتیبِ علّی ✓ · تازگیِ خطی‌پذیر ✗».
و نوارِ پایینِ نمودار، پلِ بخشِ بعد را می‌زند: «ترتیب‌دادن، تصمیم‌گرفتن نیست» —
برای اجرای یک قید، برنده باید بداند کوچک‌ترین timestamp را دارد، که یعنی شنیدن از همه‌ی نودها؛
یک نودِ ناقص کلِ تصمیم را فلج می‌کند. تصمیمِ مقاوم‌دربرابرِ خرابی یعنی consensus.
The diagram has three columns. Column one, “① Single node”, holds two cards: Autoincrement counter (unique + total order + linearizable, but SPOF and bottleneck) and Timestamp oracle — a replicated counter that persists a batch of IDs and hands them out in order: if the node dies, IDs are skipped but never duplicated; it cannot be sharded and every region must ask one node. The yellow chip at the column's foot sums up: “linearizable ✓”.
Column two, “② Distributed generators”: Sharded counters (unique, but cross-shard order is lost — “ID 16 vs 17, which came first?”), Preallocated blocks (node A owns 1–1000, node B 1001–2000; a later write can get a smaller ID), Random UUID v4 (128 bits, local, contact-free, but randomly ordered), and Wall-clock + sequence — UUIDv7 / ULID / Snowflake: roughly real-time ordered, but skew and clock jumps can invert the order — hence “almost certainly not linearizable”.
Column three, “③ Logical clocks”, holds three cards: the Lamport clock emitting (counter, nodeID) pairs under the rule counter := max(local, seen) + 1, building a causal total order (but with no physical-time meaning and no linearizability); the Hybrid logical clock blending physical time with the same rule so it only moves forward even across NTP jumps; and Vector clocks keeping one counter per node to tell “concurrent” apart from “after”, at the price of size. Yellow chip: “causal order ✓ · linearizable freshness ✗”. The bottom strip bridges to the next section: “ordering is not deciding” — to enforce a constraint the winner must know it holds the smallest timestamp, i.e. hear from every node; one broken node paralyzes the whole decision. Fault-tolerant deciding means consensus.
۲.۳. ساعتِ منطقی: Lamport و HLC2.3. Logical clocks: Lamport and HLC
ساعت Lamport وابستگیِ رویدادها را با شمارنده دنبال می‌کند: علت، عدد کوچک‌تری از معلول می‌گیرد. عکسِ این گزاره درست نیست. HLC اطلاعات منطقی را با زمان فیزیکی ترکیب می‌کند.
مثال فنی: Lamport روی ارسال پیام
وضعیت اولیه: شمارندهٔ A برابر ۵ است و پیام با برچسب ۶ می‌فرستد؛ B در عدد ۳ است.
اجرای مرحله‌به‌مرحله: B هنگام دریافت مقدار را به max(3,6)+1=7 می‌رساند. HLC همین ایدهٔ ترتیب را با مؤلفهٔ زمان فیزیکی ترکیب می‌کند.
نتیجه و دلیل: اگر a علت b باشد برچسب a کوچک‌تر است؛ کوچک‌تر بودن برچسب به‌تنهایی اثبات نمی‌کند a علت b بوده است.
Unlike a physical clock, a logical clock is an event-counting algorithm: its number never says “what time is it”, but comparing two numbers says which came first. We want three things from a logical clock: compact unique timestamps; comparability (total order); and an order consistent with causality (if A happened before B, A's timestamp is smaller).
ساعتِ Lamport (۱۹۷۸) ساده است: هر نود یک شمارنده دارد؛ هنگامِ تولیدِ رویداد یکی زیادش می‌کند؛
هر وقت timestamp بزرگ‌تری از نودِ دیگر دید، شمارنده‌اش را به آن می‌رساند.
timestamp جفتِ (counter, nodeID) است تا حتی با برابریِ شمارنده هم یکتا بماند.
مقایسه: اول شمارنده، بعد شناسه‌ی نود. نتیجه یک ترتیبِ کاملِ سازگار با علّیت است — اما خطی‌پذیر نیست:
فقط تضمین می‌کند هر رویدادی از هر چیزی که دیده بزرگ‌تر باشد، نه اینکه «تازه» باشد.
The Lamport clock (1978) is simple: each node keeps a counter; it increments on every local event; whenever it sees a larger timestamp from another node, it catches up to it. The timestamp is the pair (counter, nodeID) so it stays unique even on counter ties. Comparison: counter first, node ID second. The result is a causal total order — but not linearizable: it only guarantees each event exceeds everything it has seen, not that it is “fresh”.
روایت مدرس — نمودار ۵ را با صدای بلند بخوانیمTeacher narration
مثال فنی برای خواندنِ نمودار: Lamport روی ارسال پیام
وضعیت اولیه: شمارندهٔ A برابر ۵ است و پیام با برچسب ۶ می‌فرستد؛ B در عدد ۳ است.
اجرای مرحله‌به‌مرحله: B هنگام دریافت مقدار را به max(3,6)+1=7 می‌رساند. HLC همین ایدهٔ ترتیب را با مؤلفهٔ زمان فیزیکی ترکیب می‌کند.
نتیجه و دلیل: اگر a علت b باشد برچسب a کوچک‌تر است؛ کوچک‌تر بودن برچسب به‌تنهایی اثبات نمی‌کند a علت b بوده است.
سه شرکت‌کننده داریم: User A و User B و User C
و زیرِ هر سه نوشته «chat node, counter starts at 0» — هر کدام یک نودِ ساعتِ Lamport با شمارنده‌ی صفر.
نمودار دو فاز دارد: «پست‌های هم‌زمان (A و C همدیگر را ندیده‌اند)» و «B شمارنده‌ها را ادغام می‌کند و جواب می‌دهد».
در فازِ اول دو فلشِ مستقل می‌بینی: از A به B با برچسبِ msg ts=(1,A) و از C به B با
msg ts=(1,C). یادداشتِ کنارِ هر فلش حسابِ شمارنده را نشان می‌دهد:
«A: counter 0→1 = ts (1,A)؛ B می‌پذیرد max(0,1)=1» و برای C همین‌طور — هر دو بدونِ اطلاع از هم، شمارنده‌شان را به ۱ رسانده‌اند.
پس دو timestamp با شمارنده‌ی برابر داریم که با شناسه‌ی نود از هم جدا می‌شوند.
در فازِ دوم، B که حالا هر دو پیام را دیده شمارنده‌اش ۱ است؛ فلشِ reply ts=(2,B) از B به A می‌رود
و یادداشتش می‌گوید «B: counter 1→2 = ts (2,B)؛ A می‌پذیرد max(1,2)=2». حالا ترتیبِ نهایی را ببین:
(1,A) < (1,C) < (2,B) — اول شمارنده، بعد شناسه‌ی نود. هر رویدادی که علّیاً قبل از دیگری است،
timestamp کوچک‌تری هم دارد. محدودیت هم همان‌جاست: رویدادهای «واقعاً هم‌زمان» با رویدادهای «مرتب ولی بی‌ارتباط» قابل‌تشخیص نیستند؛
برای آن باید سراغِ vector clock بروی.
Three participants — User A, User B and User C — each a Lamport node starting at counter 0 (“chat node, counter starts at 0”), in two phases: concurrent posts (A and C haven't seen each other) and B merging the counters and replying. Phase one shows two independent arrows: A→B labelled msg ts=(1,A) and C→B labelled msg ts=(1,C), each with its counter math (“A: counter 0→1 = ts (1,A); B adopts max(0,1)=1”, same for C) — two equal-counter timestamps disambiguated by node ID.
In phase two B, having seen both messages at counter 1, sends reply ts=(2,B) to A (“B: counter 1→2 = ts (2,B); A adopts max(1,2)=2”). The final order: (1,A) < (1,C) < (2,B) — counter first, node ID second. Every causally-earlier event sorts smaller. The limit sits right there: “truly concurrent” events are indistinguishable from “ordered but unrelated” ones; for that you need a vector clock.
ساعتِ Lamport دو محدودیت دارد: هیچ ربطی به زمانِ فیزیکی ندارد (پس «پیام‌های امروز» را نمی‌توانی با آن فیلتر کنی)،
و اگر دو نود هرگز با هم حرف نزنند، شمارنده‌هایشان می‌تواند وحشتناک فاصله بگیرد.
ساعتِ منطقیِ هیبریدی (HLC) ترکیبِ هر دو است: مثلِ ساعتِ دیواری ثانیه می‌شمارد،
ولی مثلِ Lamport وقتی timestampِ بزرگ‌تری دید جلو می‌رود؛ و در هر تولیدِ timestamp یکی هم اضافه می‌کند
تا حتی با جهشِ رو‌به‌عقبِ NTP فقط جلو برود (یعنی ممکن است کمی از ساعتِ فیزیکی جلوتر باشد).
نتیجه: timestampی که تقریباً مثلِ ساعتِ دیواری استفاده می‌شود، با ترتیبِ سازگار با علّیت —
بدونِ سخت‌افزارِ خاص و فقط با ساعتِ تقریباً همگام. CockroachDB از HLC استفاده می‌کند.
The Lamport clock has two limits: no relation to physical time (so you cannot filter “today's messages” with it), and counters can drift wildly apart if two nodes never talk. The hybrid logical clock (HLC) blends both: it ticks like wall-clock time but jumps forward Lamport-style on seeing a larger timestamp; and it adds one on every timestamp it mints, so even a backward NTP jump only moves it forward (possibly slightly ahead of physical time). The result: a timestamp usable almost like wall-clock time, with causal order — no special hardware, just roughly-synchronized clocks. CockroachDB uses HLC.
Lamport/HLC در برابر vector clockLamport/HLC vs vector clocks
Lamport و HLC برای تولیدِ transaction ID در MVCC عالی‌اند (اسنپ‌شات با علّیت سازگار می‌ماند).
اما وقتی دو timestamp متفاوت می‌بینی، نمی‌توانی بفهمی «هم‌زمان بودند» یا «یکی قبل از دیگری».
Vector clock همین را می‌گوید: به‌ازای هر نود یک شمارنده؛ اگر A در یک نود بزرگ‌تر و B در نودِ دیگر بزرگ‌تر باشد،
یعنی هم‌زمان بوده‌اند. قیمتش اندازه‌ی timestamp است: یک عدد به‌ازای هر نودِ سیستم.
Lamport and HLC are perfect for minting transaction IDs in MVCC (snapshots stay causally consistent). But seeing two different timestamps, you cannot tell “concurrent” from “one before the other”. The vector clock answers exactly that: one counter per node; if A is bigger on one node and B on another, they were concurrent. Its price is timestamp size: one number per node in the system.
۲.۴. مولدِ شناسه‌ی خطی‌پذیر و چراییِ consensus2.4. The linearizable ID oracle and why consensus
مولدِ شناسهٔ خطی‌پذیر باید ترتیبِ پایان و شروعِ درخواست‌ها را در زمان واقعی رعایت کند. برای حفظ این تضمین هنگام خرابی، صرف یک شمارندهٔ محلی در هر گره کافی نیست.
مثال فنی: مولدِ مرتبِ سراسری
وضعیت اولیه: درخواست اول شناسهٔ ۱۰۷ گرفته و پاسخ آن کامل شده؛ درخواست دوم بعداً آغاز می‌شود.
اجرای مرحله‌به‌مرحله: قراردادِ خطی‌پذیر باید به دومی شناسهٔ بزرگ‌تر بدهد؛ چند نود مستقل با بازه‌های آزاد این شرط را خودکار حفظ نمی‌کنند.
نتیجه و دلیل: برای این تضمین، هماهنگیِ ترتیب تخصیص لازم است؛ UUID صرفاً مسئلهٔ یکتایی را هدف می‌گیرد.
Why isn't Lamport enough? Because linearizability demands a real-time rule: if A's work finished and B's started after, B must get the bigger ID — even if the two nodes never spoke. The book's example: a user first makes their account private, then posts a photo from a laptop; but photo and settings live on different shards and the photo shard's counter lags. Result: the photo gets the smaller timestamp, and in MVCC a viewer whose timestamp falls between the two still sees the account as “public” alongside the private photo! The simple fix: a linearizable ID oracle.
ساده‌ترین پیاده‌سازی همان «تک‌نودِ مطمئن» است: شمارنده‌ی اتمی + پایدارسازی + replication تک‌رهبری.
در عمل به آن timestamp oracle می‌گویند (الگوی Percolator در TiKV).
بهینه‌سازی: به‌جای هر درخواست، یک دسته از شناسه‌ها را پایدار و replicate کن و یکی‌یکی تحویل بده —
بعد از crash شناسه‌ها جا می‌افتند ولی تکراری یا وارونه صادر نمی‌شود. نمی‌توانی این مولد را shard کنی
(ترتیبِ خطی‌پذیر از بین می‌رود) و نمی‌توانی بینِ مناطق پخشش کنی — ولی کارش آن‌قدر ساده است که یک نود بارِ زیادی برمی‌دارد.
جایگزینِ بدونِ ارتباط: روشِ Spanner — ساعتِ فیزیکی که به‌جای عدد بازه‌ی عدم قطعیت می‌دهد
و سیستم به اندازه‌ی عرضِ بازه صبر می‌کند. نیازمندِ سخت‌افزار/نرم‌افزارِ ساعتِ دقیق است.
The simplest implementation is the same “reliable single node”: atomic counter + persistence + single-leader replication. In practice it is called a timestamp oracle (the Percolator pattern in TiKV). The optimization: persist and replicate a batch of IDs per request and hand them out one by one — after a crash IDs are skipped but never duplicated or inverted. You cannot shard this oracle (linearizable order would die) nor spread it across regions — but its job is so simple one node carries heavy load. The contact-free alternative is Spanner's approach — a physical clock emitting an uncertainty interval instead of a number, with the system waiting out the interval's width. It needs precise-clock hardware/software.
آخرین پل: ساعتِ منطقی برای قیدها کافی نیستFinal bridge: logical clocks are not enough for constraints
برای قفل یا نامِ کاربری، با ساعتِ منطقی می‌توانی به درخواست‌ها timestamp بدهی و «کوچک‌ترین» را برنده اعلام کنی.
ولی نودِ برنده چطور می‌فهمد کوچک‌ترین را دارد؟ باید از هر نودِ دیگری که ممکن است timestamp صادر کرده باشد بشنود.
اگر یکی از آن‌ها ناقص یا غیرقابل‌دسترس باشد، کلِ سیستم می‌ایستد — یعنی تحملِ خرابی نداریم.
برای قفل‌ها و leaseهای مقاوم‌دربرابرِ خرابی به چیزی قوی‌تر از ساعت نیاز داریم: consensus.
For a lock or a username, logical clocks can timestamp requests and declare the “smallest” the winner. But how does the winning node know it holds the smallest? It must hear from every other node that might have issued a timestamp. If one of them is broken or unreachable, the whole system halts — no fault tolerance. For crash-resilient locks and leases you need something stronger than clocks: consensus.
۳3 اجماع (Consensus)Consensus
۳.۱. یک مسئله، چند شکل3.1. One problem, many faces
اجماع یعنی گره‌ها با وجود بعضی خرابی‌ها بر یک تصمیم معتبر توافق کنند. انتخاب رهبر، ثبت ترتیبِ مشترک و بعضی عملیاتِ شرطی، شکل‌های مرتبطِ نیاز به توافق‌اند.
مثال فنی: یک تصمیم با چند اسم
وضعیت اولیه: سه نود باید معلوم کنند چه کسی مالک job J7 است.
اجرای مرحله‌به‌مرحله: انتخاب رهبر، درج مالک در لاگ توافق‌شده و اعمال همان تصمیم به state هر نود، شکل‌های مرتبط این مسئله‌اند.
نتیجه و دلیل: پذیرفتن مالک متفاوت در هر نود با نام «اجماع» سازگار نیست؛ پروتکل باید یک تصمیم معتبر مشترک بدهد.
The three examples of this chapter — split-brain-free leader election, a crash-resilient ID oracle, and failure-resilient CAS — are all one problem: consensus, getting several nodes to agree on one value. It is among the most fundamental and hardest problems in distributed computing, and many systems have implemented it wrongly through history. The famous algorithms: Viewstamped Replication, Paxos, Raft and Zab. All work in the non-Byzantine model (messages may arrive late or vanish, nodes may die, but nobody lies). Byzantine algorithms (assuming fewer than a third of nodes hostile) belong to blockchains and multi-party settings.
نتیجه‌ی FLP: پس چطور ممکن است؟The FLP result: so how is it possible?
نتیجه‌ی معروفِ FLP (Fischer–Lynch–Paterson) می‌گوید: اگر خطرِ crash یک نود وجود داشته باشد،
هیچ الگوریتمی نمی‌تواند همیشه به consensus برسد. اما دو نکته قضیه را عملی می‌کند:
اول اینکه FLP فقط می‌گوید نمی‌توان پایان (termination) را تضمین کرد، نه اینکه consensus ناممکن است؛
دوم اینکه اثبات برای الگوریتمِ قطعی در مدلِ ناهمگام است — یعنی بدونِ هیچ timeout یا شانسی.
اگر اجازه بدهی الگوریتم با timeout حدس بزند نودی مرده (حتی گاهی اشتباه)، یا فقط از تصادفی‌بودن استفاده کند، consensus حل می‌شود.
The famous FLP result (Fischer–Lynch–Paterson) says: if any node may crash, no algorithm can always reach consensus. But two caveats make it practical: FLP only says termination cannot be guaranteed, not that consensus is impossible; and the proof covers deterministic algorithms in the asynchronous model — i.e. with no timeouts or luck. Let the algorithm guess node death via timeout (sometimes wrongly), or use randomness, and consensus is solvable.
۳.۲. چهره‌های مختلف consensus و خواص چهارگانه3.2. The many faces of consensus and the four properties
در اجماع، توافق بر نتیجه، معتبر بودن پیشنهاد، تغییر نکردنِ تصمیم نهایی و رسیدن به تصمیم تحت شرایط لازم اهمیت دارند. شرایطِ پیشرفت به مدلِ خرابی و شبکه وابسته است.
مثال فنی: تصمیم مشترکِ معتبر
وضعیت اولیه: سه رأی‌دهنده پیشنهادهای A و B را برای رهبر دارند.
اجرای مرحله‌به‌مرحله: تصمیم نهایی باید از پیشنهاد معتبر باشد، نودها تصمیم ناسازگار ندهند و تحت فرض‌های پیشرفت بالاخره تصمیم گرفته شود.
نتیجه و دلیل: خواص agreement، validity، integrity و termination با هم قرارداد می‌سازند؛ داشتن پیام رأی به‌تنهایی کافی نیست.
Consensus wears many faces: agreement on one value (like atomic CAS), building an append-only log (called total order broadcast), the fetch-and-add operation, and atomic commitment of a distributed transaction. The deep point: they are all equivalent — a solution to one converts into a solution to the rest.
روایت مدرس — نمودار ۶ را با صدای بلند بخوانیمTeacher narration
مثال فنی برای خواندنِ نمودار: تصمیم مشترکِ معتبر
وضعیت اولیه: سه رأی‌دهنده پیشنهادهای A و B را برای رهبر دارند.
اجرای مرحله‌به‌مرحله: تصمیم نهایی باید از پیشنهاد معتبر باشد، نودها تصمیم ناسازگار ندهند و تحت فرض‌های پیشرفت بالاخره تصمیم گرفته شود.
نتیجه و دلیل: خواص agreement، validity، integrity و termination با هم قرارداد می‌سازند؛ داشتن پیام رأی به‌تنهایی کافی نیست.
این نمودارِ ساختاری، یک قلب و چند بازو دارد. قلب، جعبه‌ی بزرگِ وسط است با عنوانِ
CONSENSUS و دو زیرنویس: «یک مقدارِ توافق‌شده، یک ترتیبِ توافق‌شده» و
«safety همیشه، liveness با اکثریت».
ردیفِ بالا سه جعبه دارد که هر کدام با فلشِ سبز و برچسبِ «≡ equivalent» به قلب وصل‌اند:
Single-value consensus (نودها مقدار پیشنهاد می‌کنند، یکی انتخاب می‌شود — انتخابِ رهبر، ادعای lease،
ثبتِ نامِ کاربری)، Shared log / total order broadcast (افزودنِ entry به یک ترتیبِ واحد،
با «consensus number ∞» — شکلی که بیشترِ سیستم‌ها واقعاً عرضه می‌کنند) و Linearizable CAS
(مقایسه-و-تنظیم روی یک register، برای قفل و قیدِ uniqueness).
ردیفِ وسط دو جعبه‌ی دیگر را کنارِ قلب می‌گذارد: Atomic commitment (همه commit یا همه abort —
consensus با حقِ وتو: یک رأیِ abort یعنی abort؛ پایه‌ی 2PC) و Fetch-and-add
که با برچسبِ «consensus number 2» استثنای جمع است: فقط بینِ دو پیشنهاددهنده تصمیم می‌گیرد.
ردیفِ پایین با فلش‌های «yields» از قلب بیرون می‌آید: State machine replication
(همان لاگ + اجرای قطعی = replicaهای یکسان)، Fencing tokens (index هر entry یک عددِ افزایشی است —
zxid و revision — که نوشته‌های زامبی را می‌کُشد) و Leader election & leases
(تصمیمِ یک‌بار برای هر epoch؛ بدونِ split brain).
و دو جعبه‌ی پایینِ صفحه را آخر بخوان: «چه چیزی را باید تضمین کنی» — چهار خاصیتِ
Uniform agreement (هیچ دو نودی متفاوت تصمیم نمی‌گیرند)،
Integrity (تصمیم تغییر نمی‌کند)، Validity (فقط مقدارِ پیشنهادشده می‌تواند برنده شود)
و Termination (هر نودِ زنده‌ای بالاخره تصمیم می‌گیرد — تنها خاصیتِ liveness و نیازمندِ اکثریتِ زنده).
سه‌تای اول safetyاند و حتی با خرابیِ اکثریت هم نباید بشکنند؛ فقط پیشرفت می‌ایستد.
جعبه‌ی کناری هم «دامِ FLP» را یادآوری می‌کند و اینکه Raft و Paxos و VR و Zab در عمل، لاگِ مشترکِ با failoverِ خودکارند.
This structural diagram has one heart and several limbs. The heart is the big center box CONSENSUS — “one agreed value, one agreed order”, with “safety always, liveness with a majority”. The top row holds three boxes joined to the heart by green “≡ equivalent” arrows: Single-value consensus (nodes propose, one wins — leader election, lease claims, username registration), Shared log / total order broadcast (appending entries to one order, with “consensus number ∞” — the shape most systems actually ship) and Linearizable CAS (compare-and-set on one register, for locks and uniqueness).
The middle row parks two more boxes beside the heart: Atomic commitment (all commit or all abort — consensus with veto rights: one abort vote means abort; the basis of 2PC) and Fetch-and-add, the odd one out tagged “consensus number 2”: it only decides between two proposers. The bottom row flows out of the heart via “yields” arrows: State machine replication (the log + deterministic execution = identical replicas), Fencing tokens (each entry's index is a rising number — zxid, revision — that kills zombie writes) and Leader election & leases (one decision per epoch; no split brain).
Read the two bottom boxes last: “what you must guarantee” — the four properties Uniform agreement (no two nodes decide differently), Integrity (the decision never changes), Validity (only a proposed value may win) and Termination (every live node eventually decides — the only liveness property, needing a live majority). The first three are safety and must hold even in catastrophe; only progress stalls. The side box recalls the “FLP trap” and notes that Raft, Paxos, VR and Zab are, in practice, shared logs with automatic failover.
۳.۳. از تک‌رهبری به consensus: epoch و دو دور رأی3.3. From single-leader to consensus: epochs and two rounds of voting
شمارهٔ دورهٔ رهبری، تلاش‌های قدیمی و جدید را از هم جدا می‌کند. انتخاب رهبر و تأییدِ ورودی‌های لاگ دو نوع تصمیم‌اند؛ جزئیات رأی‌گیری و حفظ دادهٔ قبلی تعیین‌کننده‌اند.
مثال فنی: term بالاتر و رأی اکثریت
وضعیت اولیه: در گروه پنج‌نودی، A در term ۷ بوده و B با سه رأی در term ۸ انتخاب می‌شود.
اجرای مرحله‌به‌مرحله: رأی‌دهنده در هر term طبق پروتکل رأی می‌دهد و پیام term قدیمی رد می‌شود؛ انتخاب نامزد باید شرط تازگی لاگ را هم رعایت کند.
نتیجه و دلیل: term قدیمی حقِ ادامهٔ رهبری نمی‌دهد؛ شرطِ رأی و لاگ مانع دو تاریخچهٔ پذیرفته‌شدهٔ ناسازگار می‌شود.
In traditional single-leader setups a human performed failover — meaning downtime and a violated termination property. Consensus wants automatic leader election, but there is a paradox: electing a leader needs consensus, and consensus needs a leader! The way out: algorithms don't guarantee “one leader at every moment”; they define an epoch number (in Paxos a ballot, in VR a view, in Raft a term) and only guarantee one leader per epoch.
وقتی نودی مدتی از رهبر خبری نشنود، انتخاباتِ جدیدی با شماره‌ی epoch بزرگ‌تر شروع می‌کند.
اگر دو رهبرِ مربوط به دو epoch با هم تعارض کنند، رهبرِ با epoch بزرگ‌تر برنده است.
و قبل از آنکه رهبرِ جدید اجازه‌ی append به لاگ را داشته باشد، باید از یک quorum (معمولاً اکثریت) رأی بگیرد
تا مطمئن شود رهبرِ با epoch بالاتری در کار نیست. نتیجه: دو دور رأی‌گیری — یکی برای انتخابِ رهبر،
یکی برای تصویبِ هر entry — و quorum این دو باید هم‌پوشانی داشته باشند.
When a node hears nothing from the leader for a while, it starts a new election with a bigger epoch number. If two leaders from two epochs conflict, the higher-epoch leader wins. And before the new leader may append to the log, it must collect votes from a quorum (usually a majority) to be sure no higher-epoch leader exists. Result: two rounds of voting — one to elect the leader, one to approve each entry — and the two quorums must overlap.
این شبیهِ 2PC است؟ نه!Like 2PC? No!
هر دو «دو مرحله رأی» دارند، ولی تفاوت‌ها اساسی است: در consensus هر نودی می‌تواند انتخابات را شروع کند و فقط
پاسخِ quorum لازم است؛ در 2PC فقط هماهنگ‌کننده رأی می‌گیرد و به تک‌تک شرکت‌کنندگان نیاز دارد
(یکی ندهد، همه می‌ایستند). به همین دلیلِ ساده، کُردیناتورِ 2PC نقطه‌ی تکیِ خرابی می‌ماند مگر آنکه خودش با consensus مقاوم شود.
Both have “two voting rounds”, but the differences are fundamental: in consensus any node may start an election and only a quorum's replies are needed; in 2PC only the coordinator collects votes and it needs every single participant (one silence stalls everything). For exactly this reason the 2PC coordinator stays a single point of failure unless hardened by consensus itself.
۳.۴. لاگِ مشترک و replication ماشینِ وضعیت3.4. The shared log and state machine replication
در تکثیرِ ماشین حالت، گره‌ها دستورهای یک لاگ مشترک را با ترتیب یکسان اجرا می‌کنند. اگر اجرای دستورها قطعی باشد و از وضعیت یکسان شروع کنند، به وضعیت یکسان می‌رسند.
مثال فنی: همان لاگ، همان state
وضعیت اولیه: لاگِ commitشده شامل set(x,1) و سپس increment(x) است.
اجرای مرحله‌به‌مرحله: هر replica سالم هر دو را به همان ترتیب اعمال می‌کند و به x=2 می‌رسد.
نتیجه و دلیل: state machine باید برای همان ورودی‌ها نتیجهٔ یکسان بدهد؛ NOW() یا تصادفِ مستقل داخل apply می‌تواند replicaها را واگرا کند.
Most consensus systems in practice ship a shared log (the total-order-broadcast equivalent): Raft, VR and Zab do out of the box, and Paxos is used in practice as Multi-Paxos. The log is a superb replication tool: if each entry is one database write and all replicas apply the same entries in the same order with deterministic logic, all reach one final state — the idea called state machine replication (also the basis of event sourcing).
و از همین لاگ می‌توان بقیه‌ی اشکالِ consensus را هم ساخت: مقدارِ اولِ لاگ = پاسخِ consensus تک‌ارزشی؛
شماره‌ی صندلی در entryها = consensus جداگانه برای هر صندلی؛ جمعِ entryها = شمارنده‌ی fetch-and-add؛
و index هر entry = fencing token (در ZooKeeper به آن zxid می‌گویند).
And the same log builds the other consensus faces: the log's first value = the single-value consensus answer; seat numbers across entries = a separate consensus per seat; summing entries = a fetch-and-add counter; and each entry's index = a fencing token (in ZooKeeper called zxid).
روایت مدرس — نمودار ۷ را با صدای بلند بخوانیمTeacher narration
مثال فنی برای خواندنِ نمودار: همان لاگ، همان state
وضعیت اولیه: لاگِ commitشده شامل set(x,1) و سپس increment(x) است.
اجرای مرحله‌به‌مرحله: هر replica سالم هر دو را به همان ترتیب اعمال می‌کند و به x=2 می‌رسد.
نتیجه و دلیل: state machine باید برای همان ورودی‌ها نتیجهٔ یکسان بدهد؛ NOW() یا تصادفِ مستقل داخل apply می‌تواند replicaها را واگرا کند.
این یک dataflow است: جریانِ داده از چپ به راست در پنج مرحله می‌رود
که بالای نمودار شماره‌گذاری شده‌اند: 01 / Propose، 02 / Append،
03 / Total order، 04 / Replicate و 05 / Apply.
در مرحله‌ی اول سه جعبه می‌بینی: Client 1 writes و Client 2 writes و
Client 3 writes — هر سه با توضیحِ «concurrent / propose value»، یعنی چند کلاینت هم‌زمان پیشنهاد می‌نویسند.
فلشِ «propose write» آن‌ها را به جعبه‌ی Leader می‌رساند با توضیحِ «single writer / append entry».
فلشِ «append / log entry» از رهبر به Shared log می‌رود (توضیحِ «entries #1 #2 #3 / total order»):
یک ترتیبِ واحد از entryها — همان total order broadcast. بعد فلشِ «replicate / synchronous» به مرحله‌ی
Quorum copy می‌رسد («replica copies / majority ack»): هر entry قبل از تأیید به کلاینت،
به‌صورتِ هم‌زمان روی یک اکثریت کپی می‌شود و «majority ack» همان رأیِ quorum برای هر entry است.
سپس «deliver in order» به Apply in order («in log order / deterministic») و فلشِ «apply»
به State machine با توضیحِ «deterministic logic / same final state» می‌رسد:
با منطقِ قطعی و ترتیبِ یکسان، همه‌ی replicaها به یک وضعیتِ نهایی می‌رسند.
دو شاخه‌ی فرعی هم از لاگ بیرون می‌روند که قدرتِ لاگ را نشان می‌دهند:
Fencing token («monotonic counter / log index = token» — فلشِ «index = token»؛
index هر entry یک توکنِ افزایشی است) و Serial txns
(«stored procedure / one per entry» — فلشِ «stored procedure»؛ هر entry یک تراکنشِ قطعی باشد → تراکنش‌های سریال‌پذیر).
نکته‌ی پایانی: شارد‌کردنِ لاگ (یک لاگ به‌ازای هر shard) مقیاس‌پذیری می‌آورد ولی تضمین‌های بینِشاردی مثل
اسنپ‌شاتِ سازگار و foreign key را محدود می‌کند.
This dataflow runs left to right in five numbered stages: 01 / Propose, 02 / Append, 03 / Total order, 04 / Replicate and 05 / Apply. Stage one shows three boxes — Client 1 writes, Client 2 writes, Client 3 writes, all “concurrent / propose value”: several clients proposing at once. The “propose write” arrow delivers them to the Leader (“single writer / append entry”).
The “append / log entry” arrow runs from the leader to the Shared log (“entries #1 #2 #3 / total order”): one single order of entries — total order broadcast. Then “replicate / synchronous” reaches Quorum copy (“replica copies / majority ack”): each entry is synchronously copied to a majority before the client is acknowledged, and “majority ack” is the per-entry quorum vote. “Deliver in order” continues to Apply in order (“in log order / deterministic”), and “apply” to the State machine (“deterministic logic / same final state”): with deterministic logic and identical order, every replica reaches one final state. Two side branches off the log show its power: Fencing token (“monotonic counter / log index = token” — each entry's index is a rising token) and Serial txns (“stored procedure / one per entry” — one deterministic transaction per entry gives serializable transactions). Closing note: sharding the log (one log per shard) buys scalability but limits cross-shard guarantees like consistent snapshots and foreign keys.
۳.۵. ظرایف: سرنوشتِ یک log entry3.5. Subtleties: the fate of one log entry
وجود یک ورودی روی رهبر، به‌معنی تأیید نهایی آن نیست. پروتکل مشخص می‌کند چه زمانی ورودی ماندگار و قابل‌اعمال است و پس از تغییر رهبر چه سرنوشتی دارد.
مثال فنی: وجود روی یک نود، commit نیست
وضعیت اولیه: رهبر entry را روی خودش نوشته، اما پیش از تأیید quorum قطع می‌شود.
اجرای مرحله‌به‌مرحله: entry ممکن است در لاگ رهبر جدید نباشد و بعداً جایگزین شود؛ پاسخ موفق باید فقط طبق قاعدهٔ commitِ پروتکل داده شود.
نتیجه و دلیل: هر entryِ محلی ماندگارِ نهایی نیست؛ شرطِ commit و شرطِ انتخاب رهبر با هم از تاریخچهٔ پذیرفته‌شده محافظت می‌کنند.
Raft, Multi-Paxos, VR and Zab share this skeleton: a quorum vote elects the leader, and each entry needs another vote. The devil is in the details: when the old leader died and a new one arrives, entries the old leader acknowledged must survive. Raft forbids a lagging node from becoming leader (its log must be at least as fresh as a followers' majority); Paxos lets anyone lead but forces the new leader to catch its log up before appending.
روایت مدرس — نمودار ۸ را با صدای بلند بخوانیمTeacher narration
مثال فنی برای خواندنِ نمودار: وجود روی یک نود، commit نیست
وضعیت اولیه: رهبر entry را روی خودش نوشته، اما پیش از تأیید quorum قطع می‌شود.
اجرای مرحله‌به‌مرحله: entry ممکن است در لاگ رهبر جدید نباشد و بعداً جایگزین شود؛ پاسخ موفق باید فقط طبق قاعدهٔ commitِ پروتکل داده شود.
نتیجه و دلیل: هر entryِ محلی ماندگارِ نهایی نیست؛ شرطِ commit و شرطِ انتخاب رهبر با هم از تاریخچهٔ پذیرفته‌شده محافظت می‌کنند.
این نمودار یک ماشینِ وضعیت است با سه گروه که بالایشان نام‌گذاری شده:
Entry lifecycle (مسیرِ اصلی)، Slow quorum and term change (مسیرِ خطاها)
و Terminal outcomes (پایان‌ها). مسیرِ اصلی از 01 Proposed شروع می‌شود
(«client write arrives / next log slot» — درخواستِ نوشته رسید و رهبر مقدار را برای اسلاتِ بعدی پیشنهاد داد)،
با فلشِ «append to own log» به 02 Appended می‌رود («leader log, current term»)،
بعد با «send to followers» به 03 Replicating («quorum vote on the entry / second vote round» —
دورِ دومِ رأی؛ دورِ اول فقط رهبر را انتخاب کرده بود)، بعد با «acked by quorum» به 04 Committed
(«durable, client gets OK / never lost»)، و با «apply in log order» به 05 Applied
(«state machine updated»).
حالا مسیرِ خطاها. فلشِ «quorum not reached yet» از Replicating به وضعیتِ Stalled می‌رود
(«slow or failed nodes / retryable»): نودها کُند یا خراب‌اند و رهبر منتظر می‌ماند — و فلشِ برگشتیِ «retry and resend»
از بالای صف‌ها دوباره به Replicating بازمی‌گرداند. مسیرِ جدی‌تر فلشِ «higher term seen» است به
Superseded («higher term discovered / leader steps down»): رهبرِ قبلی باید کنار برود.
سرنوشتِ entry از این‌جا قطعی می‌شود: فلشِ «replaced by new leader» به Dropped می‌رود
(«uncommitted, overwritten» — entryهای تأییدنشده بازنویسی می‌شوند) و فلشِ «client retries» درخت را دوباره به Proposed می‌برد
(کلاینت با رهبرِ جدید دوباره تلاش می‌کند). و سمتِ سالمِ ماجرا: فلشِ «committed entry survives» از Applied به
Durable می‌رسد («survives every failover»).
خطِ بینِ این دو دقیقاً همان «commit» است: قبل از آن هیچ‌چیز قطعی نیست، بعد از آن همه‌چیز ابدی است —
و دلیلش قاعده‌ی Raft است: فقط نودی رهبر می‌شود که لاگش دست‌کم به‌روزِ اکثریت باشد.
This state machine has three groups: Entry lifecycle (the main path), Slow quorum and term change (the fault paths) and Terminal outcomes. The main path runs 01 Proposed (“client write arrives / next log slot”) → “append to own log” → 02 Appended (“leader log, current term”) → “send to followers” → 03 Replicating (“quorum vote on the entry / second vote round” — the second round; the first only elected the leader) → “acked by quorum” → 04 Committed (“durable, client gets OK / never lost”) → “apply in log order” → 05 Applied (“state machine updated”).
The fault paths: “quorum not reached yet” leads from Replicating to Stalled (“slow or failed nodes / retryable”) — the leader waits, and “retry and resend” loops back to Replicating. The graver path is “higher term seen” to Superseded (“higher term discovered / leader steps down”): the old leader must step aside. The entry's fate is then sealed: “replaced by new leader” goes to Dropped (“uncommitted, overwritten” — uncommitted entries are rewritten) with “client retries” looping back to Proposed, while “committed entry survives” runs from Applied to Durable (“survives every failover”). The line between the two is exactly “commit”: before it nothing is final, after it everything is eternal — thanks to Raft's rule that only a node at least as fresh as a majority may lead.
سازگاری در برابر دردسترس‌بودنِ انتخابِ رهبرConsistency vs leader-election availability
اگر نودی با داده‌ی کهنه رهبر شود، ممکن است روی entryهایی بنویسد که رهبرِ قبلی نوشته — و خاصیتِ append-only می‌شکند.
گاهی آگاهانه این تضمین را ضعیف می‌کنیم تا سریع‌تر برگردیم: مثلاً Kafka گزینه‌ی
unclean leader election را دارد که هر replicaای می‌تواند رهبر شود، حتی عقب‌افتاده.
نتیجه: در دسترسیِ بیشتر، ولی دیگر نظریه‌ی consensus حاکم نیست — تا وقتی خرابی نداشته باشی خوب است؛
با اولین ترکیبِ بدِ خرابی‌ها، داده گم یا خراب می‌شود. نکته‌ی دیگر: برای خواندنِ خطی‌پذیر هم باید رأیِ quorum گرفت
(مثلاً در etcd) تا «رهبرِ هنوزمعتبر» تأیید شود؛ و الگوریتم‌ها برای افزودن/حذفِ نود به reconfiguration نیاز دارند.
If a stale node becomes leader, it may overwrite entries the previous leader wrote — breaking append-only. We sometimes knowingly weaken this guarantee to recover faster: Kafka's unclean leader election lets any replica lead, even a lagging one. Result: more availability, but consensus theory no longer rules — fine until the first bad combination of failures loses or corrupts data. Related point: linearizable reads need a quorum vote too (e.g. in etcd) to confirm “still the valid leader”; and algorithms need reconfiguration to add or remove nodes.
۳.۶. مزایا و بهای consensus3.6. The benefits and price of consensus
اجماع تحمل خرابی و تصمیمِ مشترک می‌دهد، اما به پیام‌رسانی، نسخه‌های اضافی و اکثریتِ در دسترس نیاز دارد. برای داده و عملیاتی که این هماهنگی لازم نیست، هزینه‌اش ممکن است زیاد باشد.
مثال فنی: سه نود، تحمل یک خرابی
وضعیت اولیه: گروه سه‌عضوی برای عملیات نیازمند اکثریت به دو عضو دسترس‌پذیر نیاز دارد.
اجرای مرحله‌به‌مرحله: خرابی یک عضو قابل‌تحمل است؛ با خرابی دو عضو پیشرفت متوقف می‌شود تا اکثریت برگردد.
نتیجه و دلیل: افزایش اعضا هزینهٔ replication و هماهنگی دارد؛ اجماع معمولاً برای تصمیم‌های لازم استفاده می‌شود، نه هر محاسبهٔ مستقل.
Consensus is really “single-leader done right”: automatic failover, no lost committed data, no split brain — despite all of Chapter 9's troubles. The practical rule: any automatic-failover system not built on a proven consensus algorithm is probably unsafe. A proven algorithm doesn't guarantee the whole system — bugs live elsewhere too — but it is a good start.
- اکثریتِ سخت‌گیرانه: سه نود برای تحملِ یک خرابی، پنج نود برای دو خرابی. هر عملیات = ارتباط با quorum؛
افزودنِ نود سیستم را کُندتر می‌کند، نه سریع‌تر. در partition فقط بخشِ اکثریت پیش می‌رود.
- وابستگی به timeout: تشخیصِ خرابی با timeout است. timeout زیاد = بازیابیِ کُند؛ timeout کم = انتخاباتِ مکرر و
وقت‌گذرانیِ سیستم برای انتخابِ رهبر به‌جای کارِ مفید. در چندمنطقه‌ای تنظیمش سخت است.
- حساسیت به شبکه‌ی بد: اگر فقط یک لینک نامطمئن باشد، Raft می‌تواند در حالتی گیر کند که رهبری مدام بینِ دو نود بپرَد
یا رهبر مجبور به استعفا شود و سیستم عملاً پیشرفت نکند. راه‌حلِ بعدیِ Raft فازِ pre-vote بود؛
و EPaxos با حذفِ رهبر، در برابرِ نود/لینکِ بد مقاوم‌تر است.
- Strict majority: three nodes to survive one failure, five for two. Every operation = talking to a quorum; adding nodes makes the system slower, not faster. During a partition only the majority side advances.
- Timeout dependence: failure detection runs on timeouts. Long timeout = slow recovery; short timeout = constant elections with the system politicking instead of working. Hard to tune across regions.
- Bad-network sensitivity: a single flaky link can trap Raft in leadership flapping between two nodes, or force the leader to resign so the system makes no progress. Raft's later pre-vote phase answered this; EPaxos drops the leader and resists bad nodes/links better.
مفهوم مکمل — دو دور رأی: consensus در برابر 2PCExtra concept — two voting rounds: consensus vs 2PC
روایت مدرس از نمودارTeacher narration
مثال فنی برای خواندنِ نمودار: اجماع با 2PC فرق دارد
وضعیت اولیه: در consensus، سه replica از پنج replica ممکن است با خرابی دو عضو پیشرفت کنند.
اجرای مرحله‌به‌مرحله: در 2PC، participantِ prepared که تصمیم coordinator را ندارد ممکن است منتظر بماند؛ رأی yesِ همه برای مسیر commit لازم است.
نتیجه و دلیل: هر دو پیام‌های چندمرحله‌ای دارند، اما یکی تصمیمِ تکرارشدهٔ مقاوم به خرابی و دیگری commit مشترکِ منابع را هدف می‌گیرد.
دو ستون را مقایسه کن: در consensus هر دو دور (انتخاب رهبر و تصویب entry) فقط به quorum نیاز دارند و هر نودی می‌تواند شروع کند — یک نود خاموش مشکلی نیست. در 2PC فقط هماهنگ‌کننده رأی می‌گیرد و به تک‌تک شرکت‌کنندگان نیاز دارد — یک سکوت همه‌چیز را متوقف می‌کند. نتیجه در نوار پایین است: هماهنگ‌کننده نقطه تکی خرابی می‌ماند، مگر با consensus مقاوم شود.
Compare the two columns: in consensus both rounds (leader election and entry approval) need only a quorum, and any node may start — one silent node is harmless. In 2PC only the coordinator collects votes and needs every participant — one silence stalls everything. The bottom strip concludes: the coordinator stays a single point of failure unless hardened by consensus.