डेटाबेस की बुनियाद

 (tontinton.com)
5 पॉइंट द्वारा GN⁺ 2023-12-16 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • एक साधारण Bash key-value store से शुरू करके, यह चरण-दर-चरण दिखाता है कि वास्तविक databases को durability, atomicity, isolation और performance को अलग design problems के रूप में क्यों संभालना पड़ता है
  • fsync/fdatasync, flock, और WAL failures व concurrency की स्थितियों में data बचाने के बुनियादी tools हैं, लेकिन guarantee का स्तर बढ़ाने पर performance cost बढ़ती जाती है
  • Storage engines disk I/O और seek cost घटाने के लिए B-tree और LSM tree जैसी structures का उपयोग करते हैं, और इनके साथ vacuum व compaction जैसी maintenance भी आती है
  • Distributed databases availability और horizontal scaling पाने के बदले CAP theorem, network partition, consistency tuning और conflict resolution जैसी distributed systems complexity स्वीकार करते हैं
  • Database चुनते या implement करते समय ACID guarantees, isolation level, storage structure, replication method और consistency requirements को workload के हिसाब से tune करना चाहिए

bashdb से सामने आने वाली database की बुनियादी समस्याएँ

  • bashdb दो Bash functions से बना एक simple key-value store है
    • db_set key,value format में file में append करता है
    • db_get grep, sed, tail को मिलाकर last value पढ़ता है
  • सीखने के लिए यह simple है, लेकिन सिर्फ इसी implementation से भी production database को हल करनी पड़ने वाली समस्याएँ सामने आ जाती हैं
    • Durability: db_set की सफलता के बाद अगर machine crash हो जाए, तो disk पर flush न हुआ data गायब हो सकता है
    • Atomicity: write के दौरान crash होने पर data का सिर्फ कुछ हिस्सा record होकर corrupt हो सकता है
    • Isolation: अगर पढ़ना और लिखना एक साथ उसी item को access करें, तो reader को केवल partial data दिख सकता है
    • Performance: db_get पूरी file को line-by-line search करता है, इसलिए यह O(n) है

ACID और bashdb को सुधारने की कोशिश

  • ACID उन properties का acronym है जिन्हें कई databases guarantee करना चाहते हैं
    • Atomicity: write के दौरान failure आए तो पूरी transaction cancel या rollback की जाती है, ताकि partial write state न बचे
    • Consistency: illegal transaction से database damage नहीं होना चाहिए
    • Isolation: उसी data पर concurrent access में race condition नहीं होनी चाहिए
    • Durability: successful writes power failure जैसी स्थितियों के बाद भी बनी रहनी चाहिए
  • सभी database transactions के लिए ACID guarantee देना जरूरी नहीं है, और कुछ use cases में performance के लिए guarantees कम की जा सकती हैं

  • Durability और fsync

    • write system call buffer को file में लिखता है, लेकिन इसका मतलब यह नहीं कि वह तुरंत non-volatile storage में record हो गया है
    • Kernel buffer को page cache में dirty page के रूप में store करके बाद में disk पर flush कर सकता है
    • Disk device या RAID system के पास भी अलग write cache हो सकता है
    • fsync और fdatasync dirty pages को persistent storage में flush करने के system calls हैं
    • fdatasync write द्वारा दिए गए raw buffer को flush करता है
    • fsync data के साथ-साथ mtime जैसे file metadata को भी flush करता है
    • db_set के बाद sync -d database जोड़ने से fdatasync जैसा behavior देकर durability बढ़ाई जा सकती है, लेकिन आमतौर पर sync खुद write से धीमा होता है, इसलिए performance घटती है
    • fsync() की सफलता का मतलब है “last fsync के बाद की सभी writes disk तक पहुँच गई हैं”, न कि सिर्फ “last successful fsync के बाद की writes”
    • PostgreSQL ने 2018 में यह समस्या झेली थी, और fsync failure पर retry करने के बजाय panic करने के तरीके में behavior बदला
    • यह घटना fsyncgate के नाम से जानी गई, और संबंधित सामग्री के रूप में fsync failures paper जुड़ा है
    • MongoDB में by default writes हर 100ms पर sync होती हैं, इसलिए यह 100% durable नहीं है

  • Isolation और flock

    • bashdb में सबसे simple multi-process isolation तरीका यह है कि storage file को पढ़ने या लिखने से पहले lock लगाया जाए
    • Linux का flock files को lock करता है, और -s flag इस्तेमाल करने पर shared lock के रूप में कई readers एक साथ पढ़ सकते हैं
    • सुधरा हुआ bashdb writes के लिए exclusive lock और reads के लिए shared lock का उपयोग करता है
    • कमी यह है कि हर write पर पूरा database lock हो जाता है
    • सिर्फ Bash से atomicity को आसानी से guarantee करना मुश्किल है, और mv -T या rename का उपयोग करने की संभावना है, लेकिन इसे पूरा नहीं किया गया
    • bashdb अब भी O(n) lookup problem हल नहीं करता

