Lock-free ও Concurrency
- ●Lock/mutex contention latency-তে অপ্রত্যাশিত spike তৈরি করে; lock-free structure এই spike এড়িয়ে predictable performance দেয়।
- ●CAS (compare-and-swap) atomic instruction-ই হলো lock-free programming-এর মূল হাতিয়ার, যা lock ছাড়াই নিরাপদ update নিশ্চিত করে।
- ●Single-writer principle ও ring buffer (LMAX Disruptor) দিয়ে contention প্রায় শূন্যে নামিয়ে আনা যায়।
সমস্যাটা কী?
Multi-core প্রসেসরে একসাথে অনেক thread কাজ করে। কিন্তু যখন একাধিক thread একই data পরিবর্তন করতে চায়, তখন race condition হতে পারে — data নষ্ট হয়ে যায়। এর প্রচলিত সমাধান হলো lock (mutex) — একসময়ে একটাই thread data ছোঁবে।
সমস্যা হলো, lock low-latency সিস্টেমে এক নীরব ঘাতক। যখন একটি thread lock ধরে রাখে আর বাকিরা অপেক্ষা করে, তখন কী হয়? অপেক্ষমাণ thread-গুলো OS দ্বারা blocked হয়, context switch ঘটে (প্রতিটি প্রায় ১-৫ µs), এবং সবচেয়ে খারাপ — তারা কখন আবার চলবে তা OS scheduler ঠিক করে, যা অপ্রত্যাশিত। ফলে latency-তে random spike আসে। ট্রেডিং সিস্টেমে এই অনিশ্চয়তা মানেই হারানো টাকা।
আরও খারাপ ঘটনা ঘটতে পারে — priority inversion (নিম্ন priority thread lock ধরে রেখে উচ্চ priority thread-কে আটকে রাখে) বা convoying (একটা slow thread পুরো লাইনকে আটকে দেয়)।
মূল ধারণা
Lock-free programming হলো এমন কৌশল যেখানে একাধিক thread কোনো mutual-exclusion lock ছাড়াই shared data নিরাপদে পরিবর্তন করে — এবং গ্যারান্টি থাকে যে সিস্টেম হিসেবে অন্তত একটি thread সবসময় progress করবে (কখনো পুরোপুরি আটকে যাবে না)।
মূল পার্থক্যটা বুঝে নাও:
- Lock-based: thread blocking, OS-নির্ভর, contention-এ unpredictable।
- Lock-free: কোনো thread blocked হয় না; অন্তত একটি thread সবসময় এগোয় (system-wide progress)।
- Wait-free: সবচেয়ে শক্তিশালী — প্রতিটি thread সীমিত (bounded) সংখ্যক step-এ কাজ শেষ করে। কোনো starvation নেই।
Lock-free মানে কিন্তু "lock ছাড়া দ্রুত" নয় সবসময় — এর আসল মূল্য হলো predictability ও failure isolation: একটা thread crash বা slow হলেও বাকিরা আটকায় না।
কীভাবে কাজ করে
CAS — মূল হাতিয়ার
Lock-free programming-এর হৃদয় হলো CAS (Compare-And-Swap) — একটি atomic CPU instruction। এটি বলে: "যদি এই memory location-এ এখনও পুরোনো মান থাকে, তবে নতুন মান বসাও; নাহলে fail করো।" পুরোটা একটি single, uninterruptible operation।
// pseudo-code: lock-free counter increment
do {
old = counter; // বর্তমান মান পড়ো
new = old + 1; // নতুন মান হিসাব করো
} while (!CAS(&counter, old, new)); // মান না বদলালে বসাও, বদলালে আবার চেষ্টা
এখানে কোনো lock নেই। যদি দুই thread একসাথে চেষ্টা করে, একজনের CAS সফল হয়, অন্যজনের fail হয় এবং সে retry করে। এই retry loop-ই lock-free-এর সৌন্দর্য — কেউ blocked হয় না।
Atomics ও memory ordering
আধুনিক CPU performance-এর জন্য instruction reorder করে। তাই lock-free কোডে memory barrier / ordering (যেমন C++-এর memory_order_acquire, memory_order_release) ব্যবহার করতে হয়, যাতে এক thread-এর লেখা অন্য thread সঠিক ক্রমে দেখে। এটি না বুঝলে subtle bug তৈরি হয় যা কেবল production-এ random-ভাবে দেখা দেয়।
| বৈশিষ্ট্য | Lock-based (Mutex) | Lock-free (CAS) |
|---|---|---|
| Contention-এ আচরণ | thread blocked, context switch | retry, কিন্তু running থাকে |
| Latency predictability | কম (OS-নির্ভর) | বেশি |
| Deadlock সম্ভাবনা | আছে | নেই |
| Priority inversion | সম্ভব | নেই |
| জটিলতা | সহজ | অনেক কঠিন |
Ring Buffer ও LMAX Disruptor
Lock-free-এর সবচেয়ে বিখ্যাত প্রয়োগ হলো ring buffer — একটি fixed-size circular array যেখানে producer এক প্রান্তে লেখে, consumer অন্য প্রান্তে পড়ে। LMAX Disruptor (একটি লন্ডন ট্রেডিং exchange-এর তৈরি) এই ধারণাকে চূড়ান্ত পর্যায়ে নিয়ে গেছে — এটি একটি single thread-এ প্রতি সেকেন্ডে ২ কোটি+ মেসেজ process করতে পারে, কারণ এটি lock এড়ায়, garbage তৈরি কমায়, এবং cache-friendly memory layout ব্যবহার করে।
একটা ব্যাংকের একটাই খাতা ভাবো যেখানে সবাই টাকা জমা/তোলার হিসাব লেখে। Lock মানে — একজন খাতা নিয়ে দরজা বন্ধ করে লেখে, বাকিরা বাইরে লাইনে অপেক্ষা করে (একজন slow হলে পুরো লাইন আটকা)। CAS মানে — তুমি খাতার বর্তমান balance দেখলে, নতুন balance হিসাব করলে, লিখতে গিয়ে দেখলে balance এখনও আগের মতোই আছে কিনা; থাকলে লিখলে, না থাকলে আবার নতুন করে হিসাব করলে। কেউ দরজা বন্ধ করে বসে নেই।
কৌশল
- CAS-based atomic operations দিয়ে counter, flag, pointer update।
- Lock-free queue/stack (যেমন Michael-Scott queue) producer-consumer-এর জন্য।
- Ring buffer / Disruptor high-throughput event processing-এ।
- Single-writer principle: যেকোনো data-তে কেবল একটি thread লিখবে। এটি contention প্রায় শূন্যে নামিয়ে আনে, কারণ cache line এক core থেকে অন্য core-এ "bounce" করে না, আর synchronization লাগেই না। অন্যরা শুধু পড়ে।
- Sharding/partitioning: প্রতিটি thread-কে আলাদা data partition দাও, যাতে তারা কখনো একই data-তে লড়াই না করে।
কখন ব্যবহার করবে / করবে না
Lock-free ব্যবহার করো যখন latency predictability অত্যন্ত গুরুত্বপূর্ণ — trading, real-time gaming, OS kernel, high-throughput messaging। যখন contention তীব্র এবং blocking-এর খরচ অসহনীয়।
ব্যবহার করবে না যখন contention কম এবং কোড সহজ রাখা জরুরি। একটা সাধারণ web app-এ mutex-ই যথেষ্ট ও নিরাপদ।
Lock-free কোড লেখা ভয়ংকর কঠিন এবং bug ধরা প্রায় অসম্ভব — যেমন ABA problem (মান A থেকে B হয়ে আবার A-তে ফিরে আসে, CAS ভাবে কিছুই বদলায়নি)। নিজে lock-free data structure লেখার আগে সবসময় পরীক্ষিত library (java.util.concurrent, Disruptor, folly) ব্যবহারের কথা ভাবো। ভুল memory ordering production-এ এমন bug দেয় যা একদিনে একবার দেখা দেয়।
বাস্তব উদাহরণ
LMAX exchange তাদের Disruptor দিয়ে একটি single-threaded business logic-এ মিলিয়ন মেসেজ/সেকেন্ড সামলায় — তাদের পুরো দর্শন হলো mechanical sympathy আর single-writer principle।
Linux kernel-এ RCU (Read-Copy-Update) একটি lock-free কৌশল যা lock ছাড়াই বিপুল read scalability দেয়।
গেমিং ইঞ্জিন (যেমন Unreal, multiplayer servers) lock-free queue দিয়ে network packet ও physics update পাইপলাইন করে, যাতে frame drop না হয়।
ইন্টারভিউতে lock-free নিয়ে প্রশ্ন এলে শুধু "এটা দ্রুত" বোলো না — বলো এর আসল সুবিধা হলো predictable latency আর deadlock-freedom। CAS-এর retry loop ব্যাখ্যা করতে পারলে, আর single-writer principle উল্লেখ করলে interviewer বুঝবে তুমি গভীরে গেছ। Disruptor-এর নাম জানা একটা strong plus।
মূল শব্দ (Key Terms)
মিনি কুইজ
1. একটি lock-free অ্যালগরিদম 'wait-free' হলে এর গ্যারান্টি কী?
2. Mutex-এর সবচেয়ে বড় latency সমস্যা কোনটি low-latency সিস্টেমে?
3. Single-writer principle কেন দ্রুত?