🖼️ See the drawing + lab 🏠 Course home 🌿 Branch on GitHub ✏️ View source

🖼️ आकृती आणि labThe drawing + lab पूर्ण पानावर उघडा ↗Open full page ↗

🔏 धडा 10 — Locks, leases & fencing: संपणारे कुलूप

📍 तुम्ही इथे आहात: 12 पैकी धडा 10 · मागे: lesson-09-raft · पुढे: lesson-11-exactly-once

📦 या ब्रँचमध्ये काय आहे

धडे 01–09, आणि distributed locks: machines पलीकडचे lock lease का असायला हवे (ते संपते), holder थांबला तर फक्त lease सुरक्षित का नाही, आणि त्यावरचा उपाय — storage तपासते तो fencing token. हे Martin Kleppmann यांचे सुप्रसिद्ध उदाहरण आहे. dist/demo.py मधील locks() आणि dist/sim.py मधील LockService + Storage.

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

एका वेळी फक्त एकच व्यक्ती timetable बदलू शकते. म्हणून मुख्य office मध्ये एक किल्ली 🔑 असते.

पण कतरिनाने किल्ली घेतली आणि मग ती आठवडाभर झोपून गेली तर? कोणीच timetable बदलू शकणार नाही. म्हणून किल्ली म्हणजे एक lease: ती 1 second चालते, मग ती तिची मानली जात नाही. 🕐

कतरिना किल्ली घेते. मुख्य office त्यावर एक क्रमांक लिहिते: token 1. मग कतरिना 2 seconds साठी गोठते (तिचा computer memory साफ करण्यात व्यस्त आहे — एक लांब थांबा). आपण गोठलो होतो हे तिला कळत नाही.

1.5 seconds ला तिची lease संपलेली असते. ऐश्वर्या किल्ली घेते: token 2. ती timetable v2 लिहिते.

2.0 seconds ला कतरिना जागी होते. तिच्या मनात काहीच वेळ गेलेला नाही. तिला वाटते किल्ली अजून तिच्याकडेच आहे, आणि ती timetable v1 लिहिते. 😬

Timetable ला कोण वाचवते? कपाट 🗄️ त्याने पाहिलेला सर्वात मोठा token लक्षात ठेवते. त्याने 2 पाहिला आहे. कतरिना 1 दाखवते. कपाट म्हणते: "नाही. तू खूप जुनी आहेस."

🗺️ आकृती

sequenceDiagram
    participant K as Katrina
    participant L as Lock service
    participant A as Aishwarya
    participant S as Storage
    K->>L: acquire at 0 s
    L-->>K: lease 1 s, token 1
    Note over K: long pause, 2 s
    A->>L: acquire at 1.5 s, lease expired
    L-->>A: token 2
    A->>S: write v2 with token 2
    S-->>A: wrote, highest token is 2
    K->>S: write v1 with token 1 at 2.0 s
    S-->>K: refused, already saw 2

🗺️ रेखाटलेली आवृत्ती + एक lab: https://school-edh.pages.dev/distributed-systems/lesson-diagrams.html#l10

❓ काय

