آشنایی با Log-Structured Merge Tree یا LSM Tree

سلام رفقا

امید که دلتون شاد باشه

وسط این اوضاع آشفته و نابسامان که خیلی ها عزیزان شون رو تو جنگ از دست دادن و آسیب های جسمی و روحی دیدن، برای من نوشتن تو ویرگول نوعی مسکن و آرام بخش محسوب میشه، شاید بتونم با سرگرم کردن خودم پیرامون مبحث مورد علاقه کاریم یعنی دیتا، یه اثر مثبت هرچند کوچیک به اندازه سر سوزن بزارم، امید که روزای خوب بیاد برای کشورمون و با شادی و نشاط کنار کسایی که دوسشون داریم روزمون رو شب کنیم و شبمون رو روز

به امید اون روز ...

من محمدم، یه علاقه مند به ترکیب مهندسی داده و هوش مصنوعی :-)

تو این نوشتار میخوام Log-Structured Merge Tree رو بهتون معرفی کنم که در دیتابیس محشر کلیک هاوس، ایده‌ی ایندکس خلوت و ساختار MergeTree از مدل‌های log-structured مثل LSM Tree الهام گرفته شده تا نوشتن‌های حجیم سریع و پردازش تحلیلی بهینه بشه.

صحبت از کلیک هاوس شد، من اینجا یه رپوزیتوری آموزش محور ازش درست کردم تو گیت هاب و دارم توسعه اش میدم، اگر دوست داشتید می تونید یه نگاهی بهش بندازید :-)

اما دیگه بریم سراغ اصل کارمون:

Log-Structured Merge Tree مشهور به LSM Tree یا ساختار داده‌ای مبتنی بر لاگ برای ادغام و ذخیره‌سازی داده‌ها چیه و چرا این‌قدر مهمه؟

اگه با دیتابیس‌های مدرن مثل Cassandra، RocksDB یا LevelDB کار کرده باشید، احتمالاً اسم LSM Tree یا Log-Structured Merge Tree به گوشتون خورده. این ساختار داده یکی از مهم‌ترین ایده‌ها در طراحی دیتابیس‌های امروزی هستش، مخصوصاً وقتی حجم نوشتن روی دیتابیس مون خیلی زیاد باشه.

در واقع، LSM Tree یه روش هوشمندانه برای ذخیره‌سازی داده‌هامون هستش که تلاش می‌کنه هزینه‌ی نوشتن روی دیسک رو تا حد ممکن کاهش بده و در عوض، همه‌چیز رو به شکل دسته‌ای و بهینه انجام بده.

خب این از مقدمه، حالا بریم سراغ تعریف مبحث مون:

LSM Tree دقیقاً چیه؟

Log-Structured Merge Tree یک ساختار داده‌ی ترکیبیه که برای مدیریت کلید-مقدارها (Key-Value) طراحی شده و هدف اصلیش، بهینه‌سازی عملیات نوشتن روی دیتابیس در حجم بالا است.

ایده‌ی اصلی ساده ست:

به جای اینکه هر داده همون لحظه روی دیسک بشینه (که بسیار کند و پرهزینه ست)، داده‌ها اول تو حافظه جمع می‌شن و بعد به‌صورت دسته‌ای روی دیسک منتقل می‌شن

اگه با فریم ورک اسپارک آشنایی داشته باشید احتمال یاد بچ پراسسینگ افتادین که البته اونجا میکروبچ هم داشتیم

ایده‌ی اصلی: دو سطح ذخیره‌سازی

LSM Tree معمولاً از دو بخش اصلی تشکیل میشه:

1. حافظه (Memory Component)

• داده‌ها ابتدا وارد RAM می‌شن

• معمولاً ساختار مرتب مثل Skip List یا Tree دارن

• بسیار سریع برای نوشتن و جستجو

2. دیسک (Disk Component)

• داده‌ها به صورت مرتب و دسته‌ای ذخیره می‌شن

• به فایل‌های مرتب (Sorted Runs) تقسیم می‌شن

وقتی حافظه پر بشه، داده‌ها یک‌جا به دیسک منتقل و با داده‌های قبلی ادغام (Merge) می‌شن

چرا LSM Tree سریعه؟

راز سرعت LSM Tree تو یه چیزه:

نوشتن ترتیبی (Sequential Write) به جای نوشتن تصادفی (Random Write)

دیسک‌ها (خصوصاً HDDها) تو نوشتن‌های تصادفی خیلی کُندن، اما تو نوشتن ترتیبی بسیار سریع‌ترن. LSM Tree میاد و دقیقاً از همین موضوع استفاده می‌کنه.

عملیات اصلی در LSM Tree

1. عملیات نوشتن (Write)

وقتی دیتای جدید وارد می‌شه (خوش اومدی داداش، صفا آوردی، دیروز دوست، امروز آشنا :-)

1. اول تو حافظه ذخیره می‌شه

2. یک لاگ (Write-Ahead Log) برای جلوگیری از از دست رفتن داده ثبت می‌شه

3. وقتی حافظه پر شد، داده‌ها به دیسک flush می‌شن

4. در نهایت با داده‌های قبلی merge می‌شن

نکته مهم:

• حذف‌ها هم واقعی نیستن، بلکه با یک علامت (tombstone) ثبت می‌شن

2. جستجوی یک مقدار (Point Lookup)

اما برای پیدا کردن یک کلید:

1. اول حافظه بررسی می‌شه

2. اگر نبود، لایه‌های دیسک یکی‌یکی چک می‌شن

3. معمولاً از Bloom Filter برای سریع رد کردن فایل‌های نامرتبط استفاده می‌شه

نتیجه:

• اگه کلید موجود باشه: خیلی سریع پیدا می‌شه

• اگه وجود نداشته باشه: ممکنه چند لایه بررسی شه

3. کوئری بازه‌ای (Range Query)

برای گرفتن بازه‌ای از داده‌ها:

• همه لایه‌ها باید بررسی شن

• نتایج با هم merge شن

• داده‌های تکراری حذف و آخرین نسخه نگه داشته می‌شه

این نوع عملیات معمولاً از point lookup کندتره، مخصوصاً اگر دیتامون اسپارس باشه

مزایا و معایب LSM Tree

مزایا

• سرعت مشحر در write

• مناسب برای دیتای حجیم و real-time

• استفاده بهینه از دیسک

• مناسب برای سیستم‌های لاگ و تحلیلی

معایب

• read ممکن است کندتر بشه

• نیاز به mergeهای دوره‌ای (compaction)

• مصرف CPU و I/O در زمان مِرجِ داده‌ها

کجا از LSM Tree استفاده می‌شه؟

LSM Tree پایه‌ی بسیاری از دیتابیس‌های مدرنه، مثل:

• ClickHouse

• Cassandra

• LevelDB

• RocksDB

• HBase

هر جایی که نوشتن زیاد و مداوم داریم، این ساختار عالی عمل می‌کنه.

جمع‌بندی

LSM Tree یه سولوشن هوشمندانه برای یکی از بزرگ‌ترین مشکلات دیتابیس‌هاست،
اونم اینکه: چطور سریع بنویسیم بدون اینکه دیسک را نابود کنیم؟

با تبدیل نوشتن‌های پراکنده به نوشتن‌های بَچ، این ساختار تونسته تعادل خوبی بین سرعت، مقیاس‌پذیری و کارایی ایجاد کنه.

مرسی مقاله رو خوندین

سوالی بود من در خدمتم رفقا :-)