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

bashdb की बुनियाद

• सबसे सरल डेटाबेस प्रोग्राम bashdb दो bash functions से बना है.
• db_set function डेटा को फ़ाइल में जोड़ता है, और db_get function डेटा को खोजता है.
• bashdb की समस्याओं में durability, atomicity, isolation, performance आदि शामिल हैं.

bashdb को ACID के साथ बेहतर बनाना

• ACID डेटाबेस transaction की properties को दर्शाता है: atomicity, consistency, isolation, durability.
• bashdb की durability बेहतर करने के लिए db_set में sync command जोड़ा जाता है.
• isolation के लिए flock program का उपयोग करके file locking जोड़ी जाती है.

Durability

• fsync और fdatasync write buffer को disk पर flush करने वाले system calls हैं.
• sync command सभी 'dirty' pages को disk पर flush करती है, और -d flag fdatasync को call करता है.

Isolation

• flock का उपयोग करके bashdb को multi-process isolation दी जाती है.
• flock file locking के लिए Linux program है, और -s flag के साथ concurrent reads की अनुमति देता है.

बुरी खबर

• bashdb के साथ atomicity सुनिश्चित करने का कोई सरल तरीका नहीं मिलता.
• performance सुधारने के लिए O(n) algorithm को बेहतर बनाना ज़रूरी है.

Storage engine

• storage engine का उद्देश्य persistent storage में डेटा को पढ़ने और लिखने के लिए abstraction देना है.
• storage engine design का लक्ष्य disk I/O और disk seek को कम से कम करना है.

Mutable B-tree

• B-tree, BST का एक ऐसा रूप है जिसमें spatial locality होती है, जिससे disk I/O और seeks कम होते हैं.
• B-tree एक generalized BST है जिसमें nodes अधिक children रख सकते हैं.

Immutable LSM tree

• LSM tree एक sequentially written immutable data structure है जो write-heavy workload के लिए फायदेमंद है.
• LSM tree मेमोरी में डेटा buffer करता है, और एक तय क्षमता तक पहुँचने पर उसे sorted SSTable के रूप में flush करता है.

Bloom filter

• Bloom filter एक probabilistic data structure है जो यह कुशलता से जाँच सकता है कि कोई item set में मौजूद नहीं है.
• Bloom filter hash functions का उपयोग करके काम करता है, और इसकी space complexity O(log n) है.

Write Ahead Log

• WAL एक विशेष फ़ाइल है जो सभी transaction operations को log करती है, और database process के शुरू होने पर state को फिर से reconstruct करती है.

Isolation

• isolation हासिल करने के लिए pessimistic locking, optimistic locking, या MVCC का उपयोग किया जा सकता है.
• ANSI/ISO standard SQL 92 विभिन्न read isolation levels को परिभाषित करता है.

Distributed systems

• distributed systems जटिलता बढ़ाते हैं, और availability तथा horizontal scaling के लिए डेटा को कई machines में बाँटा जा सकता है.
• CAP theorem के अनुसार, कोई system consistency, availability, और partition tolerance में से केवल दो की ही गारंटी दे सकता है.

Consistent hashing

• consistent hashing डेटा partitioning की एक विधि है जो nodes जोड़ने या हटाने पर migrate होने वाले items की मात्रा को कम करती है.

GN⁺ की राय:

• डेटाबेस की बुनियादी समस्याओं और ACID properties की समझ, database engineering का मूल है.
• bashdb उदाहरण वास्तविक डेटाबेस systems में आने वाली समस्याओं को समझने में मदद करता है.
• storage engine और distributed systems का design, डेटाबेस की performance और reliability तय करने वाले महत्वपूर्ण तत्व हैं.

[GN⁺]

Hacker News राय

• पहली टिप्पणी का सारांश:

  • LSM-आधारित डेटाबेस की एक विशेषता यह है कि deleted records या tombstone लंबे समय तक बने रह सकते हैं।
  • tombstone को केवल अंतिम level पर ही skip करना चाहिए, सभी levels पर नहीं।
  • नहीं तो ऊपरी levels के tombstone हट सकते हैं और निचले level की entries फिर से दिखाई दे सकती हैं।
  • RocksDB जैसे डेटाबेस इस समस्या को optimize करके हल करने की कोशिश करते हैं।