Distributed lock — machines पलीकडे "एका वेळी फक्त एकच node X करू शकते": एक leader, एका file चा एक writer, एक job runner.
Lease — वेळेची मर्यादा असलेले lock. Holder crash झाला तर lease संपते आणि दुसरे कोणी ती घेऊ शकते. संपण्याची सोय नसेल तर crash झालेला holder सगळ्यांना कायमचे अडवतो.
Leases ची अडचण — त्याचा write पोहोचतो त्या क्षणी आपली lease अजून वैध आहे याची holder ला खात्री असू शकत नाही. "मी माझी lease तपासली" आणि "माझा write पोहोचला" यांच्या दरम्यान process pause (garbage collection, virtual machine suspend होणे, operating system ने memory disk वर swap करणे) किंवा हळू network येऊ शकतो. Seconds चे थांबे घडतात.
घड्याळांबद्दलची गृहीतके — lease घड्याळांनी मोजली जाते: lock service चे घड्याळ संपण्याची वेळ ठरवते, आणि holder किती वेळ उरला याचा अंदाज आपल्या घड्याळाने लावतो. एखादे घड्याळ पुढे पळाले किंवा उडी मारली (धडा 02), तर "संपले" याबद्दल त्यांच्या कल्पना वेगळ्या होतात. Leases फक्त मर्यादित pauses, network delays आणि clock drift असतानाच सुरक्षित असतात — ही गृहीतके आहेत, तथ्ये नव्हेत.
Fencing token — lock service प्रत्येक वेळी lock देताना देते तो क्रमांक; तो फक्त वाढत जातो (1, 2, 3 …). Holder तो प्रत्येक write सोबत पाठवतो. Storage आपण स्वीकारलेला सर्वात मोठा token लक्षात ठेवते आणि त्याहून लहान token असलेला कोणताही write नाकारते. आता जुना holder उशिरा जागा झाला तरी काही नुकसान करू शकत नाही.
Kleppmann यांचे उदाहरण ("How to do distributed locking", 2016, आणि Designing Data-Intensive Applications या पुस्तकातून): client 1 lease घेतो, garbage collection साठी थांबतो, lease संपते, client 2 lease घेतो आणि token 34 सह लिहितो, मग client 1 जागा होतो आणि token 33 सह लिहितो — storage 33 नाकारते. इथला धडा tokens 1 आणि 2 वापरतो.
मुख्य मुद्दा — ही तपासणी storage वरच (ज्याचे संरक्षण करायचे त्या गोष्टीवर) व्हायला हवी. Holder स्वतःला तपासू शकत नाही, कारण थांबलेल्या process ला आपण थांबलो होतो हे कळत नाही.

🤔 का

कारण locks सहसा बरोबरपणासाठी वापरले जातात: "कधीच दोन writers नकोत". जे lock फक्त बहुतेक वेळा exclusive असते ते कार्यक्षमतेसाठी ठीक आहे (तेच काम दोनदा टाळणे) आणि बरोबरपणासाठी धोकादायक आहे (data बिघडतो). Fencing token "बहुतेक वेळा" चे "नेहमी" करतो, जोपर्यंत storage तो तपासते.

🔧 कसे (या repo मध्ये)

dist/sim.py मधील LockService(lease_ms) acquire(who, now) मध्ये lock तेव्हाच देते जेव्हा ते कोणाकडेच नसते किंवा lease संपलेली असते (now >= expires); प्रत्येक वेळी lock देताना ते token मध्ये 1 मिळवते आणि तो परत करते (किंवा lock आधीच घेतलेले असेल तर None). Storage.write(token, value, fencing=True) त्याने पाहिलेल्या सर्वात मोठ्या token पेक्षा लहान token नाकारते; fencing=False असेल तर ते काहीही स्वीकारते.

🧪 करून पाहा

python3 dist/demo.py locks
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import LockService, Storage
for lease in (1000, 3000):
    ls, st = LockService(lease_ms=lease), Storage()
    t1 = ls.acquire("katrina", 0)
    t2 = ls.acquire("aishwarya", 1500)
    print(f"lease {lease} ms: Katrina token {t1}, Aishwarya at 1.5 s → {t2}")
ls, st = LockService(1000), Storage()
t1 = ls.acquire("katrina", 0); t2 = ls.acquire("aishwarya", 1500); t3 = ls.acquire("dipika", 2600)
print("tokens:", t1, t2, t3)
for tok, who in ((t3, "dipika"), (t2, "aishwarya"), (t1, "katrina")):
    print(f"  {who} writes with token {tok} → {st.write(tok, who + ' timetable')}")
print("  final value:", st.value)
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

locks हे print करते:

── Katrina takes the timetable lock, lease 1 s, fencing token 1 — then pauses for 2 s (a long GC)
   at 1.5 s the lease has expired; Aishwarya takes the lock → token 2 and writes → wrote 'timetable v2'
   Katrina wakes at 2.0 s, still thinks she holds the lock, writes with token 1 → refused token 1 (already saw 2)
   without fencing tokens → wrote 'timetable v1' — newer work silently overwritten
   a lease alone is not enough; the storage must check the token

तुमचा snippet हे print करतो:

lease 1000 ms: Katrina token 1, Aishwarya at 1.5 s → 2
lease 3000 ms: Katrina token 1, Aishwarya at 1.5 s → None
tokens: 1 2 3
  dipika writes with token 3 → wrote 'dipika timetable'
  aishwarya writes with token 2 → refused token 2 (already saw 3)
  katrina writes with token 1 → refused token 1 (already saw 3)
  final value: dipika timetable

