50 साल बाद, क्या Two-Phase Locking सबसे अच्छा है?

 (concurrencyfreaks.blogspot.com)
1 पॉइंट द्वारा GN⁺ 2023-10-01 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • 1976 में सार्वजनिक हुआ Two-Phase Locking(2PL) serializability से ज्यादा मजबूत Opacity देता है, लेकिन करीब 50 साल बाद भी read scalability और progress guarantee की सीमाएँ बनी हुई हैं
  • सरल lock acquire/release नियमों से multi-record transactions को संभालते हुए मजबूत isolation level देता है, इसलिए commercial transactional DBs और concurrent data structures में अब भी व्यापक रूप से इस्तेमाल होता है
  • पारंपरिक 2PL में mutual exclusion locks की वजह से reads आपस में भी टकरा सकते हैं, और reader-writer lock इस्तेमाल करने पर भी binary search tree के root जैसी जगहों पर, जहाँ reads इकट्ठा होते हैं, read-indicator contention पैदा होता है
  • 2PLSF reader-specific indicators को cache lines में फैला कर read lock acquisition contention घटाता है, और सिर्फ conflicted transactions पर central atomic counter का fetch_and_add() लागू करता है
  • No-Wait, Deadlock-detection, Wait-Or-Die जैसे 2PL variants live-lock या scalability समस्याएँ छोड़ते हैं, जबकि 2PLSF read scalability और starvation-free transactions दोनों को साथ में लक्ष्य बनाने वाला बेहतर variant है

2PL अब भी महत्वपूर्ण क्यों है

  • Two-Phase Locking(2PL) serializability देने वाले पहले general-purpose concurrency control mechanisms में से एक है, और असल में इससे भी मजबूत isolation level, Opacity, देता है
  • 2PL 1976 में Jim Gray और उनके साथियों के paper के जरिए सार्वजनिक हुआ था, और संभव है कि idea इससे पहले से मौजूद रहा हो, इसलिए इसे लगभग 50 साल पुरानी technique माना जाता है
  • General-purpose concurrency control उन algorithms को कहते हैं जो objects, records, tuples जैसे कई data items पर all-or-nothing semantics वाली transactions को संभव बनाते हैं
  • 2PL की खूबियाँ उसकी simplicity और strong isolation में हैं
    • record को read या write करने से पहले उस record की सुरक्षा करने वाला lock पहले acquire किया जाता है
    • transaction खत्म होने तक acquired locks को बनाए रखा जाता है, ताकि consistent view बन सके

सरल नियमों से बनने वाला isolation

  • 2PL में transaction के दौरान हर access पर lock acquire किया जाता है, और जब यह पता हो कि अब आगे कोई access नहीं होगा, यानी transaction के अंत में, सभी locks release किए जाते हैं
  • अंत के समय accessed data के सभी locks held होते हैं, इसलिए उस transaction के लिए linearization point बनता है
  • 50 साल पहले कई database researchers मानते थे कि record access पूरा करने के बाद lock तुरंत release किया जा सकता है, लेकिन ऐसा concurrency control serializable नहीं होता
  • ज्ञात commercial transactional databases 2PL या T/O, MVCC के साथ combinations इस्तेमाल करते हैं
  • concurrent data structures के क्षेत्र में linearizability लगभग standard है, और कई nodes पर consistently write करने के लिए आम तौर पर write access के लिए 2PL जैसी approach चाहिए होती है
    • exception lock-free data structures हैं, लेकिन सही lock-free implementation मुश्किल है—इस बात पर जोर दिया गया है

