‏پیتر متیس، سازندهٔ CockroachDB: همه‌چیز آخرش B-tree هست

توی این قسمت از پادکست The Pragmatic Engineer، گرگلی اوروس با پیتر متیس حرف زده. متیس CTO و هم‌بنیان‌گذار Cockroach Labs هست، GIMP رو با هم‌اتاقی دانشگاهش اسپنسر کیمبل ساخته و توی گوگل روی Gmail و ذخیره‌سازی توزیع‌شده کار کرده. اون قبل از AI سالی حدود ۱۰۰ هزار خط کد در سطح دیتابیس به production می‌فرستاده و می‌گه الان حتی پربازده‌تره.

از تجربه‌هاش توی گوگل: نسخهٔ اول Gmail (آوریل ۲۰۰۴، با ۱ گیگ فضای رایگان) برای ردیابی threadها و تعداد پیام‌های خونده‌نشده از B-tree (یعنی درختی که داده رو مرتب و با دسترسی سریع نگه می‌داره) استفاده می‌کرد. توی Colossus، جانشین GFS، تیمش به‌جای سه نسخهٔ کامل از داده سراغ Reed–Solomon erasure coding رفت (یعنی داده با چند تکهٔ کمکی ذخیره می‌شه که با اونا می‌شه بخش‌های گم‌شده رو بازسازی کرد). نتیجه: ۳۳ درصد سربار کمتر و حتی redundancy بیشتر.

متیس دو بار ساختارهای دادهٔ استاندارد رو از نظر سرعت شکست داده. std::map توی C++ یه red-black tree هست و هر گره دو پوینتر داره؛ اون یه B-tree با رفتار تقریباً یکسان ساخت که به‌خاطر نزدیکی داده‌ها توی حافظه سریع‌تر و با پوینترهای کمتر کوچیک‌تر بود. برای map زبان Go هم یه پیاده‌سازی Swiss Table نوشت که سریع‌تر بود و بعداً با کمک تیم Go وارد خود کتابخونه شد. به گفتهٔ اون، اگه دقیق نگاه کنی همه‌چیز توی دیتابیس‌های توزیع‌شده شبیه B-tree می‌شه.

دربارهٔ CockroachDB می‌گه برای consensus (یعنی توافق چند سرور سر این‌که آخرین write چی بوده) حداقل سه replica لازمه. با یکی بعد از crash نمی‌شه بازیابی کرد و با دوتا هیچ‌کدوم نمی‌دونه اون یکی آخرین write رو گرفته یا نه. واسه همین CockroachDB پیش‌فرض سه replica داره و برای بعضی جدول‌های سیستمی تا پنج‌تا. replica بیشتر یعنی latency بیشتر.

طراحی CockroachDB از Spanner و Colossus الهام گرفته. Colossus فقط append-only بود و B-tree چون نیاز به تغییر فایل داره اونجا جواب نمی‌ده؛ برای همین LSM tree (یعنی ساختاری که writeها رو اول به ته یه فایل log اضافه می‌کنه) انتخاب بهتریه. CockroachDB اول از RocksDB (که از LevelDB گوگل fork شده) استفاده می‌کرد و متیس سال ۲۰۱۹ موتور ذخیره‌سازی Pebble رو نوشت و open source کرد که الان موتور اصلی CockroachDB هست.

دربارهٔ AI، متیس که سال‌ها reviewer خوانایی C++ توی گوگل بوده، پیش‌بینی می‌کنه agentها اون‌قدر بهتر می‌شن که دیگه کد رو مثل امروز نگاه نمی‌کنیم، همون‌طور که الان assembly رو نگاه نمی‌کنیم. توی Cockroach Labs غیربرنامه‌نویس‌ها با یه پلتفرم داخلی ظرف چند ماه حدود ۱۰۰۰ اپ داخلی ساختن. اون می‌گه حالت flow هنوز هست ولی فرق کرده: چند آزمایش رو همزمان راه می‌ندازه، مثل استادی که کلی دستیار پژوهشی داره.

نکات کلیدی:

• Colossus با Reed–Solomon erasure coding سربار ذخیره‌سازی گوگل رو ۳۳ درصد کم کرد و redundancy رو بیشتر کرد.
• B-tree متیس به‌جای std::map هم سریع‌تر بود هم کم‌حجم‌تر؛ پیاده‌سازی Swiss Table اون هم وارد map زبان Go شد.
• CockroachDB پیش‌فرض سه replica داره و برای بعضی جدول‌های سیستمی پنج‌تا.
• Pebble، موتور ذخیره‌سازی LSM که متیس سال ۲۰۱۹ نوشت، جای RocksDB رو توی CockroachDB گرفت.
• غیربرنامه‌نویس‌های Cockroach Labs در چند ماه حدود ۱۰۰۰ اپ داخلی ساختن.