🏁 तुम्ही आत्ताच काय सिद्ध केले

लांब lease (3 s) अडचण फक्त पुढे ढकलते: ऐश्वर्याला थांबावे लागते, आणि 4-second चा pause ती पुन्हा मोडेल. प्रत्येक pause साठी पुरेशी लांब अशी कोणतीही lease नाही. तीन holders सर्वात वाईट क्रमाने उशिरा आले तरी storage ने फक्त सर्वात नव्या holder चेच काम ठेवले — token ठरवतो, पोहोचण्याचा क्रम नव्हे आणि कोणाचे घड्याळही नव्हे.

⚠️ नेहमीच्या चुका

कधीच overwrite होऊ नये अशा data चे संरक्षण fencing token नसलेल्या lease ने करणे
लिहिण्याच्या अगदी आधी client मध्ये lease तपासणे ("ते अजून माझ्याकडे आहे") — pause तपासणीनंतर लगेच येऊ शकतो
token कडे दुर्लक्ष करणारे storage, त्यामुळे token कशाचेच संरक्षण करत नाही
संपण्याची सोय नसलेले lock — एक crash झालेला holder सगळ्यांना अडवतो
जिथे idempotent write (धडा 11) किंवा conditional update ला lock ची गरजच नसती तिथे lock वापरणे

🏭 प्रत्यक्ष वापरात

Redis locks — single-instance pattern म्हणजे NX (फक्त नसेल तर) आणि expiry सह SET. On a real account:

redis-cli SET lock:timetable 9f2c41d7 NX PX 30000   # OK = you hold it for 30 s; (nil) = someone else does

Value अजून तुमचीच असेल तरच ते सोडा (एक छोटी Lua script तुलना करते, मग delete करते). Redlock हेच अनेक स्वतंत्र Redis servers वर पुन्हा करते आणि बहुमत मोजते. Kleppmann यांची टीका: Redlock ची सुरक्षितता timing गृहीतकांवर (मर्यादित pauses, मर्यादित clock drift) अवलंबून आहे, आणि ते कोणताही fencing token तयार करत नाही. Redis locks कार्यक्षमतेसाठी वापरा (duplicate काम टाळणे); बरोबरपणासाठी, token देणारे lock आणि तो तपासणारे storage वापरा.

etcd — lease आणि lock; प्रत्येक key ला एक revision क्रमांक असतो जो संपूर्ण store मध्ये फक्त वाढत जातो, त्यामुळे lock key ची revision fencing token म्हणून वापरता येते:

etcdctl lease grant 10                       # lease 694d7b1c2f0e4a1b granted with TTL(10s)
etcdctl lock timetable ./edit-timetable.sh      # runs the command while holding the lock

ZooKeeper — एक ephemeral sequential node तयार करा; सर्वात लहान क्रमांकाकडे lock असते, आणि holder चे session संपल्यावर ती node नाहीशी होते. तिचा sequence number (किंवा transaction ID zxid) fencing token म्हणून काम करतो:

zkCli.sh create -e -s /locks/timetable- katrina   # Created /locks/timetable-0000000007

Kubernetes controllers Lease object वापरून leader निवडतात (coordination.k8s.io): holderIdentity, leaseDurationSeconds, renewTime.

kubectl get lease -n kube-system                # kube-controller-manager, kube-scheduler …

Fencing ची storage बाजू — उदाहरणार्थ SQL मध्ये, write फक्त नव्या token सह स्वीकारा:

UPDATE timetable SET body = $1, fence = $2
WHERE id = 'term-2' AND fence < $2;          -- 0 rows updated → a stale holder; stop

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक lock साठी दोन प्रश्न विचारा: "holder 30 seconds थांबला तर काय होईल?" आणि "token कुठे तपासला जातो?". दुसऱ्या प्रश्नाचे उत्तर "कुठेच नाही" असेल, तर ते lock फक्त कार्यक्षमतेचे संरक्षण करते, बरोबरपणाचे नव्हे.

⏭️ पुढे

Locks दोन writers ना थांबवतात. Retries एक वेगळीच अडचण निर्माण करतात: तोच message दोनदा हाताळला जाणे. पुढे: exactly-once चे मिथक.

git checkout lesson-11-exactly-once

🔏 Lesson 10 — Locks, leases & fencing: a lock that expires