2PL की bottleneck: read scalability और live-lock

  • 2PL की बड़ी कमजोरी read scalability की कमी और live-lock progress guarantee है
  • Classical 2PL mutual exclusion locks के आधार पर design किया गया है, इसलिए अगर दो threads सिर्फ वही record read करें, तब भी conflict हो सकता है और एक या दोनों abort होकर restart हो सकते हैं
  • reader-writer lock में बदलने से reads के बीच conflict घटता है, लेकिन lock cost और memory usage बढ़ जाते हैं
    • mutual exclusion lock को locked/unlocked state दिखाने वाले 1 bit से implement किया जा सकता है
    • reader-writer lock को इस bit के अलावा, अभी read mode में lock रखने वाले readers की संख्या गिनने के लिए counter चाहिए
    • उदाहरण के लिए 7-bit counter अधिकतम 128 threads दिखा सकता है, और हर lock 1 byte ले सकता है
    • अगर database में अरबों records हों, तो केवल locks के लिए भी अरबों bytes की जरूरत हो सकती है
  • इससे भी बड़ी समस्या counter contention है
    • read-non-disjoint workloads में बहुत सारी reads एक ही data पर केंद्रित होती हैं
    • binary search tree का root node इसका प्रतिनिधि उदाहरण है, जिसे हर operation को नीचे के nodes में जाने से पहले read करना होता है
    • 2PL में root पर हर access के लिए lock acquisition चाहिए, और reader-writer lock इस्तेमाल करने पर भी root node lock पर भारी contention होता है

मौजूदा approaches और scalable read-indicator

  • TLRW Dave Dice और Nir Shavit द्वारा SPAA 2010 में पेश की गई approach है, जिसमें reader-writer lock का इस्तेमाल कर mutual exclusion lock से बेहतर performance मिली, लेकिन यह optimistic concurrency control जितनी तेज नहीं है
  • TLRW की तरह, अगर हर read access reader-writer lock के single variable पर contend करने वाला implementation Rank-based Relaxed AVL binary search tree पर लागू किया जाए, तो चाहे ज्यादातर write transactions हों या read transactions, scalability flat हो जाती है
  • read-indicator contention को scalable read-indicator से कम किया जा सकता है
    • पसंदीदा तरीका ऐसा reader-writer lock है, जिसमें हर reader अपना arrival और departure अलग cache line में mark करता है
    • read lock acquisition में contention खत्म हो जाता है
    • write lock लेने वाले thread को अनुमति है या नहीं यह जांचने के लिए सभी cache lines scan करनी पड़ती हैं, इसलिए write lock acquisition cost बढ़ जाती है
  • NUMA Aware reader-writer locks इस technique का इस्तेमाल करने वाले reader-writer lock algorithms पर बात करता है
    • तीन reader-writer lock algorithms में से दो high scalability रखते हैं, लेकिन starvation-free नहीं हैं

2PLSF का reader-writer lock design

  • Two-Phase Locking Starvation-Free(2PLSF) ऐसा concurrency control है, जो read lock acquisition में अच्छी scalability और अतिरिक्त गुणों वाले reader-writer lock से implement किया गया है
  • 2PLSF का reader-writer lock read-lock के लिए प्रति thread 1 bit reserve करता है
    • ये bits अपनी cache line में रखे जाते हैं
    • इन्हें adjacent locks के read-indicator bits के साथ रखा जाता है
  • NUMA-aware reader-writer lock paper की तरह, cost write lock acquisition की तरफ shift होती है
    • write lock को कई cache lines scan करनी पड़ती हैं
    • यह कोई जादुई समाधान नहीं, बल्कि trade-off है
  • यह trade-off इसलिए उपयोगी है क्योंकि ज्यादातर workloads read-heavy होते हैं, और write-intensive workloads भी record lookup चरणों आदि में काफी समय read access पर लगाते हैं
  • बेहतर reader-writer lock इस्तेमाल करने से read-non-disjoint workloads में भी 2PL scale कर सकता है, लेकिन live-lock समस्या अलग से हल करनी होगी

