डेटा-गहन एप्लिकेशन के लिए डेटा संरचनाएँ [PDF]

• key-value डेटा संरचनाएँ डेटा-आधारित सिस्टम्स का एक मुख्य घटक हैं, और workload व hardware परिस्थितियों के अनुसार इनके performance में बड़ा अंतर आ सकता है
• भौतिक संरचना को डेटा layout, खोज के लिए metadata, और स्टोरेज·retrieval algorithm में बाँटा जा सकता है; इन्हें access methods, data containers, और search structures भी कहा जाता है
• workload को point query, range query, insert, delete, update के संयोजन के रूप में व्यक्त किया जा सकता है, और memory·persistent storage की capacity और cost भी design requirement बनती है
• B+-tree read और range query में मजबूत है, लेकिन insert·update बढ़ने पर leaf node reorganization का बोझ बढ़ता है, जबकि LSM-tree buffering और merge के जरिए भारी insert workload संभालता है
• जहाँ data movement bottleneck बनता है, वहाँ नए application, hardware बदलाव, और data वृद्धि के अनुसार मौजूदा संरचना चुननी या नई संरचना डिज़ाइन करनी पड़ती है

---

key-value डेटा संरचनाएँ किस समस्या को हल करती हैं

• key-value डेटा संरचनाएँ डेटा-गहन एप्लिकेशन में व्यापक रूप से उपयोग होती हैं, और key-value मॉडल की generality के कारण कई सिस्टम्स की बुनियाद बनती हैं
• एक key एक value से map होती है, लेकिन एक ही value कई keys से जुड़ी हो सकती है
• value का अर्थ एप्लिकेशन के अनुसार बदलता है
  • यह relational database का record हो सकता है
  • यह Pandas DataFrame हो सकता है
  • यह NoSQL सिस्टम में fields का ऐसा सेट हो सकता है जिसे एप्लिकेशन parse करके उपयोग करे
  • social network data संभालने वाले सिस्टम में इसमें image या video जैसे बड़े objects के reference शामिल हो सकते हैं

भौतिक संरचना और उपयोग का दायरा

• भौतिक रूप से key-value डेटा संरचना तीन तत्वों से बनी होती है
  • किसी विशेष layout में संग्रहित data
  • data खोजने में मदद करने वाला वैकल्पिक metadata
  • स्टोरेज और retrieval operations को support करने वाले algorithm
• डेटा संरचनाएँ data systems, operating systems, file systems, compilers, और network systems में कई रूपों में उपयोग होती हैं
• पुस्तक के उदाहरण मुख्य रूप से बड़े पैमाने के data systems और secondary storage devices पर केंद्रित हैं, लेकिन विश्लेषण और design का तरीका in-memory systems पर भी लागू होता है
• यह विश्लेषण ऐसे वातावरण के लिए है जहाँ memory·storage hierarchy में दो से अधिक स्तर हों

workload और लागत डिज़ाइन को निर्धारित करते हैं

• एप्लिकेशन या workload को key-value operations के संयोजन के रूप में व्यक्त किया जा सकता है

  • point query

  • range query

    • insert
    • delete
    • update
    • memory और persistent storage की आवश्यक capacity और cost भी एप्लिकेशन requirements का हिस्सा होती हैं
    • सिस्टम के प्रकार के अनुसार optimize की जाने वाली डेटा संरचना बदलती है
    • file systems बार-बार होने वाले updates के लिए optimized डेटा संरचनाओं से file metadata और content को प्रबंधित करते हैं
    • compilers variable lifecycle के दौरान variables को hash map से प्रबंधित करते हैं, और program की समग्र संरचना को abstract syntax tree के रूप में दर्शाते हैं
    • network devices को routing tables को कुशलता से store और access करने के लिए specialized डेटा संरचनाओं की जरूरत होती है

B+-tree और LSM-tree के विपरीत विकल्प

• B+-tree का उपयोग अक्सर ऐसे workload में read cost और write cost के संतुलन के लिए किया जाता है जहाँ insert और update कम हों, लेकिन point·range query अधिक हों
• उच्च node fanout, root से leaf तक जाते समय आवश्यक secondary memory accesses को कम करता है, और upper levels को तेज memory hierarchy में cache किया जाता है
• यह सभी keys को leaf nodes में sorted रखता है और leaf nodes को linked list के रूप में जोड़कर range query को support करता है
• insert और update बढ़ने पर leaf node reorganization या split की जरूरत पड़ती है, जो performance bottleneck बन सकता है
• LSM-tree भारी insert workload के लिए एक अलग approach अपनाता है
  • सभी updates को एक shared memory buffer में रखा जाता है
  • buffer भरने पर उसे disk पर flush किया जाता है
  • buffers जमा होने पर उन्हें merge करके बड़े sorted data collections में बदला जाता है
  • updates को out-of-place policy से संभाला जाता है, इसलिए एक ही key वाले कई key-value pairs संरचना के भीतर मौजूद हो सकते हैं
  • किसी विशेष key का वर्तमान value सबसे हाल में insert किए गए key-value pair में होता है

adaptive डेटा संरचनाएँ