📍 You are here: Lesson 10 of 12 · Previous: lesson-09-raft · Next: lesson-11-exactly-once

📦 What's in this branch

Lessons 01–09, plus distributed locks: why a lock across machines must be a lease (it expires), why a lease alone is not safe when the holder pauses, and the fix — a fencing token that the storage checks. This is Martin Kleppmann's well-known example. locks() in dist/demo.py and LockService + Storage in dist/sim.py.

🧒 Explain like I'm 5

Only one person may edit the timetable at a time. So there is a key 🔑 at the head office.

But what if Katrina takes the key and then falls asleep for a week? Nobody could edit the timetable. So the key is a lease: it works for 1 second, then it stops counting as hers. 🕐

Katrina takes the key. The head office writes a number on it: token 1. Then Katrina freezes for 2 seconds (her computer is busy cleaning memory — a long pause). She does not know she froze.

At 1.5 seconds her lease has run out. Aishwarya takes the key: token 2. She writes timetable v2.

At 2.0 seconds Katrina wakes up. In her mind, no time has passed. She thinks she still holds the key, and writes timetable v1. 😬

What saves the timetable? The filing cabinet 🗄️ remembers the biggest token it has seen. It has seen 2. Katrina shows 1. The cabinet says: "No. You are too old."

🗺️ Diagram

sequenceDiagram
    participant K as Katrina
    participant L as Lock service
    participant A as Aishwarya
    participant S as Storage
    K->>L: acquire at 0 s
    L-->>K: lease 1 s, token 1
    Note over K: long pause, 2 s
    A->>L: acquire at 1.5 s, lease expired
    L-->>A: token 2
    A->>S: write v2 with token 2
    S-->>A: wrote, highest token is 2
    K->>S: write v1 with token 1 at 2.0 s
    S-->>K: refused, already saw 2

🗺️ Drawn version + a lab: https://school-edh.pages.dev/distributed-systems/lesson-diagrams.html#l10

❓ What

Distributed lock — "only one node may do X at a time" across machines: one leader, one writer of a file, one job runner.
Lease — a lock with a time limit. If the holder crashes, the lease expires and someone else can take it. Without expiry, a crashed holder blocks everyone for ever.
The problem with leases — the holder cannot be sure its lease is still valid at the moment its write lands. Between "I checked my lease" and "my write arrived" there can be a process pause (garbage collection, the virtual machine being suspended, the operating system swapping memory to disk), or a slow network. Pauses of seconds happen.
Clock assumptions — a lease is measured with clocks: the lock service's clock decides expiry, and the holder uses its own clock to guess how much time it has left. If one runs fast or jumps (lesson 02), their ideas of "expired" differ. Leases are safe only under bounded pauses, network delays and clock drift — assumptions, not facts.
Fencing token — a number the lock service hands out with every grant; it only goes up (1, 2, 3 …). The holder sends it with every write. The storage remembers the highest token it has accepted and refuses any write with a smaller one. Now an old holder can wake up late and do no harm.
Kleppmann's example (from "How to do distributed locking", 2016, and the book Designing Data-Intensive Applications): client 1 takes a lease, pauses for garbage collection, the lease expires, client 2 takes the lease and writes with token 34, then client 1 wakes and writes with token 33 — the storage rejects 33. The lesson here uses tokens 1 and 2.
The key point — the check must happen at the storage (the thing being protected). The holder cannot check itself, because a paused process does not know it paused.

🤔 Why

Because locks are usually used for correctness: "never two writers". A lock that is only usually exclusive is fine for efficiency (avoid doing the same work twice) and dangerous for correctness (corrupt data). A fencing token turns "usually" into "always", as long as the storage checks it.

🔧 How (in this repo)

LockService(lease_ms) in dist/sim.py grants the lock in acquire(who, now) only if nobody holds it or the lease has expired (now >= expires); each grant adds 1 to token and returns it (or None when the lock is taken). Storage.write(token, value, fencing=True) refuses a token smaller than the highest it has seen; with fencing=False it accepts anything.

🧪 Try it

python3 dist/demo.py locks
python3 - <<'EOF'
import sys; sys.path.insert(0, "dist"); from sim import LockService, Storage
for lease in (1000, 3000):
    ls, st = LockService(lease_ms=lease), Storage()
    t1 = ls.acquire("katrina", 0)
    t2 = ls.acquire("aishwarya", 1500)
    print(f"lease {lease} ms: Katrina token {t1}, Aishwarya at 1.5 s → {t2}")