2PL variants में बची progress guarantee समस्याएँ

  • Classical 2PL में contention handling के तरीके के आधार पर No-Wait, Deadlock-detection, Wait-Or-Die जैसे प्रमुख variants हैं

  • No-Wait

    • conflict होने पर अपनी transaction या दूसरी transaction को abort करके फिर try किया जाता है
    • retry तुरंत हो सकता है या exponential backoff के जरिए बाद में
    • अगर record A के बाद B modify करने वाली transaction और B के बाद A modify करने वाली transaction लगातार conflict करती रहें, तो दोनों commit न कर पाने के बावजूद abort-restart दोहराती रह सकती हैं, इसलिए इसमें live-lock progress होता है

  • Deadlock-detection

    • lock पर waiting threads की list रखी जाती है और cycle, यानी deadlock, detect किया जाता है
    • reader-writer lock में हर reader की अपनी list होनी चाहिए, और हर list की सुरक्षा के लिए mutual exclusion lock भी चाहिए
    • read-lock mode में lock लेते समय सभी reader lists scan करनी पड़ती हैं, इसलिए cost बढ़ जाती है
    • सिद्धांततः starvation-free संभव हो सकता है, लेकिन इसके लिए starvation-free lock चाहिए और public high-scalability starvation-free reader-writer lock उपलब्ध नहीं है, इसलिए यह लक्ष्य से टकराता है
    • हर reader के लिए list रखने से memory usage भी बढ़ सकता है

  • Wait-Or-Die

    • सभी transactions को order दिया जाता है, और lock conflict होने पर transaction timestamp और lock owner timestamp की तुलना कर wait या abort तय किया जाता है
    • mutual exclusion lock में owner को lock के अंदर unique thread identifier के रूप में store किया जा सकता है, इसलिए यह अच्छी तरह काम करता है
    • reader-writer lock में वही तरीका अपनाने के लिए हर reader के लिए thread-id चाहिए
    • 256 threads support करने के लिए 8 bits × 256 = 256 bytes हर reader-writer lock के लिए चाहिए

Central atomic counter bottleneck और 2PLSF का फर्क

  • Wait-Or-Die की बड़ी बाधा यह है कि हर transaction के पास unique transaction ID होना चाहिए
    • उदाहरण के लिए central atomic variable से fetch_and_add() के जरिए number लेकर order बनाया जा सकता है
  • आधुनिक CPUs में से अधिकांश पर contended atomic variable के लिए प्रति सेकंड 40 million से ज्यादा fetch_and_add() करना मुश्किल है
    • Visa के प्रति दिन लगभग 660 million transactions से तुलना करें तो यह बड़ा लग सकता है
    • in-memory DBMS या concurrent data structures में यह पर्याप्त बड़ा नहीं हो सकता
    • एक test machine पर प्रति सेकंड 20 million fetch_and_add() पार करना मुश्किल था
  • यह fetch_and_add() केवल write transactions ही नहीं, read transactions समेत सभी transactions के लिए चाहिए—यही scalability को सीमित करता है
  • TL2 में read transactions atomic fetch_and_add() नहीं करतीं और optimistic reads करती हैं
    • read transactions के हिसाब से यह सैकड़ों millions tps तक scale कर सकता है
    • दूसरी तरफ Wait-Or-Die आधारित 2PL 40M tps/sec से ऊपर नहीं जा सकता
  • 2PLSF केवल उन transactions को order करता है जो conflict में जाती हैं
    • central atomic variable पर fetch_and_add() करने वाली transactions की संख्या घटती है
    • conflict-free transactions 40M tps plateau में बंधी नहीं रहतीं
    • उदाहरण के लिए, 200M tps बिना conflict चल सकते हैं और केवल conflict में मौजूद 40M tps fetch_and_add() limit में बंध सकते हैं
    • algorithm starvation-freedom देता है

Materials और अंतिम मूल्यांकन

  • 2PLSF algorithm खुद विस्तार से नहीं समझाया गया है, लेकिन starvation-free algorithms के हिसाब से इसे अपेक्षाकृत सरल माना गया है
  • reference materials के रूप में paper और source code उपलब्ध हैं
  • 2PLSF ACM paper से भी जुड़ा है, और इसे Pedro Ramalhete, Andreia, Pascal Felber द्वारा बनाया गया algorithm बताया गया है
  • 2PLSF का लक्ष्य उन गुणों के करीब है जो 2PL में शुरुआत से होने चाहिए थे
    • read-non-disjoint स्थितियों में, जहाँ reads overlap करती हैं, यह अच्छी तरह scale करता है
    • blocking progress का सबसे ऊँचा रूप, starvation-free transactions, देता है
    • कुछ conflict स्थितियों में भी scalability रख सकता है
  • 2PLSF perfect नहीं है, लेकिन conflict resolution के मामले में इसे TL2 से बेहतर माना गया है, और मौजूदा 2PL से इसका फर्क pickaxe और jackhammer के फर्क से तुलना किया गया है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-10-01
