প্রচলিত রিলেশনাল ডেটাবেসগুলো ডিস্কে ডেটা সংরক্ষণের জন্য ক্লাসিক্যাল বি-ট্রি (B-Tree) ব্যবহার করত। বি-ট্রিতে ডেটা পড়া দ্রুত হলেও ($mathcal{O}(log N)$), প্রতিবার ডেটা আপডেট বা ইনসার্ট করার সময় ডিস্কের বিভিন্ন র্যান্ডম ব্লকে লিখতে হয়। ফলে মেকানিক্যাল বা এসএসডি ডিস্কে তীব্র রাইট অ্যামপ্লিফিকেশন এবং পারফরম্যান্স পতন ঘটে। ১৯৯৬ সালে প্যাট্রিক ও’নিল এবং তাঁর সহকর্মীরা উদ্ভাবন করেন লগ-স্ট্রাকচার্ড মার্জ-ট্রি (LSM-Tree)। র্যান্ডম ডিস্ক রাইটকে উচ্চগতির সিকোয়েনশিয়াল রাইটে রূপান্তর করে এবং ব্যাকগ্রাউন্ড কম্প্যাকশনের মাধ্যমে ডেটা সাজিয়ে রাখার এই আর্কিটেকচার আজ গুগল বিগটেবিল, অ্যাপাচি ক্যাসান্ড্রা, রক্সডিবি (RocksDB) এবং সাইলাডিবি-র মতো আধুনিক নোএসকিউএল ইঞ্জিনের মেরুদণ্ডে পরিণত হয়েছে।
১. রাইট-পাথ আর্কিটেকচার: মেমোরি থেকে এসএসটেবিল (SSTable)
একটি এলএসএম-ট্রি স্টোরেজ ইঞ্জিন দুটি প্রধান স্তরে কাজ করে: দ্রুতগতির মেমোরি এবং স্থায়ী অপরিবর্তনীয় ডিস্ক ফাইল।
- রাইট-অ্যাহেড লগ (WAL): ক্লায়েন্ট যখন কোনো ডেটা লেখে (`Put` বা `Delete`), তখন সাথে সাথে ডিস্কের একটি সিকোয়েনশিয়াল ফাইলে (WAL) তা লিখে ফেলা হয়। এটি সার্ভার ক্র্যাশ করলেও ডেটা অক্ষত রাখে।
- মেমটেবিল (MemTable): একই সাথে ডেটাটি র্যামের মধ্যে একটি সর্টেড ডেটা স্ট্রাকচারে (যেমন SkipList) রাখা হয়। কোনো ডেটা মুছে ফেলার জন্য টুম্বস্টোন (Tombstone) নামক একটি বিশেষ মার্কার রেকর্ড যুক্ত করা হয়। ফলে রাইট অপারেশন মিলি-সেকেন্ডের ভগ্নাংশে শেষ হয়।
- এসএসটেবিলে ফ্ল্যাশ (Flush): মেমটেবিল পূর্ণ হয়ে গেলে (যেমন ৬৪ মেগাবাইট) এটিকে ইমিউটেবল মেমটেবিল-এ রূপান্তর করে ব্যাকগ্রাউন্ড থ্রেডের মাধ্যমে ডিস্কে একটি সর্টেড স্ট্রিং টেবিল (SSTable) হিসেবে সিকোয়েনশিয়াল ফাইলে লিখে দেওয়া হয়।
২. এসএসটেবিল (SSTable)-এর অভ্যন্তরীণ গঠন
একটি এসএসটেবিল সম্পূর্ণ অপরিবর্তনীয় (Immutable)। এতে প্রধানত চারটি অংশ থাকে:
- ডেটা ব্লক (Data Blocks): ক্রমানুসারে সাজানো এবং সংকুচিত (LZ4 বা Zstandard) কি-ভ্যালু জোড়া।
- ব্লক ইনডেক্স (Block Index): প্রতিটি ব্লকের প্রথম কি এবং ডিস্কে তার বাইট অফসেটের সূচি, যা র্যামে সংরক্ষিত থাকে।
- ব্লুম ফিল্টার (Bloom Filter): মেমোরিতে থাকা একটি প্রোবাবিলিস্টিক বিট অ্যারে, যা অস্তিত্বহীন কোনো কি খুঁজতে গিয়ে অহেতুক ডিস্ক রিড সম্পূর্ণরূপে প্রতিহত করে।
৩. ব্লুম ফিল্টারের গাণিতিক অপ্টিমাইজেশন
যেহেতু ডিস্কে অনেকগুলো এসএসটেবিল ফাইল থাকে, তাই কোনো কি খুঁজতে গিয়ে সবগুলো ফাইলে খোঁজাখুঁজি করলে পারফরম্যান্স মারাত্মক ক্ষতিগ্রস্ত হবে। ব্লুম ফিল্টার $k$ সংখ্যক হ্যাশ ফাংশন ব্যবহার করে এই সমস্যা দূর করে:
যদি ব্লুম ফিল্টার বলে কোনো কি ফাইলে নেই, তবে তা শতভাগ নিশ্চিত যে ফাইলে সত্যই নেই (Zero False Negatives)। অপটিমাল হ্যাশ ফাংশনের সংখ্যা:
$$k = rac{m}{n} ln 2 pprox 0.693 rac{m}{n}$$
প্রতি কি-এর জন্য মাত্র ১০ বিট ($m/n = 10$) মেমোরি বরাদ্দ করলেই ভুল ইতিবাচক হার (False Positive Rate) ১%-এর নিচে নেমে আসে, অর্থাৎ ৯৯% অপ্রয়োজনীয় ডিস্ক অ্যাক্সেস র্যাম থেকেই বাতিল হয়ে যায়।
৪. ব্যাকগ্রাউন্ড কম্প্যাকশন: সাইজ-টিয়ার্ড বনাম লেভেল্ড
ডিস্কে এসএসটেবিল ফাইল জমতে থাকলে রিড ধীরগতির হয়ে যায়। তাই ব্যাকগ্রাউন্ডে নিয়মিত কম্প্যাকশন (Compaction) চালানো হয়—যেখানে একাধিক এসএসটেবিল মার্জ করে পুরান ওভাররাইট ও টুম্বস্টোন ডেটা ফেলে দিয়ে নতুন সুবিন্যস্ত এসএসটেবিল তৈরি করা হয়।
- সাইজ-টিয়ার্ড কম্প্যাকশন (STCS): সমআকারের ফাইলগুলোকে একত্রিত করে পরবর্তী স্তরে পাঠায়। রাইট খুব দ্রুত হলেও ডিস্কে অতিরিক্ত খালি জায়গা প্রয়োজন হয়।
- লেভেল্ড কম্প্যাকশন (LCS): ফাইলগুলোকে ধারাবাহিক লেভেলে ($L_0, L_1, L_2$) সাজায়। $L_1$ থেকে প্রতিটি লেভেলের ফাইলগুলোর ডেটা রেঞ্জের মধ্যে কোনো ওভারল্যাপ থাকে না। ফলে রিড অপারেশন অত্যন্ত দ্রুত ও নির্ভরযোগ্য হয়।