Storage engine की भूमिका और bottlenecks

  • Storage engine persistent storage में data पढ़ने और लिखने का abstraction देता है, और इसका मुख्य लक्ष्य high throughput व low latency है
  • सबसे बड़ी constraint खुद disk की speed differences से आती है
    • example latency table में L1 cache reference लगभग 0.5ns, SSD से 4KB random read 150,000ns, और disk seek 10,000,000ns बताया गया है
    • अगर L1 cache reference को दिल की धड़कन के करीब 0.5 seconds मानें, तो SSD से 1MB sequential read करीब 12 days, और disk से 1MB sequential read करीब 8 months के बराबर होगा
  • इसलिए storage engine design disk I/O और disk seek को जितना हो सके कम करने की दिशा में विकसित हुआ है
  • सामान्य storage engine design elements ये हैं
    • Disk पर items store करने के लिए basic data structure
    • ACID transactions
    • Disk reads घटाने के लिए cache
    • SQL, document, graph जैसे API layers
  • Storage engine data structures को मोटे तौर पर mutable structures और immutable structures में बाँटा जा सकता है
    • Mutable structure file में लिखे data को बाद में overwrite कर सकता है
    • Immutable structure file में लिखे data को केवल दोबारा पढ़ता है

Mutable B-tree

  • Data बढ़ने पर भी अच्छी performance बनाए रखने के लिए bashdb की तरह linear search नहीं, बल्कि maximum logarithmic time में item खोज पाना चाहिए
  • BST में O(log n) lookup संभव है, लेकिन अगर nodes disk पर एक-दूसरे से दूर हों, तो traversal के दौरान disk seek बहुत बढ़ सकते हैं
  • B-tree, BST का generalization है जिसमें एक node के दो से ज्यादा children हो सकते हैं, और यह spatial locality का उपयोग करता है
    • Disk से आमतौर पर 4KB या 8KB page पढ़ने के बाद, उसके अंदर के कई nodes को memory और CPU cache में sequentially compare किया जाता है
    • Memory और CPU cache access disk से कई orders of magnitude तेज होते हैं, इसलिए disk से पढ़े गए bytes का ज्यादा से ज्यादा उपयोग करना महत्वपूर्ण है
  • Sequential memory access SIMD, instruction pipelining और prefetching की वजह से बहुत शक्तिशाली हो सकता है
  • B+ tree सिर्फ leaf nodes में values store करता है और बाकी nodes में केवल keys रखता है, जिससे disk page में अधिक keys compare की जा सकती हैं

  • Space reclamation और vacuum

    • B-tree को space optimization के लिए data fragmentation से बनी खाली जगह reclaim करनी पड़ती है
    • बड़े value से update करने पर अगले node का data overwrite हो सकता है, इसलिए item को किसी दूसरी location पर move करना पड़ता है और original page में hole बन जाता है
    • छोटे value से update करने पर अंत में hole बच जाता है
    • Delete करने से deleted value की जगह पर hole बनता है
    • इस तरह की space reclamation और page rewriting process को vacuum, compaction, page defragmentation, maintenance आदि कहा जा सकता है
    • आमतौर पर user request latency spikes से बचने के लिए इसे background में चलाया जाता है
    • PostgreSQL में auto vacuum daemon configure किया जा सकता है
    • B-tree अक्सर indexes की underlying data structure के रूप में इस्तेमाल होता है, जैसे PostgreSQL का default index; और DynamoDB को मजाक में “distributed B-tree” कहा गया एक उदाहरण भी है