Hacker News की राय
  • मैं इस विषय में नया हूँ, लेकिन यह दिलचस्प है, और काश कोई ऐसा consistency solution होता जिसे deploy करना आसान हो
    distributed microservices architecture में कई data stores को sync करने या “consistent” बनाए रखने के लिए industry best practice क्या है, यह जानना चाहता हूँ
    कुछ दिन पहले मैंने “settled timestamp” से inconsistency की समस्या हल करने की कोशिश की थी; यह multi-version तरीके जैसा है, जिसमें अगर बिना error report के समय बीत जाए तो उसे valid save/commit माना जाता है। two-phase commit में मानो दूसरा phase समय हो
    तरीका यह था कि दूसरे server की clock को monitor किया जाए, और अगर वह update न हो तो उस server के settled timestamp पर भरोसा न किया जाए; हर update पर response का इंतज़ार करने के बजाय सिर्फ़ अगले timestamp interval का इंतज़ार करना पड़े, इसलिए मकसद consistency को बहुत सारे servers तक scale करना था
    मैंने non-determinism test करने के लिए multi-threaded और multi-processing Python code बनाया, जिसमें 10 threads random updates आपस में भेजते हैं: https://replit.com/@Chronological/InconsistencySimulation#ma...
    इस simulation में read, सभी servers द्वारा report किए गए timestamps के पूरे set का minimum होता है, और 10 सेकंड बाद हर thread से counter value पूछने पर कभी-कभी सभी वही value देते हैं, लेकिन काफ़ी बार split-brain state बन जाती है
    मुझे पता है कि distributed systems में wall clock timestamp ordering तय करने के लिए ठीक नहीं होते, और logical clocks या vector clocks इस्तेमाल करने चाहिए
    अच्छा होगा अगर किसी भी समय simulation को ऐसा बनाया जा सके कि सब वही number report करें। Bloomlang eventual consistency में देर से आने वाली values के result को प्रभावित करके linearizable न रहने वाली समस्या हल करने की कोशिश करता है
    खास तौर पर consistency बनाए रखते हुए scale करने में रुचि है, लेकिन यह काफ़ी कठिन समस्या लगती है
    • industry best practice यह है कि distributed microservices architecture का इस्तेमाल न किया जाए
    • distributed systems का core idea यह है कि एक central write-order journal हो जिसे हर node replay करे
      कई systems central journal में sequentially write करते हैं, और journal key-value store की तरह requests लेता है। वह journal सभी nodes पर replicate होता है, और nodes journal पढ़कर requested complex logic execute करते हैं
    • यह फिर से आकलन करना अच्छा होगा कि क्या सच में (a) distributed data store और (b) synchronous consistency, दोनों की ज़रूरत है। इनमें से किसी एक को छोड़ देने पर चीज़ें बहुत सरल हो जाती हैं
    • मुझे लगता है कि 5 साल के अंदर TigerBeetle DB consistent, high-throughput और fault-tolerant distributed database का industry standard बन जाएगा
    • Raft protocol देखिए। आम तौर पर protocol layer में सीधे integrate करने की कोशिश करने के बजाय, जिन coordination/data को serializable होना चाहिए उनके लिए Raft implement करने वाले etcd जैसे consistent store का इस्तेमाल standard तरीका है
      Kubernetes etcd इस्तेमाल करता है, इसलिए strong consistency वाले key-value store के रूप में यह काफ़ी अच्छी तरह scale करता है
      आपने “कई data stores” कहा है, इसलिए मान रहा हूँ कि heterogeneous data है और CockroachDB जैसे विकल्प लागू नहीं हैं
      अगर आप beginner हैं तो खुद बनाना जोखिम भरा है। https://aphyr.com/ testing के benchmark जैसी resource है और learning के लिए भी शानदार है। Jepsen से distributed systems test किए जा सकते हैं, लेकिन बेहतर है कि Kyle द्वारा robust दिखाए गए data stores का इस्तेमाल किया जाए
  • जिज्ञासा है कि यह नया approach Serializable Snapshot Isolation (SSI) से कैसे compare होता है: https://wiki.postgresql.org/wiki/SSI
    मैं इन techniques से बहुत परिचित नहीं हूँ, लेकिन databases पढ़ते समय SSI को future के “बेहतर” two-phase locking की तरह introduce किया गया था। जानना चाहता हूँ कि SSI, 2PLSF से कैसे अलग है, और यहाँ इसका ज़िक्र क्यों नहीं हुआ
    • मैं एक नए platform का memory model बना रहा हूँ, और लगभग सब कुछ copy-on-write, snapshots और SSI के इर्द-गिर्द design कर रहा हूँ
      लेकिन distributed effects में अब भी locks, two-phase transactions वगैरह चाहिए। निजी तौर पर मैं इन्हें विकल्प नहीं, बल्कि एक-दूसरे को complement करने वाली capabilities मानता हूँ
  • locking algorithms बेहतरीन हैं, लेकिन apply करने से पहले एक कदम पीछे हटकर सोचना ज़रूरी है कि क्या सच में बहुत सारे threads को उसी resource के लिए लड़ना चाहिए
    in-memory data structure हो तो यह natural है, लेकिन external database या किसी दूसरे shared external resource से deal कर रहे हों तो बेहतर तरीका हो सकता है
    अक्सर requests को batch process करके external resource को कम concurrency और बड़े payloads के साथ access किया जा सकता है। अगर वह resource batches को अच्छी तरह handle करता है, तो ज़रूरी concurrency और locking बहुत घट जाती है
    उदाहरण के लिए Postgres इस्तेमाल कर रहे हों तो connections की संख्या घटती है, और complexity बढ़ाने वाले PgBouncer को add न करना पड़े
    हालांकि request batching ज़्यादातर programming languages के साथ अच्छी तरह fit नहीं होती। Go के channels या Elixir के processes जैसी high concurrency के लिए optimized languages इसे अच्छी तरह कर सकती हैं, लेकिन जहाँ हर चीज़ threads से handle होती है वहाँ यह दर्दनाक हो सकता है
  • लेखक जिस 2PLSF paper में दावा करता है कि 2PL मूल रूप से ऐसा होना चाहिए था: https://zenodo.org/record/7886718
  • HN पर आने वाले सभी links के लिए HTTPS links की नई policy सच में चाहिए
    • क्यों? बहुत सारी पुरानी उपयोगी sites हैं जो HTTP पर भी ठीक काम करती हैं। अगर बात उन cases की है जहाँ site HTTPS support करती है लेकिन HTTP link submit होता है, तो सहमत हूँ
    • अगर कोई site purely read-only interaction के लिए है, तो HTTPS की जगह HTTP link visit करने से क्या नतीजा होता है, यह जानना चाहता हूँ। यह security issue है या privacy issue?
    • Firefox को HTTPS-only mode में चला सकते हैं: https://support.mozilla.org/en-US/kb/https-only-prefs
      जिन sites को HTTPS में upgrade नहीं किया जा सकता वहाँ warning आती है, और जो दोनों support करती हैं वे सीधे HTTPS version पर चली जाती हैं
    • concurrency algorithms पर article पढ़ने के बाद आपके दिमाग़ में यही unrelated observation आया?
      और अगर HTTP link अच्छे concurrency algorithm के बारे में है, तो मैं फिर भी पढ़ूँगा
    • अभी भी कुछ HTTP-only websites बची हुई हैं
  • Wait-Or-Die में transaction ID पाने के लिए सच में fetch_and_add चाहिए? मुझे तो यह भी संदेह है कि शुरू से transaction ID की ज़रूरत है या नहीं