• दूसरी टिप्पणी का सारांश:

  • distributed systems सीखने से बचना जोखिम भरा हो सकता है।
  • वास्तव में हर non-trivial production system एक distributed system होता है।
  • अगर डेटाबेस एक replication set है, तो वह distributed system है।
  • अगर आप distributed systems के बारे में सीखना चाहते हैं, तो jepsen.io और raft.github.io देखें।

• तीसरी टिप्पणी का सारांश:

  • consistency के संदर्भ में database consistency और application consistency दोनों होती हैं।
  • एक table में ACID (Atomicity, Consistency, Isolation, Durability) हासिल किया जा सकता है, लेकिन कई tables पर writes में विफलता हो सकती है।
  • जब कई tables को एक साथ update करने वाले transaction को संभाला जाता है, तो या तो सभी tables एक साथ update हों या फिर एक भी update न हो।

• चौथी टिप्पणी का सारांश:

  • यह लेख डेटाबेस बनाने से जुड़े विभिन्न concepts का शानदार overview देता है।
  • इसमें SIMD का उपयोग करके एक single machine पर performance बढ़ाने से लेकर consensus algorithms तक शामिल हैं।
  • डेटाबेस reliability और distributed systems पर लागू formal methods का भी उल्लेख है।
  • Amazon S3 टीम TLA+ का उपयोग करके modeling कैसे करती है, इस पर एक दिलचस्प paper है।

• पाँचवीं टिप्पणी का सारांश:

  • बहुत से लोग SQL सीखकर डेटाबेस सीखते हैं, लेकिन B-tree को समझकर RDBMS की strengths और weaknesses को बेहतर समझा जा सकता है।
  • लोग index जोड़कर डेटाबेस को तेज़ बनाने की कोशिश करते हैं, लेकिन कई बार यह सिर्फ समस्या को छिपाने जैसा होता है।
  • कुछ समस्याएँ B-tree के लिए उपयुक्त होती हैं, लेकिन बहुत-सी नहीं होतीं।
  • SQL मूल रूप से remote B-tree system के लिए एक query interface भर है।

• छठी टिप्पणी का सारांश:

  • बहुत-से developers किसी न किसी चरण में अपना छोटा-सा डेटाबेस बनाने की कोशिश करते हैं।
  • इस प्रक्रिया से यह सीखने को मिलता है कि क्या काम नहीं करता।
  • अपना डेटाबेस बनाना मौजूदा solutions के प्रति सम्मान बढ़ाने में मदद करता है।
  • डिस्क से data को तेज़ी और भरोसेमंद तरीके से ट्रांसफर करना कठिन काम है।

• सातवीं टिप्पणी का सारांश:

  • Bash version में atomicity फ़ाइल को पहले temporary file में copy करके, फिर उसे modify करके, और sync; mv; sync का उपयोग करके हासिल की जा सकती है।

• आठवीं टिप्पणी का सारांश:

  • यह बहुत शानदार design है, जिसमें document API MongoDB जैसा है, leaderless replication Cassandra जैसी है, और core-per-thread architecture ScyllaDB जैसा है।
  • यह सब Rust में implement किया गया है।

• नौवीं टिप्पणी का सारांश:

  • 'Database Internals' नाम की किताब हैरान करने वाली हद तक बेहतरीन है और internals की गहराई से पड़ताल करती है।
  • इसमें पूछा गया है कि क्या ऐसी कोई और मिलती-जुलती किताबें हैं।

• दसवीं टिप्पणी का सारांश:

  • 'Database Design and Implementation' नाम की किताब भी बहुत बढ़िया है, जिसमें Java में लिखे कई examples हैं।
  • वास्तविक research के लिए Andy (Pavlo), Viktor Leis, Thorsten Grust, Thomas Neumann आदि के काम की सिफारिश की गई है।