अपरिवर्तनीय LSM tree

  • LSM tree एक append-only डेटा स्ट्रक्चर है, जिसका विचार इस बात से शुरू होता है कि disk seek महंगा होता है
  • अगर डेटा को सिर्फ फाइल के अंत में जोड़ा जाए, तो disk head को अगली write position तक बहुत दूर जाने की जरूरत कम पड़ती है, और यह write-heavy workloads के लिए फायदेमंद होता है
  • Log Structured Merge tree, संक्षेप में LSM tree, RocksDB, Cassandra, ScyllaDB जैसे आधुनिक database storage engines में इस्तेमाल होता है
  • इसका मूल व्यवहार इस प्रकार है
    • writes को memory में मौजूद sortable डेटा स्ट्रक्चर में buffer किया जाता है
    • उदाहरण हैं AVL tree, Red Black tree, Skip List
    • एक तय capacity पर पहुंचने पर इन्हें sorted file, यानी Sorted String Table या SSTable, में flush किया जाता है
  • SSTable sorted data को store करता है, जिससे binary search और sparse index के जरिए disk I/O कम किया जा सकता है
  • durability के लिए, memory में लिखे गए operations Write-Ahead Log, यानी WAL, में record किए जाते हैं
    • program शुरू होते समय WAL पढ़कर shutdown या crash से पहले वाली state restore की जाती है
  • delete भी सामान्य write की तरह append होता है, और value की जगह tombstone store करता है
    • tombstone compaction प्रक्रिया में हटाया जाता है

  • LSM tree में read और compaction

    • LSM tree में read पहले memory डेटा स्ट्रक्चर में खोजता है; अगर नहीं मिलता, तो disk पर SSTables को सबसे नए file से पुराने file के क्रम में scan करता है
    • writes बढ़ने पर जिन SSTables को check करना पड़ता है, उनकी संख्या बढ़ती है
    • भले ही हर file sorted हो, कई छोटी files को scan करना एक बड़ी file देखने से धीमा हो सकता है
    • comparison expression log(num_files * table_size) < num_files * log(table_size) है
    • compaction एक background operation है, जो कई छोटे SSTables को एक बड़े SSTable में merge करता है और tombstone हटाता है
    • RocksDB Leveled Compaction implement करता है
    • नया flush किया गया SSTable level 0 में रखा जाता है
    • जब किसी level में configured संख्या में files जमा हो जाती हैं, तो compaction के बाद नई file को अगले level पर promote किया जाता है
    • tombstone removal सावधानी से करना चाहिए
    • deleted item के पुराने files के साथ compaction में फिर से जीवित हो जाने की data resurrection समस्या हो सकती है
    • RocksDB tombstone को अंतिम level पर promote होने वाली compaction तक बनाए रखता है
    • Rust में वास्तविक उदाहरण dbeel का LSM tree code से link किया गया है

  • Bloom filter

    • Bloom filter एक probabilistic set डेटा स्ट्रक्चर है, जिससे कुशलता से जांचा जा सकता है कि कोई item किसी set में नहीं है
    • lookup result दो प्रकार के होते हैं
      • false: item निश्चित रूप से set में नहीं है
      • true: item set में हो सकता है
    • Bloom filter कई hash functions के results को bitmap में bit positions पर map करके उन्हें 1 पर set करता है
    • space complexity को सामान्य set के O(n) के विपरीत O(log n) के रूप में प्रस्तुत किया गया है
    • bitmap memory ज्यादा allocate करके और hash functions की संख्या बढ़ाकर “नहीं है, यह निश्चित मानने की probability” adjust की जा सकती है; एक calculator भी उपलब्ध है
    • LSM tree हर SSTable के लिए Bloom filter store करता है, जिससे उन SSTables की search skip की जा सकती है जिनमें किसी specific key के न होने की पुष्टि हो चुकी है

WAL और transaction guarantees

  • WAL अचानक crash से बचने के लिए सभी transaction operations को एक special file में record करने का तरीका है
  • database process शुरू होने पर WAL file पढ़ी जाती है और data state को reconstruct किया जाता है
    • जिन transactions का commit log नहीं है, उन्हें skip किया जाता है, जिससे atomicity मिलती है
  • अगर user को response देने से पहले write request का data WAL में record और flush कर दिया जाए, तो startup के समय उसे अवश्य पढ़ा जा सकता है, जिससे durability मिलती है
  • WAL को transaction events के लिए event sourcing का एक रूप माना जा सकता है

isolation levels और concurrency control

  • isolation हासिल करने के तरीके broadly तीन हिस्सों में बंटते हैं
    • pessimistic lock: जिस data पर अभी write हो रहा है, उस तक access रोकता है
    • optimistic lock: data copy को modify करने के बाद, transaction के दौरान original नहीं बदला हो तभी commit करता है; वरना retry करता है
    • MVCC: data को overwrite करने के बजाय नया version बनाता है, ताकि हर user किसी specific point-in-time का snapshot देखे
  • हर application को पूर्ण isolation, यानी serializable isolation, की जरूरत नहीं होती
  • ANSI/ISO SQL 92 उन परिणामों को तीन categories में बांटता है जो transaction के दौरान किसी अन्य transaction द्वारा वही data बदलने पर हो सकते हैं
    • Dirty read: किसी दूसरे transaction का ऐसा update पढ़ना जो अभी commit नहीं हुआ है
    • Non-repeatable read: उसी row को दो बार पढ़ने के बीच कोई दूसरा transaction commit कर देता है और value बदल जाती है
    • Phantom read: उसी condition वाली rows के set को दो बार पढ़ने के बीच row add या remove हो जाती है
  • ANSI/SQL 92 isolation levels, उच्च से निम्न क्रम में, इस प्रकार हैं
    • Serializable: केवल committed data पढ़ता है, और range-based multi-row writes तक शामिल करते हुए phantom read से बचता है
    • Repeatable reads: phantom read की अनुमति होती है
    • Read committed: non-repeatable read की अनुमति होती है
    • Read uncommitted: dirty read की अनुमति होती है
  • ऊंचे isolation levels आम तौर पर performance की कीमत पर आते हैं
  • ANSI/SQL 92 isolation levels की अपूर्ण होने के लिए आलोचना की जाती है
    • कई MVCC implementations serializable isolation के बजाय snapshot isolation देते हैं
    • तेज serializable MVCC algorithm के रूप में HyPer recommended है

