Valkey 9.2: خداحافظی Sorted Set با skiplist
خلاصهٔ کاملتر
تو Valkey 9.2، sorted setهای بزرگ دیگه با skiplist ساخته نمیشن و جاشون یه B+ tree با انشعاب بالا به اسم fbtree اومده. تیم Valkey میگه skiplist گاهی برای توصیف ترتیب اعضا بیشتر از خود اعضا حافظه میگرفت. sorted setهای کوچیک همچنان با listpack (یعنی ذخیره پشتسرهم اعضا تو یه تیکه حافظه) نگه داشته میشن و این تغییر روشون اثری نداره.
تو skiplist هر عضو یه node جدا داره که جای جدایی از حافظه ساخته میشه و با pointer به بقیه وصله. هر node یه pointer عقبگرد ۸ بایتی داره و به طور میانگین ۱.۳۳ سطح pointer و span، که روی هم حدود ۲۹ بایت میشه. با ۸ بایت score، هر node قبل از خود رشته عضو حدود ۳۷ بایت هزینه داره. مشکل دوم cache miss هست، یعنی وقتی CPU داده رو تو کش پیدا نمیکنه و باید از RAM بیاره که حدود ۱۰۰ برابر کندتره.
fbtree هر node رو تا ۶۱ ورودی پر میکنه، یعنی ۶۱ عضو یه node ۵۱۲ بایتی رو با هم شریک میشن. score و عضو هم کنار هم ذخیره میشن تا یه سطح pointer کمتر بشه. چون skiplist عملاً ضریب انشعاب ۴ داره و fbtree ۶۱، تعداد سطحها و رفتوبرگشتها به حافظه خیلی کمتره. اندازه nodeها هم با کلاسهای تخصیص jemalloc جوره که حافظه هدر نره.
چند تا بهینهسازی هم روش سواره. nodeهای داخلی برای هر فرزند یه feature چهار بایتی نگه میدارن که با SIMD (یعنی مقایسه چند مقدار با هم تو یه دستور CPU) مقایسه میشن و معمولاً بدون خوندن node فرزند، فرزند درست پیدا میشه. برگها به هم لینک شدن، پس ZRANGE بدون بالا رفتن تو درخت جلو میره. چپترین و راستترین برگ هم کش میشن تا ZPOPMIN همون O(1) بمونه.
تو تست با ۵ میلیون عضو ۲۰ بایتی، حافظه اضافه هر عضو با درج ترتیبی از ۵۰.۳ به ۲۸.۵ بایت رسید (۴۳٪ کمتر، حدود ۱۰۹ مگابایت) و با درج تصادفی به ۳۲ بایت (۳۶٪ کمتر، حدود ۹۲ مگابایت). روی Graviton3، سرعت ZADD ۱۰۵٪، ZREM ۷۶٪، ZCOUNT ۲۷٪ و ZRANK ۱۹٪ بیشتر شد. ZSCORE تقریباً تغییری نکرد، چون از hashtable استفاده میکنه نه ساختار مرتب.
تنها فرق قابل دیدن اینه که OBJECT ENCODING برای sorted setهای بزرگ به جای skiplist حالا btree برمیگردونه. یعنی اگه مانیتورینگ یا تستی دارین که دنبال کلمه skiplist میگرده، باید آپدیتش کنین. Valkey 9.2 الان تو مرحله release candidate هست و تیم ازتون میخواد قبل از نسخه نهایی با بار واقعی خودتون تستش کنین.
نکات کلیدی:
- Valkey 9.2 برای sorted setهای بزرگ skiplist رو با fbtree با انشعاب ۶۱ عوض کرده.
- حافظه اضافه هر عضو تو تست ۵ میلیونی ۳۶ تا ۴۳ درصد کم شد، یعنی تا ۱۰۹ مگابایت صرفهجویی.
- سرعت ZADD ۱۰۵٪ و ZREM ۷۶٪ بالا رفت؛ ZSCORE و ZRANDMEMBER تقریباً ثابت موندن.
- دستورها تغییری نکردن، ولی OBJECT ENCODING حالا btree برمیگردونه.
- صرفهجویی برای هر عضوه، پس بیشترین اثر رو روی setهایی با تعداد زیاد عضو کوچیک داره.