लक्ष्य ऐसा लगता है कि सक्रिय transactions के बीच कोई मनमाना लेकिन consistent क्रम रखा जाए, ताकि conflict होने पर वे आपस में सहमत हो सकें कि कौन wait करेगा और कौन खत्म होगा। तो क्या thread ID इस्तेमाल नहीं कर सकते?
random number भी संभव हो सकता है। tie को “death” की तरह handle करें तो worst case में दोनों तरफ के transactions बेवजह abort होंगे और बस नए random number के साथ retry करेंगे
इसका ज़िक्र नहीं है, लेकिन लगता है मकसद पुराने transactions को प्राथमिकता देना है ताकि लंबे समय तक चलने वाले transactions छोटे transactions की वजह से starve न हों। उदाहरण के लिए, अगर एक long transaction औसतन तीन short transactions से टकराता है, और हर conflict में winner असल में random है, तो long transaction के तीनों बार जीतकर commit करने की संभावना केवल 1/8 है
लेकिन starvation रोकने के लिए हर बार पुराने transaction को प्राथमिकता देना ज़रूरी नहीं; ज़्यादातर मामलों में ऐसा होना काफी है। खासकर तब, जब वह बस बहुत थोड़ा-सा ही पुराना हो
इसलिए threads के बीच clock skew या दूसरी inaccuracies होने पर भी timestamp या cycle counter जैसी चीज़ ठीक से काम कर सकती है। tie को thread ID से तोड़ा जा सकता है, या फिर दोनों को abort करा सकते हैं

  • thread ID के बजाय मैं ULID इस्तेमाल करूंगा: https://github.com/ulid/spec
    यह ऐसे case और कई दूसरे cases में अच्छी तरह fit बैठता है
  • 2-phase approach और Paxos की तुलना का frame देने वाला बेहतरीन paper है: https://lamport.azurewebsites.net/video/consensus-on-transac...
    • नाम मिलते-जुलते हैं, लेकिन 2-phase locking 2-phase commit से अलग है
      2-phase commit की तुलना Paxos से की जा सकती है, और दोनों consensus protocols की category में आते हैं
      2-phase locking concurrency control mechanism है
  • यह हमेशा चलता रहता है, और कभी बिल्कुल perfect भी नहीं होता
    जब पहला lock message गायब हो जाए, तो आप कैसे जानेंगे कि खोया हुआ message response message नहीं था?
    साधारण cases में GitHub या Dropbox की तरह बस आगे बढ़ सकते हैं और बाद में conflicts handle कर सकते हैं। database हो तो किस्मत अच्छी चाहिए, और bank हो तो और भी ज़्यादा
  • relaxed AVL tree का आखिरी figure मुझे ठीक से समझ नहीं आया। 100% reads वाले सबसे दाएं हिस्से में TL2 algorithm को threads की संख्या के साथ linearly scale करना चाहिए ऐसा लगता है
    read-only transaction में TL2 global version को sample करने के बाद, सभी reads के लिए बस यह check कर सकता है कि local version sampled version से कम या बराबर है या नहीं
    तो यह समझना मुश्किल है कि graph linear से कम क्यों है, और TL2 दूसरी STM implementations जितना तेज़ क्यों नहीं है
    • TL2 के लिए ऐसा graph नहीं दिख रहा। इसके बजाय TLRW graph दिख रहा है, और TLRW reader lock इस्तेमाल करता है, इसलिए उसकी scalability limit है
  • randomized queue जोड़ने से यह simple तरीके से solve हो सकता है
    उदाहरण के लिए मान लें आम तौर पर 1000 tasks और 10~100 hardware threads हैं
    1000 tasks की एक sorted list बनाएं, हर thread के लिए उसकी copy बनाएं, और हर बार copy का order randomize करें
    फिर हर thread अपनी list पढ़कर tasks execute कर सकता है, और non-blocking multi-threaded queue के रूप में implement की गई एक list को subscribe कर सकता है
    worst case में कुछ threads कोई task बार-बार कर सकते हैं
    इस approach से atomic operations 1000 गुना तक scale हो सकते हैं