ScyllaDB با ایندکس Trie تا ۳ برابر سریعتر شد
خلاصهٔ کاملتر
نویسندههای تیم ScyllaDB توضیح میدن که از نسخهٔ ۲۰۲۶.۲، فرمت ایندکس پیشفرض دیتابیس عوض شده. تو فرمت قدیمی (me/md) هر بار که میخواستی یه پارتیشن رو پیدا کنی، باید سه چهارتا ساختار پیموده میشد: فایل Summary.db که کامل تو رم بود، یه جستوجوی دودویی تو Index.db و بعد خوندن ترتیبی از Data.db. این مدل هم رم میخورد هم برای هر lookup چند مرحله داشت.
فرمت جدید این دو فایل رو با یه درخت پیشوندی (prefix tree یا همون Trie) روی دیسک جایگزین میکنه که با فرمت BTI کاساندرا هم سازگاره. تو یه Trie کلیدها کاراکتر به کاراکتر ذخیره میشن، برای همین پیشوندهای مشترک فقط یهبار نوشته میشن؛ مثلاً k، ko و koo بین چند کلید فقط یکبار جا میگیرن. همین باعث میشه ایندکس خیلی جمعوجورتر بشه.
مهمترین بهینهسازی موقع نوشتن اینه که یه گره و بچههاش رو تو یه صفحهٔ ۴ کیلوبایتی کنار هم میذاره، طوری که یه محلهٔ کامل از درخت با یه بار I/O خونده میشه، حتی تو دسترسی سرد. نویسنده میگه پیادهسازی ScyllaDB برخلاف کاساندرا که هر گره یه کاراکتره، کاراکترها رو تو زنجیرههایی تا ۳۰۰ بایت گروه میکنه که نوشتن کلیدهای بلند رو خیلی سریعتر میکنه.
نتیجهٔ بنچمارکها روی یه کلاستر سهنودی AWS این بود که Trie تو هر چهار بار کاری خوندن بهتر عمل کرد. تو حالت معمولی حدود ۳۱ درصد، تو حالت key/value تا بیش از ۲۰۰ درصد، و تو پارتیشنهای بزرگ و کلیدهای با پیشوند بلند بین ۵۰ تا ۷۳ درصد توان عملیاتی بیشتر گرفت. حتی تو همون نرخ درخواست، تأخیر P99 تقریباً نصف شد.
نویسنده به نقل از Avi Kivity، مدیر فنی ScyllaDB، سه دلیل برای این بهبود میگه: ایندکس چگالتره پس راحتتر تو کش جا میگیره، اگه هم تو کش نباشه چون کمعمقتر و فشردهتره I/O کمتری میخواد، و پردازشش هم CPU کمتری میبره. تنها ضررش اینه که ساختن ایندکس موقع flush و compaction کمی CPU بیشتر میخواد که با سود سمت خوندن جبران میشه.
به گفتهٔ نویسنده برای همون توان عملیاتی، خوندن از دیسک تو فرمت قدیمی حدود ۲۴۰ مگابایت بر ثانیه بود ولی تو Trie فقط حدود ۳۳ مگابایت، یعنی حدود یکهفتم پهنای باند ذخیرهسازی. البته تأکید میکنه که برای بارهای کاری با نرخ اصابت کش ۱۰۰ درصد یا صفر درصد این سود تقریباً هیچیه، چون اونجا نمایش ایندکس تو حافظه بیاهمیته.
نکات کلیدی:
- از نسخهٔ ۲۰۲۶.۲ فرمت ایندکس پیشفرض ScyllaDB درخت پیشوندی (Trie) شده
- دو فایل Summary.db و Index.db با Partitions.db و Rows.db جایگزین شدن
- پیشوندهای مشترک فقط یکبار ذخیره میشن، پس ایندکس فشردهتره
- بین ۲۰ تا ۲۳۰ درصد توان عملیاتی بیشتر و ۳۱ تا ۶۳ درصد تأخیر کمتر تو بنچمارکها
- مصرف پهنای باند دیسک تا حدود یکهفتم کم شده و اثرش روی نوشتن ناچیزه