distributed systems की जरूरत और CAP

  • distributed systems बहुत complexity जोड़ते हैं, इसलिए जब non-distributed solution पर्याप्त हो, तो इन्हें avoid करना चाहिए
  • data को कई machines में distribute करने के आम तौर पर दो कारण होते हैं
    • availability (Availability): database machine crash हो जाए या user से connection टूट जाए, तब भी request को दूसरी machine पर भेजा जा सकता है
    • horizontal scaling (Horizontal Scaling): किसी बड़े single machine तक scale करने वाली vertical scaling के बजाय, network से जुड़ी कई machines को एक की तरह काम कराना
  • distributed systems operational complexity और network partition की समस्या introduce करते हैं
  • CAP theorem कहता है कि system निम्न तीन में से केवल दो guarantees दे सकता है
    • Consistency: read को सबसे recent write मिलता है
    • Availability: failure की परवाह किए बिना सभी requests सफल होती हैं
    • Partition Tolerance: nodes के बीच message loss या delay होने पर भी system चलता रहता है
  • single-machine database में network partition नहीं होता और वह consistent होता है, लेकिन machine failure पर नई requests fail हो जाती हैं, जिससे availability violate होती है
  • अगर दो machines के पास अलग CPU, memory और disk हों और वे cable से जुड़ी हों, तो failure situation में choices बंट जाती हैं
    • requests cancel करने पर availability sacrifice होती है और consistency बनी रहती है
    • केवल working machine पर requests process करते रहने पर consistency sacrifice होती है और availability बनी रहती है
  • जो systems consistency sacrifice करके बाद में reconcile करते हैं, उन्हें eventually consistent कहा जाता है
  • network partition cluster में बिखरे data को इकट्ठा करना जरूरी बना देता है, इसलिए efficient JOIN भी मुश्किल हो जाता है; इसे कम करने के लिए NoSQL समुदाय denormalization की सलाह देता है

Replication और Amazon Dynamo का उदाहरण

  • Amazon का मूल Dynamo paper amazon.com के shopping cart में consistency की तुलना में availability को अधिक महत्वपूर्ण मानने के उदाहरण के रूप में पेश किया जाता है
    • अगर उपयोगकर्ता को cart में वही product दो बार दिखे, तो वह एक को हटा सकता है
    • यह खरीदारी ही न कर पाने की स्थिति से बेहतर माना गया
  • availability पाने के लिए सिर्फ यह काफी नहीं कि कई nodes डेटा को बांटकर रखें; हर item की कम-से-कम एक copy भी होनी चाहिए
  • item की copy store करने वाला node replica होता है, और copy करने की प्रक्रिया replication कहलाती है
  • replicas की संख्या बढ़ाने से availability बढ़ती है, लेकिन copies store करने के लिए अधिक resources चाहिए होते हैं
  • डेटा copies को पूरा-का-पूरा store करने के बजाय erasure coding से बांटकर कई nodes में फैलाया भी जा सकता है, और इससे जुड़ी latency characteristics के लिए erasure coding लेख लिंक किया गया है