ls, st = LockService(1000), Storage()
t1 = ls.acquire("katrina", 0); t2 = ls.acquire("aishwarya", 1500); t3 = ls.acquire("dipika", 2600)
print("tokens:", t1, t2, t3)
for tok, who in ((t3, "dipika"), (t2, "aishwarya"), (t1, "katrina")):
    print(f"  {who} writes with token {tok} → {st.write(tok, who + ' timetable')}")
print("  final value:", st.value)
EOF

✅ Verify — what you should see

locks prints:

── Katrina takes the timetable lock, lease 1 s, fencing token 1 — then pauses for 2 s (a long GC)
   at 1.5 s the lease has expired; Aishwarya takes the lock → token 2 and writes → wrote 'timetable v2'
   Katrina wakes at 2.0 s, still thinks she holds the lock, writes with token 1 → refused token 1 (already saw 2)
   without fencing tokens → wrote 'timetable v1' — newer work silently overwritten
   a lease alone is not enough; the storage must check the token

Your snippet prints:

lease 1000 ms: Katrina token 1, Aishwarya at 1.5 s → 2
lease 3000 ms: Katrina token 1, Aishwarya at 1.5 s → None
tokens: 1 2 3
  dipika writes with token 3 → wrote 'dipika timetable'
  aishwarya writes with token 2 → refused token 2 (already saw 3)
  katrina writes with token 1 → refused token 1 (already saw 3)
  final value: dipika timetable

🏁 What you just proved

A longer lease (3 s) only moves the problem: Aishwarya must wait, and a 4-second pause would break it again. There is no lease long enough for every pause. With three holders arriving late in the worst order, the storage still kept only the newest holder's work — the token decides, not the arrival order and not anyone's clock.

⚠️ Common mistakes

a lease with no fencing token, protecting data that must never be overwritten
checking the lease in the client just before writing ("I still hold it") — the pause can come right after the check
a storage that ignores the token, so the token protects nothing
a lock with no expiry — one crashed holder blocks everyone
using a lock where an idempotent write (lesson 11) or a conditional update would need no lock at all

🏭 In production

Redis locks — the single-instance pattern is SET with NX (only if not present) and an expiry. On a real account:

redis-cli SET lock:timetable 9f2c41d7 NX PX 30000   # OK = you hold it for 30 s; (nil) = someone else does

Release it only if the value is still yours (a small Lua script compares, then deletes). Redlock repeats this on several independent Redis servers and counts a majority. Kleppmann's critique: Redlock's safety depends on timing assumptions (bounded pauses, bounded clock drift), and it produces no fencing token. Use Redis locks for efficiency (avoid duplicate work); for correctness, use a lock that gives a token and a storage that checks it.

etcd — a lease plus a lock; every key has a revision number that only goes up across the whole store, so the lock key's revision can be the fencing token:

etcdctl lease grant 10                       # lease 694d7b1c2f0e4a1b granted with TTL(10s)
etcdctl lock timetable ./edit-timetable.sh      # runs the command while holding the lock

ZooKeeper — create an ephemeral sequential node; the lowest number holds the lock, and the node disappears when the holder's session ends. Its sequence number (or the transaction ID zxid) works as a fencing token:

zkCli.sh create -e -s /locks/timetable- katrina   # Created /locks/timetable-0000000007

Kubernetes controllers elect a leader with a Lease object (coordination.k8s.io): holderIdentity, leaseDurationSeconds, renewTime.

kubectl get lease -n kube-system                # kube-controller-manager, kube-scheduler …

The storage side of fencing — for example in SQL, accept a write only with a newer token:

UPDATE timetable SET body = $1, fence = $2
WHERE id = 'term-2' AND fence < $2;          -- 0 rows updated → a stale holder; stop

🏭 Why this matters in production: for every lock, ask two questions: "what happens if the holder pauses for 30 seconds?" and "where is the token checked?". If the answer to the second is "nowhere", the lock only protects efficiency, not correctness.

⏭️ Next

Locks stop two writers. Retries create a different problem: the same message done twice. Next: the exactly-once myth.

git checkout lesson-11-exactly-once

← Previousraft Next →exactly once

This page is the lesson's README from the lesson-10-locks-leases branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.