• इसमें सिर्फ workload का पहले से अनुमान लगाकर डेटा संरचना डिज़ाइन करने की बात नहीं है, बल्कि ऐसी डेटा संरचनाएँ भी शामिल हैं जो runtime के दौरान धीरे-धीरे आदर्श रूप के करीब पहुँचती हैं
• मूल रूप में डिज़ाइन किए गए B+-tree और LSM-tree, सभी point या range queries का उत्तर देने के लिए disk-resident nodes के भीतर sorted order को लागू करते हैं
• adaptive डेटा संरचनाएँ एक या अधिक unsorted nodes से शुरू हो सकती हैं और अवसर मिलने पर धीरे-धीरे sort की जा सकती हैं
• database cracking, आने वाली queries के access patterns का उपयोग करके आधारभूत data को लगातार और incrementally भौतिक रूप से reorganize करता है
• लक्ष्य भविष्य की query performance को बेहतर बनाना है

hardware hierarchy और memory wall

• hardware की प्रगति डेटा संरचना डिज़ाइन के लिए नई चुनौतियाँ और अवसर पैदा करती है
• storage hierarchy में नीचे के स्तर कम कीमत पर अधिक storage देते हैं, लेकिन access latency अधिक होती है; processor के करीब ऊपर के स्तर तेज होते हैं, लेकिन छोटे और प्रति byte महंगे होते हैं
• किसी विशेष एप्लिकेशन का bottleneck layer, एप्लिकेशन data के आकार और प्रत्येक layer की storage capacity पर निर्भर करता है
• B+-tree मूल रूप से fanout को अधिकतम करके disk access कम करना चाहता था, लेकिन memory capacity बढ़ने और data के RAM या non-volatile secondary memory में आने से trade-off काफ़ी बदल गए हैं
• in-memory B+-tree छोटे fanout पर सबसे अच्छा performance दिखाता है
• memory wall प्रोसेसर की गति और off-chip memory की गति के बीच बढ़ती खाई को दर्शाता है
• 2000 के दशक की शुरुआत के बाद से operating systems और data management systems को cache memory उपयोग को optimize करने के लिए फिर से डिज़ाइन किया गया है

design space और guidelines

• इसमें डेटा संरचना डिज़ाइन विकल्पों के space को व्यवस्थित किया गया है और बताया गया है कि एप्लिकेशन लक्ष्यों और workload के अनुसार सही संरचना कैसे चुनी जाए
• hardware और data गुण लगातार बदलते रहते हैं, इसलिए डेटा संरचना डिज़ाइन में निरंतर innovation की जरूरत है
• यह व्यवस्थित design space और guidelines मौजूदा डेटा संरचनाओं में सबसे उपयुक्त विकल्प चुनने या किसी विशेष workload के लिए नई डेटा संरचना डिज़ाइन करने में उपयोगी हैं

[GN⁺]

Hacker News की राय

• अभी तक सिर्फ सरसरी तौर पर देखा है, लेकिन यह लेख एक बहुत बड़े क्षेत्र को कवर करने वाली बेहतरीन सर्वे सामग्री है
  यह सिर्फ data structures की सूची भर नहीं देता, बल्कि applications में data structures बनाते या इस्तेमाल करते समय किन बातों पर विचार करना चाहिए, उन्हें दिमाग में व्यवस्थित करने में मदद करता है

  • मैंने जितनी technical books पढ़ी हैं, उनमें यह आसानी से सबसे ऊँचे स्तर में आता है

• इस किताब के लेखकों में से एक इस क्षेत्र की research lab चलाते हैं
  optimal data structure design में मदद करने वाला एक बढ़िया tool भी है: http://daslab.seas.harvard.edu/datacalculator/

  • असली tool कहाँ है, यह ढूँढना मुश्किल है

• इस विषय पर और recommended resources जानना चाहता हूँ
  paper शानदार है, और Martin Klepmann की Designing Data-Intensive Applications के बारे में भी जानता हूँ, लेकिन वह किताब data structures की बजाय databases के ज़्यादा करीब है

  • Algorithms and Data Structures for Massive Datasets से मुझे बहुत कुछ मिला: https://www.manning.com/books/algorithms-and-data-structures...

• अगर किसी तरह के analytics data को रखने के लिए structure design कर रहे हैं, तो array of structures और structure of arrays के बीच का अहम अंतर गायब है

  • सेक्शन 6.1 में row-oriented storage और column-oriented storage के फायदे-नुकसान और कारणों पर चर्चा है
    यानी चर्चा तो है, लेकिन उसे array of structures/structure of arrays वाली terminology में समझाया नहीं गया है

• एक copy खरीदना चाहता हूँ, लेकिन Amazon पर यह 100 डॉलर की है

  • अभी भी इंतज़ार है कि कोई book industry में बदलाव लाकर Amazon dependency तोड़े
    यह एक टूटा हुआ ढांचा है जिसमें author भी नुकसान में है और reader भी

• Table of contents चाहिए

  • Firefox में खोलने पर पूरा table of contents दिखता है: https://imgur.com/a/cgdy0nY
  • PDF upload करके ChatGPT 4 से table of contents बनाने को कहा, लेकिन वह इसे process करने में काफ़ी जूझ रहा है
    page headers और footers को ignore करने को कहा तब भी यही हुआ, जबकि मुझे लगा था कि latest level अब काफी बेहतर हो गया होगा