Consistent Hashing और डेटा placement

  • जब कई nodes हों, तो यह तय करने के लिए load balancing या data partitioning की जरूरत होती है कि storage request किस node द्वारा handle की जाएगी
  • एक सरल तरीका है primary key को hash करके nodes की संख्या से modulo करना
    • node add या remove होने पर len(nodes) बदल जाता है, इसलिए वही key किसी दूसरे node की ओर point करती है
    • इस स्थिति में लगभग सभी items migrate करने पड़ते हैं, जिसकी cost ज्यादा होती है
  • Consistent Hashing nodes को array में नहीं बल्कि ring पर रखता है, जिससे node add/remove होने पर move होने वाले items की संख्या कम हो जाती है
    • इसका उपयोग Dynamo और Cassandra जैसे databases में होता है
  • Consistent hashing में node name का hash ring पर रखा जाता है, और request key के hash के बाद मिलने वाला node owner बनता है
  • replica selection ring पर counter-clockwise चलते हुए next node में copy store करने के तरीके से किया जा सकता है
    • अगर owner node down हो जाए, तो replica node request handle करके availability बनाए रखता है
    • इस तरीके को Leaderless Replication कहा जाता है, और Cassandra जैसे Dynamo-style databases में इसका उपयोग होता है
  • node add होने पर move होने वाली keys की संख्या औसतन num_keys / num_nodes होती है
  • virtual node एक physical node को ring पर कई बार रखता है, जिससे कुछ nodes के अधिक items own करने की संभावना कम होती है
    • उदाहरण के तौर पर node name में "half-0", "half-1" की तरह index को suffix के रूप में जोड़ा जाता है
  • leader node और replica node चुनने का एक दूसरा तरीका leader election है, लेकिन यहाँ उस पर चर्चा नहीं की गई है

Leaderless Replication और consistency tuning

  • leaderless configuration high availability पाने के बदले consistency की कुर्बानी देती है
  • अगर owner node write request के समय down हो, तो write replica पर होता है, और owner node फिर से up होने के बाद read request में stale data पढ़ा जा सकता है
  • अगर किसी खास request में consistency चाहिए, तो read request कई replicas और owner node को parallel में भेजी जाती है, और client सबसे नया डेटा चुनता है
  • write request आमतौर पर सभी replicas को parallel में भेजी जाती है, लेकिन केवल कुछ nodes के acknowledgement का इंतजार किया जाता है
  • request level पर consistency tune करने के लिए R + W > N/2 + 1 verify किया जाता है
    • N: डेटा copy रखने वाले nodes की संख्या
    • W: write success के लिए acknowledgement देने वाले nodes की संख्या
    • R: read success के लिए response देने वाले nodes की संख्या
  • W या R का N/2 + 1 होना majority-node request है और इसे quorum कहा जाता है

  • Conflict Resolution

    • सबसे नई write चुनने की प्रक्रिया Conflict Resolution है
    • केवल timestamp compare करना distributed systems में भरोसेमंद नहीं होता
    • हर machine की अपनी hardware clock होती है, और clocks पूरी तरह accurate नहीं होतीं, इसलिए drift होता है
    • NTP अधिक accurate time source से समय लेता है, लेकिन request खुद network से गुजरती है, इसलिए response आने में लगा समय ठीक-ठीक पता नहीं लगाया जा सकता
    • Cassandra timestamp का उपयोग करता है, और संबंधित documentation Cassandra data versioning पर लिंक है
    • Google Spanner ने खास high-precision time hardware और timestamp uncertainty range expose करने वाली API के जरिए clock-based consistency guarantees हासिल किए, और संबंधित paper Spanner paper है
    • Dynamo जैसे systems Version Vectors से कुछ conflicts कम करते हैं
    • हर item version के साथ (node, counter) pair जोड़कर versions के बीच causal relationship खोजी जाती है
    • निश्चित रूप से अधिक नया version खोजकर कुछ पुराने values हटाए जा सकते हैं
    • अधिक विस्तृत material के लिए Dotted Version Vectors लिंक किया गया है
    • Riak KV की तरह conflict values को application को सभी वापस किया जा सकता है, और application को डेटा की जानकारी के आधार पर resolve करने दिया जा सकता है
    • eventually consistent systems में conflicts कम करने की कई techniques आमतौर पर Anti Entropy शब्द के तहत रखी जाती हैं

Anti Entropy techniques

  • Read Repair

    • client कई nodes के read results में से latest value चुनने के बाद, उस value को उन nodes पर वापस भेजकर repair करता है जिन्होंने उसे अभी तक store नहीं किया है

  • Hinted Handoff

    • अगर write request target node तक नहीं पहुंच पाती, तो उसे किसी दूसरे node में hint के रूप में store किया जाता है
    • target node फिर से available होने पर stored hint deliver किया जाता है
    • quorum write में इस तरीके को Sloppy Quorum भी कहा जाता है, और यह quorum request की availability और बढ़ाता है

  • Merkle Trees

    • read repair सिर्फ queried data को ठीक करता है, इसलिए बहुत-सा डेटा लंबे समय तक inconsistent रह सकता है
    • nodes के बीच sync करते हुए पूरा difference ढूंढना data ज्यादा होने पर O(n) की वजह से महंगा होता है
    • Merkle tree एक hierarchical structure है जिसमें data range hash leaf में store होता है, और parent अपने child hashes को combine करके बना hash store करता है
    • root hash समान हो तो दोनों nodes का data समान है; अगर अलग हो, तो lower-level hashes को recursively compare करके inconsistent data खोजा जाता है, जिससे synchronization O(log n) जितना तेज हो सकता है

  • Gossip Dissemination

    • events को पूरे cluster में सरल और भरोसेमंद तरीके से propagate करने की विधि है
    • node configured संख्या के random nodes, यानी fanout, को message भेजता है, और receive करने वाले nodes फिर random nodes N को भेजते हैं
    • वही gossip message configured बार देख लेने पर आगे broadcast नहीं किया जाता
    • data convergence को महसूस कर सकने वाला simulator लिंक किया गया है
    • gossip messages आमतौर पर UDP से भेजे जाते हैं

और गहराई से कवर किए जा सकने वाले क्षेत्र

  • databases में यहाँ कवर की गई बातों के अलावा भी कई topics हैं
    • Linux के O_DIRECT का उपयोग और अपना page cache implementation
    • distributed systems में failure detection
    • Raft जैसे consensus algorithms
    • distributed transaction
    • leader election
  • database चुनते या implement करते समय storage engine, ACID, isolation levels, distributed replication, और conflict resolution methods वास्तविक requirements से कैसे मेल खाते हैं, यह साथ में देखना चाहिए

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

1 टिप्पणियां

 
GN⁺ 2023-12-16
Hacker News की राय

  • compact method में एक bug है: tombstone को केवल अंतिम, यानी सबसे बड़े level को compact करते समय ही छोड़ना चाहिए, हर level के बीच हटाना नहीं चाहिए
    नहीं तो ऊपरी level का tombstone compaction के दौरान गायब हो जाएगा, और निचले level में मौजूद entry फिर से दिखाई देने लगेगी
    LSM-आधारित database में delete/tombstone record का लंबे समय तक बने रहना इसकी एक विशेषता है, और RocksDB जैसे कुछ database इससे बचने के लिए optimization जोड़ते हैं

    • सही है, लेख में संक्षिप्तता के लिए इसे जानबूझकर छोड़ा गया था, और dbeel में इसका ध्यान रखा गया है
    • जानना दिलचस्प होगा कि RocksDB कौन-सा optimization करता है
      range delete से जुड़ी सुविधाओं के बारे में पता है, लेकिन single-key delete के बारे में पढ़ा हो ऐसा याद नहीं है

  • बहुत से लोग SQL सीखते हुए database सीखते हैं, लेकिन मैं इसे इस तरह सीखने की सलाह दूँगा कि B-tree को समझा जाए
    RDBMS के ज़्यादातर फायदे और नुकसान B-tree और उसके key insertion, lookup, sorting पर प्रभाव को समझने से स्पष्ट हो जाते हैं
    बहुत से लोग database को तेज़ करने के लिए index जोड़ते हैं, लेकिन आखिर में वह सिर्फ़ एक tree के ऊपर दूसरी tree रखने जैसा है, इसलिए यह मूल समस्या को छिपा देता है
    कुछ समस्याएँ B-tree के लिए उपयुक्त होती हैं, लेकिन बहुत-सी नहीं
    SQL बस remote B-tree system के लिए एक query interface है

    • यह बात कुछ ज़्यादा ही reductive है
      B-tree ही एकमात्र indexing strategy नहीं है, और यह भी अच्छी तरह जाना-पहचाना तथ्य है कि index पढ़ने की performance बढ़ाने के बदले लिखने की performance की क़ीमत पर आते हैं
      आम तौर पर database write की तुलना में read कहीं ज़्यादा संभालते हैं
      “एक tree के ऊपर दूसरी tree रखना” आखिर किस समस्या को छिपाता है, और index को छुए बिना उसे कैसे हल करेंगे, यह जानना चाहूँगा
      ठीक-ठाक आकार की table के लिए index लगभग अनिवार्य होते हैं
    • मैं इससे सहमत हूँ
      B-tree और hash index, I/O layer, process model जैसी चीज़ें सीखनी चाहिए
      आजकल column-oriented database की सामान्य रणनीतियाँ भी सीखने लायक हैं: late tuple materialization, lazy execution, linear scan और binary search, instruction pipelining वगैरह
      इन चीज़ों की समझ हो जाए तो यह भी पता चलता है कि व्यवहार में कई बार DBMS की जगह एक साधारण flat file या RocksDB जैसा embedded database ही काफ़ी होता है
    • यह B-tree हो सकता है, LSM-tree, trie, या स्थिति के अनुसार कोई और index structure भी
      और हाँ, covering index भी हो सकता है
    • “एक tree के ऊपर दूसरी tree रखना समस्या को छिपाता है” इस हिस्से को किसी ठोस उदाहरण से समझाया जाए तो अच्छा होगा

  • “अगर distributed न होने वाला समाधान काफ़ी है, तो distributed system से बचो” वाली सलाह पर मैं उलटा कहना चाहूँगा
    हर ऐसा production system जो मामूली न हो, distributed system होता है
    कम-से-कम अगर database एक replication set है, तो वह पहले से ही distributed system है, इसलिए distributed system न सीखना जोखिम लेना है
    https://jepsen.io/ और https://raft.github.io/ देखना उपयोगी रहेगा

    • system के कुछ हिस्से network call या distributed पहलुओं से बच नहीं सकते
      लेकिन इसका यह मतलब नहीं कि इन्हें हर जगह ले आना ठीक है; ऐसा करने से ज़रूरत से ज़्यादा complexity बढ़ती है
    • पहले “मामूली न होने वाला production system” की परिभाषा देनी होगी
      इस तरह कहने से अनावश्यक complexity से बचने वाली सलाह का खंडन नहीं होता। असली बात यह नहीं कि तकनीकी रूप से distributed है या नहीं, बल्कि यह कि क्या उसकी सच में ज़रूरत है
      distributed system सीखना और उनका उपयोग करना अलग बातें हैं
      सीख लेने के बाद भी उसे सिर्फ़ सही जगह लागू करने का संयम होना ज़रूरी है
      आजकल अक्सर बहुत मेहनत ऐसे systems को अधिक मज़बूत distributed model में ले जाने पर लगती है जो पहले से simple और ठीक चल रहे होते हैं, और इसे ऐसे लिया जाता है मानो इसकी लागत लगभग न के बराबर हो
      लेकिन जिस समस्या और scale को हल करना होता है, उसे देखें तो कई मामलों में एक single Postgres instance और monolith ही काफ़ी था
      मूल सलाह का आशय शायद यही था
    • HN bubble के भीतर यह सही लग सकता है, लेकिन औसत business नज़रिए से यह बिल्कुल सही नहीं है
      कम-से-कम यह अनिवार्य तो नहीं है
    • distributed/redundant system backup नहीं होते
      मैं फिर भी simple solution चुनने की सलाह दूँगा
      अक्सर systems “मामूली और simple storage” में भी persistent state को ठीक से store, backup और restore नहीं कर पाते
      disaster recovery की स्थिति में distributed storage की state restore करने की कोशिश करना और भी कठिन है
      काम करने वाला backup solution पहले तैयार कर लेना चाहिए, उसके बाद distributed solution अपनाना ठीक है
    • replica failover को distributed system कहना थोड़ा मुश्किल है
      read-only replica वाला master setup भी आमतौर पर वह “distributed” नहीं है जिसकी लोग बात करते हैं, क्योंकि write distributed नहीं हैं
      व्यवहार में distributed का मतलब ज़्यादातर यह होता है कि data shard किया गया है, और जब तक सच में ज़रूरत न हो, यही वह चीज़ है जिससे हर हाल में बचना चाहिए

  • database बनाते समय जुड़े कई concepts का अच्छा अवलोकन दिया गया है, इसलिए पढ़ने में मज़ा आया
    single machine से performance निचोड़ने के लिए SIMD से लेकर consensus algorithm तक शामिल हैं
    database, reliability और distributed system की बात चल ही रही है, तो ऐसे scenarios और database के internal implementation पर लागू होने वाली formal methods भी साथ में पढ़ने लायक हैं
    S3 team द्वारा TLA+ से modeling पर एक दिलचस्प paper है
    [0] Use of Formal Methods at Amazon Web Services
    https://lamport.azurewebsites.net/tla/formal-methods-amazon....
    [1] How Amazon Web Services uses formal methods
    https://www.amazon.science/publications/how-amazon-web-servi...

  • consistency के दो पहलू होते हैं: database consistency और application consistency
    उदाहरण के लिए, एक table के स्तर पर atomicity, isolation, durability हासिल की जा सकती है, लेकिन कई tables पर फैले write में विफलता हो सकती है
    जब आप एक साथ कई tables को update करने वाले transaction सँभालने लगते हैं, तब consistency महत्वपूर्ण हो जाती है
    या तो सभी tables एक साथ update हों, या फिर कुछ भी update न हो

    • यह अच्छा उदाहरण है, इसे लेख में शामिल करूँगा

  • “MongoDB जैसी document API, Cassandra जैसी leaderless replication, और ScyllaDB जैसी per-core thread architecture है” — ऐसा design काफ़ी शानदार है
    ऊपर से सब कुछ Rust में लिखा गया है

  • “किताबों ने जिज्ञासा जगाई, इसलिए मैंने खुद एक छोटा database बनाया” वाला चरण शायद बहुत से developers अपनी ज़िंदगी में कम-से-कम एक बार ज़रूर पार करते हैं
    मैं इसे रोकने की ज़रूरत नहीं समझता। खुद करके देखने पर यह बहुत अच्छी तरह समझ में आता है कि क्या काम नहीं करता
    अगर आप समय निकाल सकते हैं, तो यह बेहद मूल्यवान सीख है
    खुद database बनाकर देखने से मौजूदा समाधानों के प्रति सम्मान सबसे ज़्यादा बढ़ा
    bytes को disk पर तेज़ी से लिखना और पढ़ना असली मुश्किल हिस्सा नहीं है
    असली मुश्किल यह है कि जिन use cases की आपने कभी कल्पना भी नहीं की, उन्हें support करते हुए कई सालों तक स्थिर रूप से काम करवाया जाए

    • मुझे अक्सर यह जिज्ञासा होती है कि आधुनिक DBMS की जटिलता का कितना हिस्सा किसी खास business domain के use cases से पैदा हुई सीमाओं से आता है
      अगर domain-specific DBMS इस मान्यता पर डिज़ाइन किया जाए कि domain के बाहर के use cases को मना किया जा सकता है और नज़रअंदाज़ किया जा सकता है, तो कितनी efficiency मिल सकती है?
      उदाहरण के लिए, आज भी हम ऐसे datasets के लिए सामान्य-उद्देश्य database इस्तेमाल कर रहे हैं जो मूल रूप से append-only हैं
      अगर ऐसा database हो जिसमें मौजूदा rows को update या delete करने की अवधारणा ही न हो, और सिर्फ insert तथा पूरे table/dataset को delete करने जैसी क्रियाएँ हों, तो कैसा रहेगा?
      क्या ऐसे database को MVCC transactions लागू करने की ज़रूरत नहीं होगी? क्या हर table खुद ही write-ahead log बन सकता है, जिससे अलग write-ahead log की ज़रूरत न पड़े? क्या इसे और अधिक कुशलता से store किया जा सकता है? क्या indexing को पूरे table-स्तर की atomicity के बजाय chunk-स्तर की atomicity पर बनाया जा सकता है ताकि locking कम हो?

  • Bash version में atomicity क्या file को एक temporary file में copy करके, उसे modify करने के बाद sync; mv; sync चलाकर “आसानी” से हासिल नहीं की जा सकती?

    • copy करते समय reverse grep filter के साथ duplicates से भी बचा जा सकता है
      copy करते-करते sorting की गारंटी भी दी जा सकती है, लेकिन “bash” और सिर्फ बुनियादी utilities के साथ ऐसा करना बहुत व्यावहारिक नहीं लगता
      ऐसे काम के लिए DJB का CDB है, यानी cdbget, cdbmake वगैरह:
      https://cr.yp.to/cdb.html
    • सही है, मैं इसे बाद में जोड़ दूँगा

  • शानदार लेख
    Database Internals किताब अच्छी लग रही है, क्या ऐसी और किताबें हैं जो implementation internals में गहराई से जाती हों?

    • किताब तो नहीं, लेकिन मैं CMU के @apavlo group द्वारा डाली गई database class lectures की सिफारिश करूँगा
      https://www.youtube.com/c/cmudatabasegroup
      शुरुआती और उन्नत, दोनों तरह की classes online उपलब्ध हैं, और industry products पर talks और lectures भी हैं
      यह बहुत उपयोगी है
      इससे अधिक उच्च-स्तरीय, सैद्धांतिक computer science दृष्टिकोण वाला, और physical implementation पर कम केंद्रित एक शानदार स्रोत “Alice” किताब है, यानी “Foundations of Databases”
      यह बहुत सघन और गणितीय है, लेकिन relational algebra, Datalog, और Datalog को relational algebra में बदलने की चर्चा करती है
      print copy अब मिलना मुश्किल है; मैंने जो पुरानी copy खरीदी थी, उसकी binding टूटी हुई थी और pages निकल रहे थे, लेकिन पूरी किताब online उपलब्ध है: http://webdam.inria.fr/Alice/
    • Postgres पर केंद्रित एक मशहूर स्रोत भी है: https://www.interdb.jp/pg/
    • इसी तरह के overview के लिए यह paper अच्छा है:
      https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
    • Raghu Ramakrishnan की Database Management Systems किताब भी मेरे लिए बहुत उपयोगी रही
      हालांकि Database Internals ज़्यादा आधुनिक है

  • यह बात अच्छी लगी कि लेख “database” को रहस्यमय नहीं बनाता, बल्कि Bash one-liner से एक तुच्छ implementation दिखाकर शुरुआत करता है
    यह एक शानदार परिचय है