فصل ۳ — ذخیره‌سازی و بازیابی

Wer Ordnung hält, ist nur zu faul zum Suchen. (اگر همه‌چیز را مرتب نگه دارید، فقط برای جستجو تنبل هستید.)

— ضرب‌المثل آلمانی

در اساسی‌ترین سطح، یک پایگاه داده باید دو کار انجام دهد: وقتی داده‌ای به آن می‌دهید، آن را ذخیره کند، و وقتی بعداً دوباره می‌پرسید، داده را به شما برگرداند.

در فصل ۲ دربارهٔ مدل‌های داده و زبان‌های پرس‌وجو صحبت کردیم — یعنی قالبی که شما (توسعه‌دهندهٔ برنامه) داده را به پایگاه داده می‌دهید، و مکانیزمی که با آن بعداً می‌توانید دوباره درخواستش کنید. در این فصل همان موضوع را از دیدگاه پایگاه داده بررسی می‌کنیم: چگونه داده‌ای که به ما داده می‌شود را ذخیره کنیم، و چگونه وقتی از ما خواسته می‌شود دوباره آن را پیدا کنیم.

چرا شما به‌عنوان توسعه‌دهندهٔ برنامه باید به نحوهٔ داخلی مدیریت ذخیره‌سازی و بازیابی در پایگاه داده اهمیت دهید؟ احتمالاً موتور ذخیره‌سازی خودتان را از صفر پیاده نمی‌کنید، اما باید از میان گزینه‌های فراوان، موتوری متناسب با برنامهٔ خود انتخاب کنید. برای تنظیم موتور ذخیره‌سازی تا روی بار کاری شما خوب عمل کند، باید تصویر تقریبی از آنچه موتور زیر پوست انجام می‌دهد داشته باشید.

به‌ویژه، تفاوت بزرگی بین موتورهای ذخیره‌سازی بهینه‌شده برای بارهای تراکنشی و آن‌هایی که برای تحلیل بهینه شده‌اند وجود دارد. این تمایز را بعداً در «پردازش تراکنش یا تحلیل؟» در صفحهٔ ۹۰ بررسی می‌کنیم، و در «ذخیره‌سازی ستون‌گرا» در صفحهٔ ۹۵ خانواده‌ای از موتورهای ذخیره‌سازی بهینه‌شده برای تحلیل را بحث می‌کنیم.

با این حال، ابتدا این فصل را با صحبت دربارهٔ موتورهای ذخیره‌سازی در پایگاه‌داده‌هایی آغاز می‌کنیم که احتمالاً با آن‌ها آشنا هستید: پایگاه‌داده‌های رابطه‌ای سنتی و همچنین بیشتر پایگاه‌داده‌هایی که NoSQL نامیده می‌شوند. دو خانواده از موتورهای ذخیره‌سازی را بررسی می‌کنیم: موتورهای ذخیره‌سازی ساختاریافته بر پایهٔ لاگ، و موتورهای ذخیره‌سازی صفحه‌گرا مانند درخت‌های B.

ساختارهای داده‌ای که پایگاه داده شما را به‌کار می‌اندازند

ساده‌ترین پایگاه دادهٔ دنیا را در نظر بگیرید، پیاده‌شده به‌صورت دو تابع Bash:

#!/bin/bash

db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

این دو تابع یک مخزن کلید-مقدار پیاده می‌کنند. می‌توانید db_set key value را فراخوانی کنید که کلید و مقدار را در پایگاه داده ذخیره می‌کند. کلید و مقدار می‌توانند (تقریباً) هر چیزی باشند — مثلاً مقدار می‌تواند یک سند JSON باشد. سپس می‌توانید db_get key را فراخوانی کنید که جدیدترین مقدار مرتبط با آن کلید را جستجو و برمی‌گرداند.

و کار می‌کند:

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

قالب ذخیره‌سازی زیرین بسیار ساده است: یک فایل متنی که هر خط آن یک جفت کلید-مقدار دارد، با کاما از هم جدا شده (تقریباً شبیه فایل CSV، بدون در نظر گرفتن مسائل escape). هر فراخوانی db_set به انتهای فایل اضافه می‌کند، بنابراین اگر یک کلید را چند بار به‌روز کنید، نسخه‌های قدیمی مقدار بازنویسی نمی‌شوند — باید آخرین وقوع یک کلید در فایل را پیدا کنید تا جدیدترین مقدار را بیابید (از این رو tail -n 1 در db_get):

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

تابع db_set ما در واقع برای چیزی به‌این سادگی عملکرد نسبتاً خوبی دارد، چون افزودن به فایل معمولاً بسیار کارآمد است. مشابه کاری که db_set انجام می‌دهد، بسیاری از پایگاه‌داده‌ها دروناً از لاگ استفاده می‌کنند؛ لاگ فایل داده‌ای فقط-افزودنی (append-only) است. پایگاه‌داده‌های واقعی مسائل بیشتری دارند (مانند کنترل همزمانی، آزاد کردن فضای دیسک تا لاگ برای همیشه رشد نکند، و مدیریت خطاها و رکوردهای نیمه‌نوشته‌شده)، اما اصل پایه همان است. لاگ‌ها فوق‌العاده مفیدند و چندین بار در ادامهٔ این کتاب با آن‌ها روبه‌رو می‌شویم.

کلمهٔ log اغلب به لاگ‌های برنامه اشاره دارد، جایی که برنامه متنی خروجی می‌دهد که توصیف می‌کند چه اتفاقی می‌افتد. در این کتاب، log به معنای عمومی‌تر استفاده می‌شود: دنباله‌ای فقط-افزودنی از رکوردها. لازم نیست برای انسان خوانا باشد؛ ممکن است دودویی باشد و فقط برای خواندن توسط برنامه‌های دیگر در نظر گرفته شده باشد.

از سوی دیگر، تابع db_get ما اگر تعداد زیادی رکورد در پایگاه داده داشته باشید عملکرد وحشتناکی دارد. هر بار که می‌خواهید کلیدی را جستجو کنید، db_get باید کل فایل پایگاه داده را از ابتدا تا انتها اسکن کند و وقوع کلید را پیدا کند. از نظر الگوریتمی، هزینهٔ یک جستجو O(n) است: اگر تعداد رکوردها n را دو برابر کنید، جستجو دو برابر طول می‌کشد. این خوب نیست.

برای یافتن کارآمد مقدار یک کلید خاص در پایگاه داده، به ساختار داده‌ای متفاوت نیاز داریم: ایندکس. در این فصل طیفی از ساختارهای ایندکس را بررسی می‌کنیم و می‌بینیم چگونه مقایسه می‌شوند؛ ایدهٔ کلی پشت آن‌ها نگه‌داشتن متا‌دادهٔ اضافی در کنار است که مانند تابلو راهنما عمل می‌کند و به شما کمک می‌کند دادهٔ مورد نظر را پیدا کنید. اگر بخواهید همان داده را به چند روش مختلف جستجو کنید، ممکن است به چند ایندکس متفاوت روی بخش‌های مختلف داده نیاز داشته باشید.

ایندکس ساختار اضافی است که از دادهٔ اصلی مشتق می‌شود. بسیاری از پایگاه‌داده‌ها اجازه می‌دهند ایندکس اضافه و حذف کنید و این روی محتوای پایگاه داده تأثیری ندارد؛ فقط روی عملکرد پرس‌وجوها اثر می‌گذارد. نگه‌داری ساختارهای اضافی هزینه دارد، به‌ویژه روی نوشتن‌ها. برای نوشتن، سخت است عملکرد صرفاً افزودن به فایل را شکست دهید، چون ساده‌ترین عملیات نوشتن ممکن است. هر نوع ایندکسی معمولاً نوشتن‌ها را کند می‌کند، چون ایندکس هم باید هر بار که داده نوشته می‌شود به‌روز شود.

این مصالحهٔ مهمی در سیستم‌های ذخیره‌سازی است: ایندکس‌های خوب انتخاب‌شده پرس‌وجوهای خواندن را تسریع می‌کنند، اما هر ایندکس نوشتن‌ها را کند می‌کند. به همین دلیل، پایگاه‌داده‌ها معمولاً همه‌چیز را به‌طور پیش‌فرض ایندکس نمی‌کنند، بلکه از شما — توسعه‌دهندهٔ برنامه یا مدیر پایگاه داده — می‌خواهند با دانش الگوهای پرس‌وجوی معمول برنامه، ایندکس‌ها را دستی انتخاب کنید. سپس می‌توانید ایندکس‌هایی را انتخاب کنید که بیشترین سود را به برنامه می‌دهند، بدون اینکه هزینهٔ غیرضروری اضافه کنند.

ایندکس هش

با ایندکس‌ها برای دادهٔ کلید-مقدار شروع کنیم. این تنها نوع داده‌ای نیست که می‌توانید ایندکس کنید، اما بسیار رایج است و بلوک سازندهٔ مفیدی برای ایندکس‌های پیچیده‌تر است.

مخزن‌های کلید-مقدار شبیه نوع دیکشنری هستند که در بیشتر زبان‌های برنامه‌نویسی پیدا می‌کنید و معمولاً به‌صورت نقشهٔ هش (جدول هش) پیاده می‌شوند. نقشه‌های هش در بسیاری از کتاب‌های درسی الگوریتم توصیف شده‌اند [۱، ۲]، پس جزئیات نحوهٔ کار آن‌ها را اینجا شرح نمی‌دهیم. از آنجا که برای ساختارهای دادهٔ درون‌حافظه‌ای خودمان نقشهٔ هش داریم، چرا از آن‌ها برای ایندکس کردن داده روی دیسک استفاده نکنیم؟

فرض کنید ذخیره‌سازی دادهٔ ما فقط افزودن به فایل است، مانند مثال قبل. سپس ساده‌ترین راهبرد ایندکس‌گذاری ممکن این است: یک نقشهٔ هش درون‌حافظه‌ای نگه دارید که هر کلید به آفست بایتی در فایل داده نگاشت می‌شود — مکانی که مقدار در آن یافت می‌شود، همان‌طور که در شکل ۳-۱ نشان داده شده. هر بار که جفت کلید-مقدار جدیدی به فایل اضافه می‌کنید، نقشهٔ هش را هم به‌روز می‌کنید تا آفست داده‌ای که تازه نوشته‌اید را منعکس کند (این هم برای درج کلیدهای جدید و هم برای به‌روزرسانی کلیدهای موجود کار می‌کند). وقتی می‌خواهید مقداری را جستجو کنید، از نقشهٔ هش برای یافتن آفست در فایل داده استفاده می‌کنید، به آن مکان می‌روید و مقدار را می‌خوانید.

شکل ۳-۱. ذخیرهٔ لاگ جفت‌های کلید-مقدار در قالبی شبیه CSV، ایندکس‌شده با نقشهٔ هش درون‌حافظه‌ای.

شاید ساده به نظر برسد، اما رویکردی قابل اجراست. در واقع، این تقریباً همان کاری است که Bitcask (موتور ذخیره‌سازی پیش‌فرض در Riak) انجام می‌دهد [۳]. Bitcask خواندن و نوشتن با عملکرد بالا ارائه می‌دهد، مشروط بر اینکه همهٔ کلیدها در RAM موجود جا شوند، چون نقشهٔ هش کاملاً در حافظه نگه داشته می‌شود. مقادیر می‌توانند فضای بیشتری از حافظهٔ موجود مصرف کنند، چون با یک seek دیسکی از دیسک بارگذاری می‌شوند. اگر آن بخش از فایل داده از قبل در کش فایل‌سیستم باشد، خواندن اصلاً به I/O دیسک نیاز ندارد.

موتور ذخیره‌سازی مانند Bitcask برای موقعیت‌هایی که مقدار هر کلید مکرراً به‌روز می‌شود مناسب است. مثلاً کلید ممکن است URL یک ویدیوی گربه باشد و مقدار تعداد دفعاتی که پخش شده (هر بار که کسی دکمهٔ پخش را می‌زند افزایش می‌یابد). در این نوع بار کاری، نوشتن‌های زیادی وجود دارد، اما کلیدهای متمایز زیادی نیست — نوشتن‌های زیادی به ازای هر کلید دارید، اما نگه‌داشتن همهٔ کلیدها در حافظه عملی است.

تا اینجا فقط به فایل اضافه می‌کنیم — پس چگونه از تمام شدن فضای دیسک جلوگیری می‌کنیم؟ راه‌حل خوب شکستن لاگ به بخش‌هایی با اندازهٔ مشخص است: وقتی فایل بخشی به اندازهٔ معینی رسید بسته شود و نوشتن‌های بعدی به فایل بخش جدید برود. سپس می‌توانیم تراکم (compaction) روی این بخش‌ها انجام دهیم، همان‌طور که در شکل ۳-۲ نشان داده شده. تراکم یعنی دور انداختن کلیدهای تکراری در لاگ و نگه‌داشتن فقط جدیدترین به‌روزرسانی برای هر کلید.

شکل ۳-۲. تراکم لاگ به‌روزرسانی کلید-مقدار (شمارش تعداد دفعات پخش هر ویدیوی گربه)، با نگه‌داشتن فقط جدیدترین مقدار برای هر کلید.

علاوه بر این، چون تراکم اغلب بخش‌ها را بسیار کوچک‌تر می‌کند (با فرض اینکه یک کلید به‌طور میانگین چند بار در یک بخش بازنویسی می‌شود)، می‌توانیم هم‌زمان با تراکم چند بخش را هم ادغام کنیم، همان‌طور که در شکل ۳-۳ نشان داده شده. بخش‌ها پس از نوشته شدن هرگز تغییر نمی‌کنند، بنابراین بخش ادغام‌شده به فایل جدید نوشته می‌شود. ادغام و تراکم بخش‌های منجمد را می‌توان در یک نخ پس‌زمینه انجام داد و در حین انجام، همچنان می‌توان درخواست‌های خواندن و نوشتن را به‌طور عادی با فایل‌های بخش قدیمی سرویس داد. پس از اتمام فرایند ادغام، درخواست‌های خواندن را به بخش ادغام‌شدهٔ جدید به‌جای بخش‌های قدیمی منتقل می‌کنیم — و سپس فایل‌های بخش قدیمی را می‌توان ساده حذف کرد.

شکل ۳-۳. انجام هم‌زمان تراکم و ادغام بخش‌ها.

هر بخش اکنون نقشهٔ هش درون‌حافظهٔ خود را دارد که کلیدها را به آفست فایل نگاشت می‌کند. برای یافتن مقدار یک کلید، ابتدا نقشهٔ هش جدیدترین بخش را بررسی می‌کنیم؛ اگر کلید نبود، دومین بخش از نظر تازگی را بررسی می‌کنیم، و همین‌طور ادامه. فرایند ادغام تعداد بخش‌ها را کم نگه می‌دارد، پس جستجوها نیازی به بررسی نقشه‌های هش زیاد ندارند.

جزئیات زیادی برای عملی کردن این ایدهٔ ساده در عمل لازم است. به‌اختصار، برخی مسائل مهم در پیاده‌سازی واقعی عبارت‌اند از:

قالب فایل : CSV بهترین قالب برای لاگ نیست. سریع‌تر و ساده‌تر است از قالب دودویی استفاده کنید که ابتدا طول رشته را به بایت کدگذاری می‌کند، سپس رشتهٔ خام (بدون نیاز به escape).

حذف رکوردها : اگر بخواهید کلید و مقدار مرتبط را حذف کنید، باید رکورد حذف ویژه‌ای به فایل داده اضافه کنید (گاهی tombstone نامیده می‌شود). وقتی بخش‌های لاگ ادغام می‌شوند، tombstone به فرایند ادغام می‌گوید هر مقدار قبلی برای کلید حذف‌شده را کنار بگذارد.

بازیابی پس از خرابی : اگر پایگاه داده راه‌اندازی مجدد شود، نقشه‌های هش درون‌حافظه از بین می‌روند. در اصل می‌توانید نقشهٔ هش هر بخش را با خواندن کل فایل بخش از ابتدا تا انتها و یادداشت آفست جدیدترین مقدار برای هر کلید بازسازی کنید. اما اگر فایل‌های بخش بزرگ باشند ممکن است زمان زیادی ببرد و راه‌اندازی مجدد سرور را دردناک کند. Bitcask بازیابی را با ذخیرهٔ نسخهٔ فوری (snapshot) نقشهٔ هش هر بخش روی دیسک تسریع می‌کند که سریع‌تر به حافظه بارگذاری می‌شود.

رکوردهای نیمه‌نوشته‌شده : پایگاه داده ممکن است هر لحظه خرابی کند، از جمله نیمهٔ راه افزودن رکورد به لاگ. فایل‌های Bitcask شامل checksum هستند که اجازه می‌دهند بخش‌های خراب لاگ شناسایی و نادیده گرفته شوند.

کنترل همزمانی : چون نوشتن‌ها به‌ترتیب کاملاً ترتیبی به لاگ اضافه می‌شوند، انتخاب پیاده‌سازی رایج داشتن فقط یک نخ نویسنده است. بخش‌های فایل داده فقط-افزودنی و در غیر این صورت تغییرناپذیرند، پس می‌توانند هم‌زمان توسط چند نخ خوانده شوند.

لاگ فقط-افزودنی در نگاه اول اسراف‌آمیز به نظر می‌رسد: چرا فایل را درجا به‌روز نمی‌کنید و مقدار قدیمی را با جدید بازنویسی نمی‌کنید؟ اما طراحی فقط-افزودنی به چند دلیل خوب از آب درمی‌آید:

• افزودن و ادغام بخش‌ها عملیات نوشتن ترتیبی هستند که معمولاً بسیار سریع‌تر از نوشتن تصادفی‌اند، به‌ویژه روی هارد دیسک‌های مغناطیسی. تا حدی نوشتن‌های ترتیبی روی SSDهای حالت جامد هم ترجیح داده می‌شوند [۴]. این موضوع را در «مقایسه درخت‌های B و LSM» در صفحهٔ ۸۳ بیشتر بحث می‌کنیم.
• همزمانی و بازیابی پس از خرابی بسیار ساده‌تر است اگر فایل‌های بخش فقط-افزودنی یا تغییرناپذیر باشند. مثلاً لازم نیست نگران حالتی باشید که خرابی هنگام بازنویسی مقدار رخ داده و فایلی با بخشی از مقدار قدیمی و بخشی از جدید باقی مانده باشد.
• ادغام بخش‌های قدیمی از مشکل تکه‌تکه شدن فایل‌های داده در طول زمان جلوگیری می‌کند.

با این حال، ایندکس جدول هش محدودیت‌هایی هم دارد:

• جدول هش باید در حافظه جا شود، پس اگر کلیدهای بسیار زیادی دارید، راهی ندارید. در اصل می‌توانید نقشهٔ هش روی دیسک نگه دارید، اما متأسفانه سخت است نقشهٔ هش روی دیسک را با عملکرد خوب پیاده کنید. به I/O دسترسی تصادفی زیادی نیاز دارد، وقتی پر می‌شود رشد آن گران است، و برخورد هش به منطق پیچیده نیاز دارد [۵].
• پرس‌وجوهای بازه‌ای کارآمد نیستند. مثلاً نمی‌توانید به‌راحتی روی همهٔ کلیدهای بین kitty00000 و kitty99999 اسکن کنید — باید هر کلید را جداگانه در نقشه‌های هش جستجو کنید.

در بخش بعد ساختار ایندکسی را می‌بینیم که این محدودیت‌ها را ندارد.

SSTableها و درخت‌های LSM

در شکل ۳-۳، هر بخش ذخیره‌سازی ساختاریافته بر پایهٔ لاگ دنباله‌ای از جفت‌های کلید-مقدار است. این جفت‌ها به ترتیبی که نوشته شده‌اند ظاهر می‌شوند و مقادیر دیرتر در لاگ بر مقادیر همان کلید در بخش‌های قبلی لاگ اولویت دارند. غیر از آن، ترتیب جفت‌های کلید-مقدار در فایل مهم نیست.

اکنون می‌توانیم تغییر ساده‌ای در قالب فایل‌های بخش بدهیم: الزام کنیم که دنبالهٔ جفت‌های کلید-مقدار بر اساس کلید مرتب باشد. در نگاه اول این الزام توانایی استفاده از نوشتن‌های ترتیبی را از بین می‌برد، اما به آن می‌رسیم.

به این قالب Sorted String Table یا به‌اختصار SSTable می‌گوییم. همچنین الزام می‌کنیم هر کلید فقط یک‌بار در هر فایل بخش ادغام‌شده ظاهر شود (فرایند تراکم از قبل این را تضمین می‌کند). SSTableها چند مزیت بزرگ نسبت به بخش‌های لاگ با ایندکس هش دارند:

۱. ادغام بخش‌ها ساده و کارآمد است، حتی اگر فایل‌ها از حافظهٔ موجود بزرگ‌تر باشند. رویکرد شبیه الگوریتم mergesort است و در شکل ۳-۴ نشان داده شده: فایل‌های ورودی را کنار هم می‌خوانید، اولین کلید هر فایل را نگاه می‌کنید، کمترین کلید (طبق ترتیب مرتب‌سازی) را به فایل خروجی کپی می‌کنید و تکرار می‌کنید. این یک فایل بخش ادغام‌شدهٔ جدید هم مرتب‌شده بر اساس کلید تولید می‌کند.

شکل ۳-۴. ادغام چند بخش SSTable، با نگه‌داشتن فقط جدیدترین مقدار برای هر کلید.

اگر همان کلید در چند بخش ورودی ظاهر شود چه؟ به یاد داشته باشید هر بخش شامل همهٔ مقادیری است که در بازهٔ زمانی مشخصی به پایگاه داده نوشته شده. یعنی همهٔ مقادیر یک بخش ورودی باید جدیدتر از همهٔ مقادیر بخش دیگر باشند (با فرض اینکه همیشه بخش‌های مجاور را ادغام می‌کنیم). وقتی چند بخش همان کلید را دارند، می‌توانیم مقدار جدیدترین بخش را نگه داریم و مقادیر بخش‌های قدیمی‌تر را کنار بگذاریم.

۲. برای یافتن کلید خاصی در فایل، دیگر لازم نیست ایندکس همهٔ کلیدها را در حافظه نگه دارید. شکل ۳-۵ را ببینید: فرض کنید دنبال کلید handiwork هستید، اما آفست دقیق آن کلید در فایل بخش را نمی‌دانید. با این حال آفست کلیدهای handbag و handsome را می‌دانید، و به‌خاطر مرتب‌سازی می‌دانید handiwork باید بین آن دو باشد. یعنی می‌توانید به آفست handbag بپرید و از آنجا اسکن کنید تا handiwork را پیدا کنید (یا نه، اگر کلید در فایل نباشد).

شکل ۳-۵. یک SSTable با ایندکس درون‌حافظه‌ای.

هنوز به ایندکس درون‌حافظه‌ای نیاز دارید که آفست برخی کلیدها را بگوید، اما می‌تواند پراکنده باشد: یک کلید به ازای هر چند کیلوبایت فایل بخش کافی است، چون چند کیلوبایت را می‌توان خیلی سریع اسکن کرد.

i. اگر همهٔ کلیدها و مقادیر اندازهٔ ثابت داشتند، می‌توانستید جستجوی دودویی روی فایل بخش انجام دهید و کاملاً از ایندکس درون‌حافظه اجتناب کنید. اما در عمل معمولاً طول متغیر دارند که بدون ایندکس تشخیص پایان یک رکورد و شروع بعدی را دشوار می‌کند.

۳. از آنجا که درخواست‌های خواندن به هر حال باید چند جفت کلید-مقدار در بازهٔ درخواستی را اسکن کنند، می‌توان آن رکوردها را در یک بلوک گروه‌بندی و قبل از نوشتن روی دیسک فشرده کرد (ناحیهٔ سایه‌دار در شکل ۳-۵). هر ورود ایندکس پراکندهٔ درون‌حافظه‌ای به ابتدای یک بلوک فشرده اشاره می‌کند. علاوه بر صرفه‌جویی فضای دیسک، فشرده‌سازی استفاده از پهنای باند I/O را هم کم می‌کند.

ساخت و نگه‌داری SSTableها

تا اینجا خوب است — اما چگونه داده را از ابتدا بر اساس کلید مرتب می‌کنید؟ نوشتن‌های ورودی می‌توانند به هر ترتیبی رخ دهند.

نگه‌داری ساختار مرتب روی دیسک ممکن است (بخش «درخت‌های B» در صفحهٔ ۷۹ را ببینید)، اما نگه‌داری آن در حافظه بسیار آسان‌تر است. ساختارهای درختی شناخته‌شدهٔ زیادی وجود دارد، مانند درخت‌های قرمز-سیاه یا AVL [۲]. با این ساختارها می‌توانید کلیدها را به هر ترتیبی درج کنید و به ترتیب مرتب بخوانید.

اکنون موتور ذخیره‌سازی را این‌گونه می‌توانیم به‌کار بیندازیم:

• وقتی نوشتنی می‌آید، آن را به ساختار درختی متوازن درون‌حافظه‌ای اضافه کنید (مثلاً درخت قرمز-سیاه). این درخت درون‌حافظه‌ای گاهی memtable نامیده می‌شود.
• وقتی memtable از آستانه‌ای بزرگ‌تر شد — معمولاً چند مگابایت — آن را به‌صورت فایل SSTable روی دیسک بنویسید. این کارآمد است چون درخت از قبل جفت‌های کلید-مقدار را بر اساس کلید مرتب نگه می‌دارد. SSTable جدید جدیدترین بخش پایگاه داده می‌شود. در حین نوشتن SSTable روی دیسک، نوشتن‌ها می‌توانند به نمونهٔ memtable جدید ادامه یابند.
• برای سرویس درخواست خواندن، ابتدا کلید را در memtable جستجو کنید، سپس در جدیدترین بخش روی دیسک، سپس بخش قدیمی‌تر بعدی، و غیره.
• گاه‌به‌گاه فرایند ادغام و تراکم را در پس‌زمینه اجرا کنید تا فایل‌های بخش را ترکیب و مقادیر بازنویسی‌شده یا حذف‌شده را کنار بگذارید.

این طرح بسیار خوب کار می‌کند. فقط یک مشکل دارد: اگر پایگاه داده خرابی کند، جدیدترین نوشتن‌ها (که در memtable هستند اما هنوز روی دیسک نوشته نشده‌اند) از دست می‌روند. برای جلوگیری از آن، می‌توانیم لاگ جداگانه‌ای روی دیسک نگه داریم که هر نوشتن فوراً به آن اضافه شود، مانند بخش قبل. آن لاگ مرتب نیست، اما مهم نیست چون تنها هدفش بازسازی memtable پس از خرابی است. هر بار memtable به SSTable نوشته می‌شود، لاگ متناظر را می‌توان دور انداخت.

ساخت درخت LSM از SSTableها

الگوریتمی که اینجا توصیف شد اساساً همان چیزی است که در LevelDB [۶] و RocksDB [۷] — کتابخانه‌های موتور ذخیره‌سازی کلید-مقدار برای تعبیه در برنامه‌های دیگر — استفاده می‌شود. از جمله، LevelDB می‌تواند در Riak به‌جای Bitcask به‌کار رود. موتورهای ذخیره‌سازی مشابه در Cassandra و HBase [۸] استفاده می‌شوند که هر دو از مقالهٔ Bigtable گوگل [۹] الهام گرفته‌اند (که اصطلاحات SSTable و memtable را معرفی کرد).

در ابتدا این ساختار ایندکس توسط Patrick O'Neil و همکاران با نام Log-Structured Merge-Tree (یا LSM-Tree) توصیف شد [۱۰]، بر پایهٔ کارهای پیشین روی فایل‌سیستم‌های ساختاریافته بر پایهٔ لاگ [۱۱]. موتورهای ذخیره‌سازی مبتنی بر اصل ادغام و تراکم فایل‌های مرتب اغلب موتورهای ذخیره‌سازی LSM نامیده می‌شوند.

Lucene، موتور ایندکس جستجوی تمام‌متن که Elasticsearch و Solr از آن استفاده می‌کنند، روش مشابهی برای ذخیرهٔ فرهنگ واژه‌هایش دارد [۱۲، ۱۳]. ایندکس تمام‌متن بسیار پیچیده‌تر از ایندکس کلید-مقدار است اما بر ایدهٔ مشابهی استوار است: با توجه به واژه‌ای در پرس‌وجوی جستجو، همهٔ سندهایی (صفحات وب، توصیف محصول و غیره) که آن واژه را ذکر کرده‌اند پیدا کنید. این با ساختار کلید-مقدار پیاده می‌شود که کلید واژه (term) و مقدار فهرست شناسه‌های همهٔ سندهای حاوی آن واژه (فهرست postings) است. در Lucene این نگاشت از term به فهرست postings در فایل‌های مرتب شبیه SSTable نگه داشته می‌شود که در پس‌زمینه در صورت نیاز ادغام می‌شوند [۱۴].

بهینه‌سازی‌های عملکرد

همان‌طور که همیشه، جزئیات زیادی برای عملکرد خوب موتور ذخیره‌سازی در عمل لازم است. مثلاً الگوریتم LSM-tree هنگام جستجوی کلیدهایی که در پایگاه داده نیستند می‌تواند کند باشد: باید memtable و سپس بخش‌ها را تا قدیمی‌ترین بررسی کنید (شاید برای هر کدام از دیسک بخوانید) قبل از اطمینان از نبود کلید. برای بهینه‌سازی این نوع دسترسی، موتورهای ذخیره‌سازی اغلب از فیلترهای بلوم اضافی استفاده می‌کنند [۱۵]. (فیلتر بلوم ساختار دادهٔ حافظه‌کارآمد برای تقریب محتوای یک مجموعه است. می‌تواند بگوید کلید در پایگاه داده نیست و از خواندن‌های دیسک غیرضروری زیاد برای کلیدهای ناموجود جلوگیری می‌کند.)

راهبردهای مختلفی هم برای تعیین ترتیب و زمان‌بندی تراکم و ادغام SSTableها وجود دارد. رایج‌ترین گزینه‌ها تراکم لایه‌ای بر اساس اندازه (size-tiered) و تراکم سطحی (leveled) هستند. LevelDB و RocksDB از تراکم سطحی استفاده می‌کنند (از این رو نام LevelDB)، HBase از size-tiered، و Cassandra هر دو را پشتیبانی می‌کند [۱۶]. در تراکم size-tiered، SSTableهای جدیدتر و کوچک‌تر پیاپی در SSTableهای قدیمی‌تر و بزرگ‌تر ادغام می‌شوند. در تراکم leveled، بازهٔ کلید به SSTableهای کوچک‌تر تقسیم و دادهٔ قدیمی‌تر به «سطح‌های» جدا منتقل می‌شود که تراکم را تدریجی‌تر و با فضای دیسک کمتر امکان‌پذیر می‌کند.

با وجود ظرافت‌های زیاد، ایدهٔ پایهٔ LSM-tree — نگه‌داشتن آبشاری از SSTableها که در پس‌زمینه ادغام می‌شوند — ساده و مؤثر است. حتی وقتی مجموعه داده بسیار بزرگ‌تر از حافظهٔ موجود است خوب کار می‌کند. چون داده به ترتیب مرتب ذخیره می‌شود، می‌توانید پرس‌وجوهای بازه‌ای را کارآمد انجام دهید (اسکن همهٔ کلیدها از حداقلی تا حداکثری)، و چون نوشتن‌های دیسک ترتیبی‌اند، LSM-tree می‌تواند توان نوشتن فوق‌العاده‌ای پشتیبانی کند.

درخت‌های B

ایندکس‌های ساختاریافته بر پایهٔ لاگی که تا اینجا بحث کردیم در حال پذیرش هستند، اما رایج‌ترین نوع ایندکس نیستند. پرکاربردترین ساختار ایندکس کاملاً متفاوت است: درخت B.

در سال ۱۹۷۰ معرفی شد [۱۷] و کمتر از ۱۰ سال بعد «همه‌جا» نامیده شد [۱۸]؛ درخت‌های B آزمون زمان را بسیار خوب پس داده‌اند. همچنان پیاده‌سازی استاندارد ایندکس در تقریباً همهٔ پایگاه‌داده‌های رابطه‌ای و بسیاری از پایگاه‌داده‌های غیررابطه‌ای‌اند.

مانند SSTableها، درخت‌های B جفت‌های کلید-مقدار را بر اساس کلید مرتب نگه می‌دارند که جستجوی کلید-مقدار و پرس‌وجوهای بازه‌ای کارآمد را ممکن می‌کند. اما شباهت همین‌جا تمام می‌شود: درخت‌های B فلسفهٔ طراحی بسیار متفاوتی دارند.

ایندکس‌های ساختاریافته بر پایهٔ لاگ که پیش‌تر دیدیم پایگاه داده را به بخش‌های با اندازهٔ متغیر تقسیم می‌کنند، معمولاً چند مگابایت یا بیشتر، و همیشه یک بخش را به‌صورت ترتیبی می‌نویسند. در مقابل، درخت‌های B پایگاه داده را به بلوک‌ها یا صفحه‌های با اندازهٔ ثابت تقسیم می‌کنند، سنتی ۴ کیلوبایت (گاهی بزرگ‌تر)، و یک صفحه را در هر بار می‌خوانند یا می‌نویسند. این طراحی با سخت‌افزار زیرین همخوان‌تر است، چون دیسک‌ها هم به بلوک‌های با اندازهٔ ثابت چیده شده‌اند.

هر صفحه را می‌توان با آدرس یا مکان شناسایی کرد که به یک صفحه اجازه می‌دهد به صفحهٔ دیگر ارجاع دهد — شبیه اشاره‌گر، اما روی دیسک به‌جای حافظه. می‌توانیم با این ارجاعات صفحه درختی از صفحات بسازیم، همان‌طور که در شکل ۳-۶ نشان داده شده.

شکل ۳-۶. جستجوی کلید با استفاده از ایندکس درخت B.

یک صفحه به‌عنوان ریشهٔ درخت B تعیین می‌شود؛ هر بار که می‌خواهید کلیدی را در ایندکس جستجو کنید، از اینجا شروع می‌کنید. صفحه چند کلید و ارجاع به صفحات فرزند دارد. هر فرزند مسئول بازهٔ پیوسته‌ای از کلیدهاست و کلیدهای بین ارجاعات مرز بین آن بازه‌ها را نشان می‌دهند.

در مثال شکل ۳-۶، دنبال کلید ۲۵۱ هستیم، پس می‌دانیم باید ارجاع صفحه بین مرزهای ۲۰۰ و ۳۰۰ را دنبال کنیم. این ما را به صفحهٔ مشابهی می‌برد که بازهٔ ۲۰۰–۳۰۰ را بیشتر به زیربازه‌ها تقسیم می‌کند.

در نهایت به صفحه‌ای می‌رسیم که کلیدهای تکی دارد (صفحهٔ برگ)، که یا مقدار هر کلید را درون خود دارد یا ارجاع به صفحاتی که مقادیر در آن‌ها یافت می‌شوند.

تعداد ارجاعات به صفحات فرزند در یک صفحه از درخت B ضریب شاخه‌دهی (branching factor) نامیده می‌شود. مثلاً در شکل ۳-۶ ضریب شاخه‌دهی شش است. در عمل به فضای لازم برای ذخیرهٔ ارجاعات صفحه و مرزهای بازه بستگی دارد، اما معمولاً چند صد است.

اگر بخواهید مقدار کلید موجودی را در درخت B به‌روز کنید، صفحهٔ برگی که آن کلید را دارد جستجو می‌کنید، مقدار را در آن صفحه تغییر می‌دهید و صفحه را روی دیسک می‌نویسید (هر ارجاعی به آن صفحه معتبر می‌ماند). اگر بخواهید کلید جدید اضافه کنید، صفحه‌ای را پیدا می‌کنید که بازه‌اش کلید جدید را در بر می‌گیرد و آن را به آن صفحه اضافه می‌کنید. اگر فضای آزاد کافی در صفحه برای جا دادن کلید جدید نباشد، به دو صفحهٔ نیمه‌پر تقسیم می‌شود و صفحهٔ والد برای تقسیم جدید بازه‌های کلید به‌روز می‌شود — شکل ۳-۷ را ببینید.

شکل ۳-۷. رشد درخت B با تقسیم یک صفحه.

این الگوریتم تضمین می‌کند درخت متوازن بماند: درخت B با n کلید همیشه عمق O(log n) دارد. بیشتر پایگاه‌داده‌ها در درخت B سه یا چهار سطحی جا می‌شوند، پس لازم نیست ارجاعات صفحهٔ زیادی را دنبال کنید تا صفحهٔ مورد نظر را بیابید. (درخت چهارسطحی صفحات ۴ کیلوبایتی با ضریب شاخه‌دهی ۵۰۰ می‌تواند تا ۲۵۶ ترابایت ذخیره کند.)

ii. درج کلید جدید در درخت B تا حدی شهودی است، اما حذف آن (با حفظ توازن درخت) کمی پیچیده‌تر است [۲].

قابلیت اطمینان درخت‌های B

عملیات نوشتن پایهٔ درخت B بازنویسی یک صفحه روی دیسک با دادهٔ جدید است. فرض می‌شود بازنویسی مکان صفحه را تغییر نمی‌دهد؛ یعنی همهٔ ارجاعات به آن صفحه هنگام بازنویسی معتبر می‌مانند. این با ایندکس‌های ساختاریافته بر پایهٔ لاگ مانند LSM-tree تضاد شدید دارد که فقط به فایل‌ها اضافه می‌کنند (و در نهایت فایل‌های منسوخ را حذف می‌کنند) اما هرگز فایل‌ها را درجا تغییر نمی‌دهند.

می‌توانید بازنویسی صفحه روی دیسک را عملیات سخت‌افزاری واقعی بدانید. روی هارد دیسک مغناطیسی یعنی حرکت دادن سر دیسک به جای درست، انتظار برای رسیدن موقعیت مناسب روی صفحهٔ چرخان، و بازنویسی بخش مناسب با دادهٔ جدید. روی SSDها کمی پیچیده‌تر است، چون SSD باید بلوک‌های نسبتاً بزرگی از تراشهٔ ذخیره‌سازی را یک‌جا پاک و بازنویسی کند [۱۹].

علاوه بر این، برخی عملیات نیاز به بازنویسی چند صفحهٔ مختلف دارند. مثلاً اگر صفحه‌ای را به‌خاطر پر بودن از درج تقسیم کنید، باید دو صفحهٔ تقسیم‌شده و صفحهٔ والدشان را برای به‌روزرسانی ارجاعات به دو فرزند بنویسید. این عملیات خطرناک است، چون اگر پایگاه داده پس از نوشتن فقط برخی صفحات خرابی کند، ایندکس خراب می‌ماند (مثلاً صفحهٔ یتیمی که فرزند هیچ والدی نیست).

برای مقاوم کردن پایگاه داده در برابر خرابی، پیاده‌سازی‌های درخت B معمولاً ساختار دادهٔ اضافی روی دیسک دارند: لاگ پیش‌نوشت (write-ahead log یا WAL، که redo log هم نامیده می‌شود). این فایل فقط-افزودنی است که هر تغییر درخت B قبل از اعمال روی صفحات خود درخت باید به آن نوشته شود. وقتی پایگاه داده پس از خرابی بالا می‌آید، این لاگ برای بازگرداندن درخت B به حالت سازگار استفاده می‌شود [۵، ۲۰].

پیچیدگی اضافی به‌روزرسانی صفحات درجا این است که اگر چند نخ هم‌زمان به درخت B دسترسی داشته باشند کنترل همزمانی دقیق لازم است — وگرنه نخی ممکن است درخت را در حالت ناسازگار ببیند. معمولاً با محافظت ساختارهای دادهٔ درخت با latch (قفل سبک) انجام می‌شود. رویکردهای ساختاریافته بر پایهٔ لاگ در این زمینه ساده‌ترند، چون همهٔ ادغام‌ها را در پس‌زمینه بدون تداخل با پرس‌وجوهای ورودی انجام می‌دهند و گاه‌به‌گاه اتمی بخش‌های قدیمی را با جدید عوض می‌کنند.

بهینه‌سازی‌های درخت B

چون درخت‌های B مدت‌ها وجود داشته‌اند، تعجبی نیست که سال‌ها بهینه‌سازی‌های زیادی روی آن‌ها شده. فقط چند مورد:

• به‌جای بازنویسی صفحات و نگه‌داری WAL برای بازیابی پس از خرابی، برخی پایگاه‌داده‌ها (مانند LMDB) از طرح کپی هنگام نوشتن (copy-on-write) استفاده می‌کنند [۲۱]. صفحهٔ تغییریافته به مکان دیگری نوشته می‌شود و نسخهٔ جدیدی از صفحات والد درخت ساخته می‌شود که به مکان جدید اشاره می‌کنند. این رویکرد برای کنترل همزمانی هم مفید است، همان‌طور که در «ایزولاسیون عکس‌برداری و خواندن تکرارپذیر» در صفحهٔ ۲۳۷ خواهیم دید.
• می‌توان با ذخیره نکردن کل کلید و اختصار دادن آن در صفحات فضا صرفه‌جویی کرد. به‌ویژه در صفحات داخلی درخت، کلیدها فقط باید اطلاعات کافی برای مرز بین بازه‌های کلید بدهند. جا دادن کلیدهای بیشتر در یک صفحه ضریب شاخه‌دهی بالاتر و در نتیجه سطوح کمتر می‌دهد.
• به‌طور کلی صفحات می‌توانند هر جای دیسک باشند؛ الزامی نیست صفحات با بازه‌های کلید نزدیک، روی دیسک نزدیک هم باشند. اگر پرس‌وجویی بخش بزرگی از بازهٔ کلید را به ترتیب مرتب اسکن کند، چیدمان صفحه‌به‌صفحه می‌تواند ناکارآمد باشد چون برای هر صفحهٔ خوانده‌شده ممکن است seek دیسک لازم باشد. بسیاری از پیاده‌سازی‌های درخت B سعی می‌کنند درخت را طوری بچینند که صفحات برگ به ترتیب متوالی روی دیسک باشند. اما با رشد درخت حفظ آن ترتیب دشوار است. در مقابل، چون LSM-treeها هنگام ادغام بخش‌های بزرگی از ذخیره‌سازی را یک‌جا بازنویسی می‌کنند، نگه‌داشتن کلیدهای متوالی نزدیک هم روی دیسک برایشان آسان‌تر است.
• اشاره‌گرهای اضافی به درخت افزوده شده‌اند. مثلاً هر صفحهٔ برگ ممکن است به صفحات خواهر چپ و راست ارجاع دهد که اسکن کلیدها به ترتیب بدون پرش به صفحات والد را ممکن می‌کند.
• گونه‌هایی مانند fractal tree [۲۲] برخی ایده‌های ساختاریافته بر پایهٔ لاگ را برای کاهش seek دیسک قرض می‌گیرند (و ربطی به فراکتال ندارند).

مقایسه درخت‌های B و LSM

با وجود اینکه پیاده‌سازی‌های درخت B معمولاً بالغ‌تر از LSM-tree هستند، LSM-treeها به‌خاطر ویژگی‌های عملکردی‌شان جالب‌اند. به‌طور تقریبی، LSM-treeها معمولاً برای نوشتن سریع‌ترند، در حالی که گمان می‌رود درخت‌های B برای خواندن سریع‌تر باشند [۲۳]. خواندن روی LSM-treeها معمولاً کندتر است چون باید چند ساختار داده و SSTable در مراحل مختلف تراکم را بررسی کنند.

با این حال، معیارها اغلب نتیجه‌گیری قطعی نمی‌دهند و به جزئیات بار کاری حساس‌اند. باید سیستم‌ها را با بار کاری خاص خودتان آزمایش کنید تا مقایسهٔ معتبر داشته باشید. در این بخش چند نکته را که هنگام سنجش عملکرد موتور ذخیره‌سازی باید در نظر گرفت، به‌اختصار بحث می‌کنیم.

مزایای LSM-treeها

ایندکس درخت B باید هر تکه داده را حداقل دو بار بنویسد: یک‌بار به لاگ پیش‌نوشت و یک‌بار به صفحهٔ خود درخت (و شاید دوباره هنگام تقسیم صفحات). هزینهٔ نوشتن کل صفحه در هر بار هم هست، حتی اگر فقط چند بایت در آن صفحه تغییر کرده باشد. برخی موتورهای ذخیره‌سازی حتی همان صفحه را دو بار بازنویسی می‌کنند تا در صورت قطع برق صفحهٔ نیمه‌به‌روز نماند [۲۴، ۲۵].

ایندکس‌های ساختاریافته بر پایهٔ لاگ هم به‌خاطر تراکم و ادغام مکرر SSTableها داده را چند بار بازنویسی می‌کنند. این اثر — یک نوشتن به پایگاه داده منجر به چند نوشتن روی دیسک در طول عمر پایگاه داده — تقویت نوشتن (write amplification) نامیده می‌شود. به‌ویژه روی SSDها که فقط تعداد محدودی بار می‌توانند بلوک‌ها را بازنویسی کنند قبل از فرسودگی، نگران‌کننده است.

در برنامه‌های با نوشتن سنگین، گلوگاه عملکرد ممکن است نرخی باشد که پایگاه داده می‌تواند روی دیسک بنویسد. در این حالت تقویت نوشتن هزینهٔ عملکرد مستقیم دارد: هرچه موتور ذخیره‌سازی بیشتر روی دیسک بنویسد، نوشتن‌های کمتری در ثانیه در پهنای باند دیسک موجود انجام می‌دهد.

علاوه بر این، LSM-treeها معمولاً می‌توانند توان نوشتن بالاتری از درخت‌های B حفظ کنند، بخشی به‌خاطر تقویت نوشتن گاهی پایین‌تر (هرچند به پیکربندی موتور و بار کاری بستگی دارد)، و بخشی به‌خاطر نوشتن ترتیبی فایل‌های SSTable فشرده به‌جای بازنویسی چند صفحه در درخت [۲۶]. این تفاوت به‌ویژه روی هارد دیسک‌های مغناطیسی مهم است، جایی که نوشتن ترتیبی بسیار سریع‌تر از تصادفی است.

LSM-treeها بهتر فشرده می‌شوند و اغلب فایل‌های کوچک‌تری روی دیسک تولید می‌کنند. موتورهای درخت B به‌خاطر تکه‌تکه شدن فضای دیسک بلااستفاده می‌ماند: وقتی صفحه تقسیم می‌شود یا سطری در صفحهٔ موجود جا نمی‌شود، بخشی از صفحه خالی می‌ماند. چون LSM-treeها صفحه‌گرا نیستند و دوره‌ای SSTableها را بازنویسی می‌کنند تا تکه‌تکه شدن را حذف کنند، سربار ذخیره‌سازی کمتری دارند، به‌ویژه با تراکم leveled [۲۷].

در بسیاری از SSDها، فریمور دروناً از الگوریتم ساختاریافته بر پایهٔ لاگ استفاده می‌کند تا نوشتن‌های تصادفی را به ترتیبی روی تراشه‌های زیرین تبدیل کند، پس اثر الگوی نوشتن موتور ذخیره‌سازی کمتر است [۱۹]. با این حال، تقویت نوشتن پایین‌تر و تکه‌تکه شدن کمتر روی SSDها هم مفید است: نمایش فشرده‌تر داده اجازه می‌دهد درخواست‌های خواندن و نوشتن بیشتری در پهنای باند I/O موجود انجام شود.

iii. این گونه گاهی درخت B+ نامیده می‌شود، هرچند بهینه‌سازی آن‌قدر رایج است که اغلب از سایر گونه‌های درخت B تفکیک نمی‌شود.

معایب LSM-treeها

عیب ذخیره‌سازی ساختاریافته بر پایهٔ لاگ این است که فرایند تراکم گاهی با عملکرد خواندن و نوشتن جاری تداخل می‌کند. اگرچه موتورهای ذخیره‌سازی سعی می‌کنند تراکم را تدریجی و بدون تأثیر روی دسترسی همزمان انجام دهند، منابع دیسک محدودند و به‌راحتی ممکن است درخواستی منتظر بماند تا دیسک عملیات تراکم پرهزینه را تمام کند. اثر روی توان و میانگین زمان پاسخ معمولاً کوچک است، اما درصدایل بالاتر (بخش «توصیف عملکرد» در صفحهٔ ۱۳ را ببینید) زمان پاسخ پرس‌وجو به موتورهای ساختاریافته بر پایهٔ لاگ گاهی می‌تواند بالا باشد و درخت‌های B قابل پیش‌بینی‌تر [۲۸].

مسئلهٔ دیگر تراکم در توان نوشتن بالا: پهنای باند محدود نوشتن دیسک باید بین نوشتن اولیه (لاگ و flush کردن memtable به دیسک) و نخ‌های تراکم در پس‌زمینه تقسیم شود. هنگام نوشتن در پایگاه دادهٔ خالی، کل پهنای باند دیسک برای نوشتن اولیه قابل استفاده است، اما هرچه پایگاه داده بزرگ‌تر شود پهنای باند بیشتری برای تراکم لازم است. اگر توان نوشتن بالا باشد و تراکم با دقت پیکربندی نشود، ممکن است تراکم از نرخ نوشتن‌های ورودی عقب بماند. در این حالت تعداد بخش‌های ادغام‌نشده روی دیسک رشد می‌کند تا فضای دیسک تمام شود و خواندن هم کند می‌شود چون باید فایل‌های بخش بیشتری بررسی شود. معمولاً موتورهای مبتنی بر SSTable نرخ نوشتن ورودی را حتی وقتی تراکم عقب می‌ماند محدود نمی‌کنند، پس برای تشخیص این وضعیت نیاز به پایش صریح دارید [۲۹، ۳۰].

مزیت درخت‌های B این است که هر کلید دقیقاً در یک جای ایندکس وجود دارد، در حالی که موتور ساختاریافته بر پایهٔ لاگ ممکن است چند نسخه از همان کلید در بخش‌های مختلف داشته باشد. این جنبه درخت‌های B را برای پایگاه‌داده‌هایی که می‌خواهند معناشناسی تراکنشی قوی ارائه دهند جذاب می‌کند: در بسیاری از پایگاه‌داده‌های رابطه‌ای، ایزولاسیون تراکنش با قفل روی بازه‌های کلید پیاده می‌شود و در ایندکس درخت B آن قفل‌ها را می‌توان مستقیماً به درخت وصل کرد [۵]. در فصل ۷ این نکته را بیشتر بحث می‌کنیم.

درخت‌های B در معماری پایگاه‌داده‌ها ریشه دوانده‌اند و برای بسیاری از بارهای کاری عملکرد مداوماً خوبی دارند، پس بعید است به‌زودی از بین بروند. در مخزن‌های دادهٔ جدید، ایندکس‌های ساختاریافته بر پایهٔ لاگ روزبه‌روز محبوب‌تر می‌شوند. قاعدهٔ سریع و آسان برای تعیین اینکه کدام نوع موتور ذخیره‌سازی برای مورد استفادهٔ شما بهتر است وجود ندارد، پس ارزش دارد به‌صورت تجربی آزمایش کنید.

ساختارهای ایندکس دیگر

تا اینجا فقط ایندکس‌های کلید-مقدار را بحث کردیم که شبیه ایندکس کلید اصلی در مدل رابطه‌ای‌اند. کلید اصلی یک‌بار یک سطر در جدول رابطه‌ای، یا یک سند در پایگاه دادهٔ سندی، یا یک رأس در پایگاه دادهٔ گرافی را منحصربه‌فرد شناسایی می‌کند. سایر رکوردهای پایگاه داده می‌توانند با کلید اصلی (یا شناسه) به آن سطر/سند/رأس ارجاع دهند و ایندکس برای حل چنین ارجاعاتی استفاده می‌شود.

ایندکس‌های ثانویه هم بسیار رایج‌اند. در پایگاه‌داده‌های رابطه‌ای می‌توانید با دستور CREATE INDEX چند ایندکس ثانویه روی همان جدول بسازید و اغلب برای انجام کارآمد joinها حیاتی‌اند. مثلاً در شکل ۲-۱ فصل ۲ احتمالاً ایندکس ثانویه روی ستون‌های user_id دارید تا همهٔ سطرهای متعلق به همان کاربر در هر جدول را پیدا کنید.

ایندکس ثانویه را می‌توان به‌راحتی از ایندکس کلید-مقدار ساخت. تفاوت اصلی این است که کلیدها منحصربه‌فرد نیستند؛ یعنی ممکن است سطرها (اسناد، رأس‌ها) زیادی با همان کلید وجود داشته باشد. این را به دو روش می‌توان حل کرد: یا هر مقدار در ایندکس فهرستی از شناسه‌های سطرهای منطبق باشد (مانند فهرست postings در ایندکس تمام‌متن)، یا هر کلید با افزودن شناسهٔ سطر منحصربه‌فرد شود. در هر صورت، هم درخت‌های B و هم ایندکس‌های ساختاریافته بر پایهٔ لاگ می‌توانند به‌عنوان ایندکس ثانویه به‌کار روند.

ذخیرهٔ مقادیر درون ایندکس

کلید در ایندکس چیزی است که پرس‌وجوها دنبالش می‌گردند، اما مقدار می‌تواند یکی از دو چیز باشد: خود سطر (سند، رأس) مورد نظر، یا ارجاع به سطری که جای دیگری ذخیره شده. در حالت دوم، جایی که سطرها ذخیره می‌شوند فایل heap نامیده می‌شود و داده را بدون ترتیب خاصی نگه می‌دارد (ممکن است فقط-افزودنی باشد، یا سطرهای حذف‌شده را ردیابی کند تا بعداً با دادهٔ جدید بازنویسی شوند). رویکرد فایل heap رایج است چون از تکرار داده وقتی چند ایندکس ثانویه وجود دارد جلوگیری می‌کند: هر ایندکس فقط به مکانی در فایل heap ارجاع می‌دهد و دادهٔ واقعی در یک جا نگه داشته می‌شود.

وقتی مقداری بدون تغییر کلید به‌روز می‌شود، رویکرد فایل heap می‌تواند کارآمد باشد: رکورد درجا بازنویسی می‌شود، به‌شرط آنکه مقدار جدید از مقدار قدیمی بزرگ‌تر نباشد. اگر مقدار جدید بزرگ‌تر باشد پیچیده‌تر است، چون احتمالاً باید به مکان جدیدی در heap منتقل شود که فضای کافی دارد. در آن حالت یا همهٔ ایندکس‌ها باید به مکان جدید heap اشاره کنند، یا در مکان قدیمی heap اشاره‌گر هدایت‌کننده باقی بماند [۵].

در برخی موقعیت‌ها، پرش اضافی از ایندکس به فایل heap برای خواندن جریمهٔ عملکردی زیادی است، پس مطلوب است سطر ایندکس‌شده را مستقیماً درون ایندکس ذخیره کنید. این ایندکس خوشه‌ای (clustered index) نامیده می‌شود. مثلاً در موتور InnoDB MySQL، کلید اصلی جدول همیشه ایندکس خوشه‌ای است و ایندکس‌های ثانویه به کلید اصلی (نه مکان فایل heap) ارجاع می‌دهند [۳۱]. در SQL Server می‌توانید یک ایندکس خوشه‌ای به ازای هر جدول مشخص کنید [۳۲].

مصالحه بین ایندکس خوشه‌ای (ذخیرهٔ همهٔ دادهٔ سطر درون ایندکس) و ایندکس غیرخوشه‌ای (ذخیرهٔ فقط ارجاعات درون ایندکس) ایندکس پوششی (covering index) یا ایندکس با ستون‌های گنجانده‌شده نامیده می‌شود که برخی ستون‌های جدول را درون ایندکس نگه می‌دارد [۳۳]. این اجازه می‌دهد برخی پرس‌وجوها فقط با ایندکس پاسخ داده شوند (در این حالت گفته می‌شود ایندکس پرس‌وجو را می‌پوشاند) [۳۲].

مانند هر نوع تکرار داده، ایندکس‌های خوشه‌ای و پوششی می‌توانند خواندن را تسریع کنند، اما فضای اضافی می‌خواهند و روی نوشتن سربار می‌گذارند. پایگاه‌داده‌ها هم باید تلاش اضافی برای تضمین معناشناسی تراکنشی کنند، چون برنامه‌ها نباید به‌خاطر تکرار ناسازگاری ببینند.

ایندکس چندستونی

ایندکس‌هایی که تا اینجا بحث شد فقط یک کلید را به یک مقدار نگاشت می‌کنند. برای پرس‌وجوی هم‌زمان چند ستون جدول (یا چند فیلد در سند) کافی نیست.

رایج‌ترین نوع ایندکس چندستونی ایندکس الحاقی (concatenated index) نامیده می‌شود که چند فیلد را با الحاق یک ستون به دیگری در یک کلید ترکیب می‌کند (تعریف ایندکس ترتیب الحاق فیلدها را مشخص می‌کند). شبیه دفترچه تلفن کاغذی قدیمی است که ایندکس از (نام‌خانوادگی، نام) به شماره تلفن می‌دهد. به‌خاطر ترتیب مرتب‌سازی، ایندکس برای یافتن همهٔ افراد با نام‌خانوادگی خاص، یا همهٔ افراد با ترکیب نام‌خانوادگی-نام خاص کار می‌کند. اما اگر بخواهید همهٔ افراد با نام خاص را پیدا کنید ایندکس بی‌فایده است.

ایندکس‌های چندبعدی راه عمومی‌تر پرس‌وجوی چند ستون هم‌زمان‌اند که به‌ویژه برای دادهٔ جغرافیایی مهم است. مثلاً وب‌سایت جستجوی رستوران ممکن است پایگاه داده‌ای با عرض و طول جغرافیایی هر رستوران داشته باشد. وقتی کاربر رستوران‌ها را روی نقشه می‌بیند، وب‌سایت باید همهٔ رستوران‌های داخل ناحیهٔ مستطیلی نقشهٔ فعلی کاربر را جستجو کند. این به پرس‌وجوی بازهٔ دوبعدی مانند زیر نیاز دارد:

SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
                            AND longitude > -0.1162 AND longitude < -0.1004;

ایندکس استاندارد درخت B یا LSM-tree نمی‌تواند چنین پرس‌وجویی را کارآمد پاسخ دهد: یا همهٔ رستوران‌ها در بازهٔ عرض جغرافیایی (با هر طولی) را می‌دهد، یا همهٔ رستوران‌ها در بازهٔ طول (در هر نقطه بین قطب‌ها)، اما نه هر دو هم‌زمان.

یک گزینه تبدیل موقعیت دوبعدی به یک عدد با منحنی پرکننده فضا (space-filling curve) و استفاده از ایندکس درخت B معمولی است [۳۴]. رایج‌تر، ایندکس‌های فضایی تخصصی مانند R-tree استفاده می‌شوند. مثلاً PostGIS ایندکس‌های جغرافیایی را به‌صورت R-tree با تسهیلات Generalized Search Tree PostgreSQL پیاده می‌کند [۳۵]. اینجا جا برای شرح R-tree نداریم، اما ادبیات زیادی دربارهٔ آن‌ها وجود دارد.

ایدهٔ جالبی این است که ایندکس‌های چندبعدی فقط برای مکان جغرافیایی نیستند. مثلاً در وب‌سایت تجارت الکترونیک می‌توانید ایندکس سه‌بعدی روی (قرمز، سبز، آبی) برای جستجوی محصولات در بازهٔ رنگی خاص داشته باشید، یا در پایگاه دادهٔ مشاهدات هواشناسی ایندکس دوبعدی روی (تاریخ، دما) برای جستجوی کارآمد همهٔ مشاهدات سال ۲۰۱۳ با دمای بین ۲۵ و ۳۰ درجهٔ سانتی‌گراد. با ایندکس یک‌بعدی باید یا همهٔ رکوردهای ۲۰۱۳ را اسکن کنید (صرف‌نظر از دما) و بعد فیلتر دما، یا برعکس. ایندکس ۲بعدی می‌تواند هم‌زمان بر زمان و دما محدود کند. این تکنیک در HyperDex [۳۶] استفاده شده.

جستجوی تمام‌متن و ایندکس‌های فازی

همهٔ ایندکس‌های بحث‌شده فرض می‌کنند دادهٔ دقیق دارید و اجازه می‌دهند مقادیر دقیق کلید یا بازه‌ای از مقادیر با ترتیب مرتب را پرس‌وجو کنید. آنچه اجازه نمی‌دهند جستجوی کلیدهای مشابه است، مانند واژه‌های اشتباه املایی. چنین پرس‌وجوی فازی به تکنیک‌های متفاوتی نیاز دارد.

مثلاً موتورهای جستجوی تمام‌متن معمولاً اجازه می‌دهند جستجوی یک واژه به مترادف‌ها گسترش یابد، تغییرات دستوری نادیده گرفته شود، وقوع واژه‌ها نزدیک هم در همان سند جستجو شود، و ویژگی‌های دیگری که به تحلیل زبانی متن وابسته‌اند پشتیبانی شود. برای مقابله با غلط‌های املایی در اسناد یا پرس‌وجوها، Lucene می‌تواند متن را برای واژه‌هایی در فاصلهٔ ویرایش مشخص (فاصلهٔ ویرایش ۱ یعنی یک حرف اضافه، حذف یا جایگزین شده) جستجو کند [۳۷].

همان‌طور که در «ساخت درخت LSM از SSTableها» در صفحهٔ ۷۸ گفته شد، Lucene برای فرهنگ واژه‌هایش از ساختار شبیه SSTable استفاده می‌کند. این ساختار به ایندکس کوچک درون‌حافظه‌ای نیاز دارد که به پرس‌وجوها بگوید در فایل مرتب به کدام آفست نگاه کنند. در LevelDB این ایندکس درون‌حافظه مجموعهٔ پراکنده‌ای از برخی کلیدهاست، اما در Lucene ایندکس درون‌حافظه اتوماتون حالت متناهی روی نویسه‌های کلیدهاست، شبیه trie [۳۸]. این اتوماتون را می‌توان به اتوماتون Levenshtein تبدیل کرد که جستجوی کارآمد واژه‌ها در فاصلهٔ ویرایش داده‌شده را پشتیبانی می‌کند [۳۹].

سایر تکنیک‌های جستجوی فازی به سمت طبقه‌بندی سند و یادگیری ماشین می‌روند. برای جزئیات بیشتر کتاب درسی بازیابی اطلاعات را ببینید [مثلاً ۴۰].

نگه‌داشتن همه‌چیز در حافظه

ساختارهای داده‌ای که تا اینجا در این فصل بحث شد همه پاسخی به محدودیت‌های دیسک بودند. نسبت به حافظهٔ اصلی، دیسک‌ها دست‌وپاگیرند. هم روی دیسک مغناطیسی و هم SSD، برای عملکرد خواندن و نوشتن باید داده روی دیسک با دقت چیده شود. اما این دست‌وپاگیری را تحمل می‌کنیم چون دیسک دو مزیت مهم دارد: پایدار است (با قطع برق محتوا از بین نمی‌رود) و هزینهٔ هر گیگابایت از RAM کمتر است.

با ارزان‌تر شدن RAM، استدلال هزینهٔ هر گیگابایت ضعیف می‌شود. بسیاری از مجموعه‌داده‌ها آن‌قدر بزرگ نیستند که نگه‌داشتن کامل آن‌ها در حافظه عملی باشد، شاید توزیع‌شده روی چند ماشین. این به توسعهٔ پایگاه‌داده‌های درون‌حافظه‌ای منجر شده.

برخی مخزن‌های کلید-مقدار درون‌حافظه مانند Memcached فقط برای کش در نظر گرفته شده‌اند و از دست رفتن داده با راه‌اندازی مجدد ماشین قابل قبول است. اما پایگاه‌داده‌های درون‌حافظهٔ دیگر هدف پایداری دارند که با سخت‌افزار ویژه (مانند RAM با باتری)، نوشتن لاگ تغییرات روی دیسک، نوشتن دوره‌ای snapshot روی دیسک، یا تکرار حالت درون‌حافظه روی ماشین‌های دیگر قابل دستیابی است.

وقتی پایگاه دادهٔ درون‌حافظه راه‌اندازی مجدد می‌شود، باید حالتش را بارگذاری کند، از دیسک یا از شبکه از یک replica (مگر سخت‌افزار ویژه استفاده شود). با وجود نوشتن روی دیسک، همچنان پایگاه دادهٔ درون‌حافظه است چون دیسک فقط به‌عنوان لاگ فقط-افزودنی برای پایداری به‌کار می‌رود و خواندن‌ها کاملاً از حافظه سرویس می‌شوند. نوشتن روی دیسک مزایای عملیاتی هم دارد: فایل‌های دیسک به‌راحتی پشتیبان، بازرسی و تحلیل با ابزارهای خارجی می‌شوند.

محصولاتی مانند VoltDB، MemSQL و Oracle TimesTen پایگاه‌داده‌های درون‌حافظه با مدل رابطه‌ای‌اند و فروشندگان ادعا می‌کنند با حذف همهٔ سربارهای مدیریت ساختارهای دادهٔ روی دیسک بهبود عملکرد بزرگی ارائه می‌دهند [۴۱، ۴۲]. RAMCloud مخزن کلید-مقدار درون‌حافظهٔ متن‌باز با پایداری است (با رویکرد ساختاریافته بر پایهٔ لاگ هم برای داده در حافظه و هم روی دیسک) [۴۳]. Redis و Couchbase با نوشتن ناهمگام روی دیسک پایداری ضعیف ارائه می‌دهند.

غیرشهودی، مزیت عملکرد پایگاه‌داده‌های درون‌حافظه به‌خاطر نیاز نداشتن به خواندن از دیسک نیست. حتی موتور مبتنی بر دیسک اگر حافظهٔ کافی داشته باشید شاید هرگز از دیسک نخواند، چون سیستم‌عامل بلوک‌های دیسک اخیراً استفاده‌شده را در حافظه کش می‌کند. بلکه می‌توانند سریع‌تر باشند چون از سربار کدگذاری ساختارهای دادهٔ درون‌حافظه به قالبی قابل نوشتن روی دیسک اجتناب می‌کنند [۴۴].

علاوه بر عملکرد، حوزهٔ جالب دیگر برای پایگاه‌داده‌های درون‌حافظه ارائهٔ مدل‌های داده‌ای است که با ایندکس‌های مبتنی بر دیسک پیاده‌سازی دشوارند. مثلاً Redis رابط شبیه پایگاه داده به ساختارهای دادهٔ مختلف مانند صف اولویت و مجموعه می‌دهد. چون همهٔ داده را در حافظه نگه می‌دارد، پیاده‌سازی آن نسبتاً ساده است.

پژوهش‌های اخیر نشان می‌دهد معماری پایگاه دادهٔ درون‌حافظه می‌تواند برای مجموعه‌داده‌های بزرگ‌تر از حافظهٔ موجود گسترش یابد، بدون بازگرداندن سربارهای معماری دیسک‌محور [۴۵]. رویکرد به‌اصطلاح ضد-کش (anti-caching) با بیرون‌انداختن کم‌ترین استفاده‌شده‌ها از حافظه به دیسک وقتی حافظه کافی نیست کار می‌کند و هنگام دسترسی مجدد دوباره به حافظه بارگذاری می‌کند. شبیه کاری است که سیستم‌عامل با حافظه مجازی و فایل swap انجام می‌دهد، اما پایگاه داده می‌تواند حافظه را کارآمدتر از OS مدیریت کند چون در سطح رکورد تکی کار می‌کند نه کل صفحات حافظه. با این حال این رویکرد همچنان نیاز دارد ایندکس‌ها کاملاً در حافظه جا شوند (مانند مثال Bitcask در ابتدای فصل).

اگر فناوری‌های حافظهٔ غیرفرار (NVM) رایج‌تر شوند، احتمالاً تغییرات بیشتری در طراحی موتور ذخیره‌سازی لازم است [۴۶]. در حال حاضر حوزهٔ پژوهشی جدیدی است، اما ارزش دارد در آینده زیر نظر داشته باشید.

پردازش تراکنش یا تحلیل؟

در روزهای اول پردازش دادهٔ تجاری، نوشتن به پایگاه داده معمولاً متناظر با انجام تراکنش تجاری بود: فروش، سفارش به تأمین‌کننده، پرداخت حقوق کارمند و غیره. با گسترش پایگاه‌داده‌ها به حوزه‌هایی که پول رد و بدل نمی‌شد، اصطلاح تراکنش ماند و به گروهی از خواندن‌ها و نوشتن‌ها که واحد منطقی تشکیل می‌دهند اشاره کرد.

تراکنش لزوماً ویژگی‌های ACID (اتمی بودن، سازگاری، ایزولاسیون و پایداری) ندارد. پردازش تراکنش فقط یعنی اجازهٔ خواندن و نوشتن با تأخیر کم به کلاینت‌ها — در مقابل کارهای پردازش دسته‌ای که فقط دوره‌ای (مثلاً روزی یک‌بار) اجرا می‌شوند. ویژگی‌های ACID را در فصل ۷ و پردازش دسته‌ای را در فصل ۱۰ بحث می‌کنیم.

با وجود استفاده از پایگاه‌داده‌ها برای انواع داده — نظرات وبلاگ، اقدامات بازی، مخاطبین دفترچه تلفن و غیره — الگوی دسترسی پایه شبیه پردازش تراکنش‌های تجاری ماند. برنامه معمولاً تعداد کمی رکورد را با کلیدی از طریق ایندکس جستجو می‌کند. رکوردها بر اساس ورودی کاربر درج یا به‌روز می‌شوند. چون این برنامه‌ها تعاملی‌اند، الگوی دسترسی پردازش تراکنش آنلاین (OLTP) نام گرفت.

با این حال، پایگاه‌داده‌ها روزبه‌روز بیشتر برای تحلیل داده هم به‌کار رفتند که الگوی دسترسی بسیار متفاوتی دارد. معمولاً پرس‌وجوی تحلیلی باید تعداد بسیار زیادی رکورد را اسکن کند، فقط چند ستون از هر رکورد را بخواند، و آمارهای تجمیعی (مانند شمارش، مجموع یا میانگین) محاسبه کند به‌جای برگرداندن دادهٔ خام به کاربر. مثلاً اگر داده جدول تراکنش‌های فروش باشد، پرس‌وجوهای تحلیلی ممکن است این‌ها باشند:

• درآمد کل هر فروشگاه ما در ژانویه چقدر بود؟
• در آخرین پروموشن چند موز بیشتر از معمول فروختیم؟
• کدام برند غذای کودک بیشتر همراه برند X پوشک خریده می‌شود؟

این پرس‌وجوها اغلب توسط تحلیل‌گران کسب‌وکار نوشته می‌شوند و به گزارش‌هایی تغذیه می‌کنند که مدیریت شرکت را در تصمیم‌گیری بهتر یاری می‌دهند (هوش تجاری). برای تمایز این الگوی استفاده از پایگاه داده از پردازش تراکنش، اصطلاح پردازش تحلیل آنلاین (OLAP) [۴۷] به‌کار رفت. تفاوت OLTP و OLAP همیشه روشن نیست، اما برخی ویژگی‌های معمول در جدول ۳-۱ آمده است.

جدول ۳-۱. مقایسهٔ ویژگی‌های سیستم‌های پردازش تراکنش در برابر سیستم‌های تحلیلی

ویژگی	سیستم‌های پردازش تراکنش (OLTP)	سیستم‌های تحلیلی (OLAP)
الگوی اصلی خواندن	تعداد کم رکورد در هر پرس‌وجو، واکشی با کلید	تجمیع روی تعداد زیاد رکورد
الگوی اصلی نوشتن	نوشتن دسترسی تصادفی با تأخیر کم از ورودی کاربر	واردات انبوه (ETL) یا جریان رویداد
استفادهٔ اصلی توسط	کاربر/مشتری نهایی، از طریق برنامهٔ وب	تحلیل‌گر داخلی، برای پشتیبانی تصمیم
معنای داده	آخرین وضعیت داده (لحظهٔ فعلی)	تاریخچهٔ رویدادهایی که در طول زمان رخ داده
اندازهٔ مجموعه داده	گیگابایت تا ترابایت	ترابایت تا پتابایت

در ابتدا همان پایگاه‌داده‌ها هم برای پردازش تراکنش و هم برای پرس‌وجوهای تحلیلی استفاده می‌شد. SQL در این زمینه انعطاف‌پذیر بود: هم برای پرس‌وجوهای OLTP و هم OLAP خوب کار می‌کرد. با این حال، در اواخر دههٔ ۱۹۸۰ و اوایل ۱۹۹۰، روند شرکت‌ها این بود که دیگر سیستم‌های OLTP را برای تحلیل به‌کار نبرند و تحلیل را روی پایگاه دادهٔ جداگانه اجرا کنند. این پایگاه دادهٔ جداگانه انبار داده (data warehouse) نامیده شد.

iv. معنای آنلاین در OLAP روشن نیست؛ احتمالاً به این اشاره دارد که پرس‌وجوها فقط برای گزارش‌های از پیش تعریف‌شده نیستند، بلکه تحلیل‌گران به‌صورت تعاملی از سیستم OLAP برای پرس‌وجوهای اکتشافی استفاده می‌کنند.

انبار داده

یک بنگاه ممکن است ده‌ها سیستم پردازش تراکنش مختلف داشته باشد: سیستم‌های وب رو به مشتری، سیستم‌های صندوق فروشگاه فیزیکی، ردیابی موجودی انبار، برنامه‌ریزی مسیر خودروها، مدیریت تأمین‌کنندگان، ادارهٔ کارمندان و غیره. هر کدام پیچیده‌اند و تیم نگهداری می‌خواهند، پس سیستم‌ها عمدتاً مستقل از هم کار می‌کنند.

از این سیستم‌های OLTP معمولاً دسترسی بالا و پردازش تراکنش با تأخیر کم انتظار می‌رود، چون اغلب برای عملیات کسب‌وکار حیاتی‌اند. مدیران پایگاه داده بنابراین پایگاه‌های OLTP را به‌دقت محافظت می‌کنند. معمولاً بی‌میل‌اند تحلیل‌گران کسب‌وکار پرس‌وجوهای تحلیلی ad hoc روی پایگاه OLTP اجرا کنند، چون آن پرس‌وجوها اغلب پرهزینه‌اند و بخش بزرگی از مجموعه داده را اسکن می‌کنند که می‌تواند به عملکرد تراکنش‌های همزمان آسیب بزند.

انبار داده، در مقابل، پایگاه دادهٔ جداگانه‌ای است که تحلیل‌گران می‌توانند هرچقدر بخواهند پرس‌وجو کنند بدون اینکه عملیات OLTP را تحت تأثیر قرار دهند [۴۸]. انبار داده شامل نسخهٔ فقط-خواندنی داده از همهٔ سیستم‌های OLTP مختلف شرکت است. داده از پایگاه‌های OLTP استخراج می‌شود (با dump دوره‌ای یا جریان مداوم به‌روزرسانی)، به طرحوارهٔ مناسب تحلیل تبدیل، پاکسازی و سپس به انبار داده بارگذاری می‌شود. این فرایند ورود داده به انبار استخراج–تبدیل–بارگذاری (Extract–Transform–Load یا ETL) نامیده می‌شود و در شکل ۳-۸ نشان داده شده.

شکل ۳-۸. طرح کلی سادهٔ ETL به انبار داده.

انبار داده اکنون در تقریباً همهٔ بنگاه‌های بزرگ وجود دارد، اما در شرکت‌های کوچک تقریباً ناشناخته است. احتمالاً به‌خاطر این است که بیشتر شرکت‌های کوچک سیستم‌های OLTP متعدد ندارند و دادهٔ کمی دارند — آن‌قدر کم که در پایگاه SQL معمولی یا حتی صفحه‌گسترده قابل تحلیل است. در شرکت بزرگ، کار سنگین زیادی لازم است برای کاری که در شرکت کوچک ساده است.

مزیت بزرگ استفاده از انبار دادهٔ جداگانه به‌جای پرس‌وجوی مستقیم سیستم‌های OLTP برای تحلیل این است که انبار داده را می‌توان برای الگوهای دسترسی تحلیلی بهینه کرد. معلوم می‌شود الگوریتم‌های ایندکس بحث‌شده در نیمهٔ اول این فصل برای OLTP خوب‌اند، اما برای پاسخ به پرس‌وجوهای تحلیلی چندان مناسب نیستند.

در ادامهٔ این فصل موتورهای ذخیره‌سازی بهینه‌شده برای تحلیل را می‌بینیم.

واگرایی بین پایگاه‌های OLTP و انبارهای داده

مدل دادهٔ انبار داده معمولاً رابطه‌ای است، چون SQL عموماً برای پرس‌وجوهای تحلیلی مناسب است. ابزارهای تحلیل دادهٔ گرافیکی زیادی SQL تولید، نتایج را visualize و به تحلیل‌گران اجازهٔ کاوش داده می‌دهند (با عملیاتی مانند drill-down و slicing and dicing).

در ظاهر، انبار داده و پایگاه OLTP رابطه‌ای شبیه‌اند چون هر دو رابط پرس‌وجوی SQL دارند. اما درون سیستم‌ها می‌تواند کاملاً متفاوت باشد، چون برای الگوهای پرس‌وجوی بسیار متفاوت بهینه شده‌اند. بسیاری از فروشندگان پایگاه داده اکنون روی پشتیبانی از بار کاری پردازش تراکنش یا تحلیل تمرکز می‌کنند، نه هر دو.

برخی پایگاه‌داده‌ها مانند Microsoft SQL Server و SAP HANA در یک محصول از پردازش تراکنش و انبار داده پشتیبانی می‌کنند. اما روزبه‌روز بیشتر به دو موتور ذخیره‌سازی و پرس‌وجوی جدا تبدیل می‌شوند که از رابط SQL مشترک در دسترس‌اند [۴۹، ۵۰، ۵۱].

فروشندگان انبار داده مانند Teradata، Vertica، SAP HANA و ParAccel معمولاً سیستم‌هایشان را با مجوزهای تجاری گران می‌فروشند. Amazon RedShift نسخهٔ میزبانی‌شدهٔ ParAccel است. اخیراً انبوهی از پروژه‌های متن‌باز SQL-on-Hadoop ظهور کرده‌اند؛ جوان‌اند اما قصد رقابت با انبارهای دادهٔ تجاری را دارند. از جمله Apache Hive، Spark SQL، Cloudera Impala، Facebook Presto، Apache Tajo و Apache Drill [۵۲، ۵۳]. برخی بر ایده‌های Dremel گوگل [۵۴] استوارند.

ستاره‌ها و دانه‌برفی: طرحواره‌های تحلیلی

همان‌طور که در فصل ۲ دیدیم، طیف وسیعی از مدل‌های داده در حوزهٔ پردازش تراکنش بسته به نیاز برنامه به‌کار می‌رود. در تحلیل، تنوع مدل داده بسیار کمتر است. بسیاری از انبارهای داده به سبک نسبتاً فرمولی به‌نام طرحواره ستاره‌ای (star schema، که مدل‌سازی بعدی [۵۵] هم نامیده می‌شود) استفاده می‌شوند.

طرحوارهٔ نمونه در شکل ۳-۹ انبار داده‌ای را نشان می‌دهد که ممکن است در خرده‌فروشی مواد غذایی باشد. در مرکز طرحواره جدولی به‌نام جدول واقعیت (fact table) است (در این مثال fact_sales). هر سطر جدول واقعیت رویدادی را در زمان مشخص نشان می‌دهد (اینجا هر سطر خرید مشتری از یک محصول). اگر به‌جای فروش خرده‌فروشی، ترافیک وب را تحلیل می‌کردیم، هر سطر ممکن است بازدید صفحه یا کلیک کاربر باشد.

شکل ۳-۹. نمونهٔ طرحواره ستاره‌ای برای انبار داده.

معمولاً واقعیت‌ها به‌صورت رویدادهای تکی ثبت می‌شوند چون انعطاف تحلیل بعدی را حداکثر می‌کند. اما یعنی جدول واقعیت می‌تواند بسیار بزرگ شود. بنگاه بزرگی مانند Apple، Walmart یا eBay ممکن است ده‌ها پتابایت تاریخچهٔ تراکنش در انبار داده داشته باشد که بیشتر آن در جداول واقعیت است [۵۶].

برخی ستون‌های جدول واقعیت ویژگی‌اند، مانند قیمتی که محصول فروخته شد و هزینهٔ خرید از تأمین‌کننده (که حاشیهٔ سود را محاسبه می‌کند). ستون‌های دیگر کلیدهای خارجی به جداول دیگر به‌نام جداول بعد (dimension tables) هستند. چون هر سطر جدول واقعیت یک رویداد را نشان می‌دهد، ابعاد نشان‌دهندهٔ چه کسی، چه چیزی، کجا، چه زمانی، چگونه و چرا رویداد هستند.

مثلاً در شکل ۳-۹ یکی از ابعاد محصول فروخته‌شده است. هر سطر در dim_product یک نوع محصول قابل فروش را نشان می‌دهد، شامل SKU، توصیف، نام برند، دسته، میزان چربی، اندازهٔ بسته و غیره. هر سطر در fact_sales با کلید خارجی نشان می‌دهد در آن تراکنش کدام محصول فروخته شد. (برای سادگی، اگر مشتری چند محصول مختلف یک‌جا بخرد، به‌صورت سطرهای جدا در جدول واقعیت نشان داده می‌شوند.)

حتی تاریخ و زمان اغلب با جداول بعد نمایش داده می‌شوند، چون اطلاعات اضافی دربارهٔ تاریخ (مانند تعطیلات رسمی) را امکان‌پذیر می‌کند و پرس‌وجوها می‌توانند فروش در تعطیلات و غیرتعطیلات را تفکیک کنند.

نام «طرحواره ستاره‌ای» از این می‌آید که وقتی روابط جداول visualize شوند، جدول واقعیت در وسط و جداول بعد دور آن‌اند؛ اتصالات به آن جداول مانند پرتوهای ستاره‌اند.

گونه‌ای از این قالب طرحواره دانه‌برفی (snowflake schema) نامیده می‌شود که ابعاد بیشتر به زیربعدها تقسیم می‌شوند. مثلاً جداول جدا برای برندها و دسته‌های محصول وجود داشته باشد و هر سطر در dim_product به برند و دسته به‌عنوان کلید خارجی ارجاع دهد به‌جای ذخیره به‌صورت رشته در خود dim_product. طرحواره‌های دانه‌برفی نرمال‌تر از ستاره‌ای‌اند، اما طرحواره ستاره‌ای اغلب ترجیح داده می‌شود چون برای تحلیل‌گران ساده‌تر است [۵۵].

در انبار دادهٔ معمولی، جداول اغلب بسیار عریض‌اند: جداول واقعیت اغلب بیش از ۱۰۰ ستون و گاهی چندصد ستون دارند [۵۱]. جداول بعد هم می‌توانند بسیار عریض باشند چون همهٔ متادیتایی که ممکن است برای تحلیل مرتبط باشد را شامل می‌شوند — مثلاً dim_store ممکن است جزئیات خدمات هر فروشگاه، وجود نانوایی درون فروشگاه، متراژ، تاریخ افتتاح، آخرین بازسازی، فاصله از بزرگراه نزدیک و غیره را داشته باشد.

ذخیره‌سازی ستون‌گرا

اگر تریلیون‌ها سطر و پتابایت داده در جداول واقعیت دارید، ذخیره و پرس‌وجوی کارآمد آن‌ها چالش‌برانگیز می‌شود. جداول بعد معمولاً بسیار کوچک‌ترند (میلیون‌ها سطر)، پس در این بخش عمدتاً روی ذخیرهٔ واقعیت‌ها تمرکز می‌کنیم.

اگرچه جداول واقعیت اغلب بیش از ۱۰۰ ستون عریض‌اند، پرس‌وجوی معمول انبار داده فقط ۴ یا ۵ ستون را در هر بار دسترسی می‌دهد (پرس‌وجوهای SELECT * برای تحلیل به‌ندرت لازم‌اند) [۵۱]. پرس‌وجوی مثال ۳-۱ را ببینید: به تعداد زیادی سطر (هر وقوع خرید میوه یا شیرینی در سال تقویمی ۲۰۱۳) دسترسی دارد، اما فقط به سه ستون fact_sales نیاز دارد: date_key، product_sk و quantity. پرس‌وجو بقیهٔ ستون‌ها را نادیده می‌گیرد.

مثال ۳-۱. تحلیل اینکه آیا مردم بسته به روز هفته بیشتر به میوهٔ تازه یا شیرینی تمایل دارند

SELECT
  dim_date.weekday, dim_product.category,
  SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
  JOIN dim_date    ON fact_sales.date_key = dim_date.date_key
  JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
  dim_date.year = 2013 AND
  dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
  dim_date.weekday, dim_product.category;

چگونه این پرس‌وجو را کارآمد اجرا کنیم؟

در بیشتر پایگاه‌های OLTP، ذخیره‌سازی به‌صورت سطر‌گرا (row-oriented) چیده شده: همهٔ مقادیر یک سطر جدول کنار هم ذخیره می‌شوند. پایگاه‌های سندی مشابه‌اند: کل سند معمولاً به‌صورت دنبالهٔ پیوسته‌ای از بایت‌ها ذخیره می‌شود. در مثال CSV شکل ۳-۱ می‌بینید.

برای پردازش پرس‌وجویی مانند مثال ۳-۱، ممکن است ایندکس روی fact_sales.date_key و/یا fact_sales.product_sk داشته باشید که به موتور ذخیره‌سازی می‌گوید همهٔ فروش‌های تاریخ یا محصول خاص کجاست. اما موتور ذخیره‌سازی سطر‌گرا همچنان باید همهٔ آن سطرها (هر کدام بیش از ۱۰۰ ویژگی) را از دیسک به حافظه بارگذاری، parse و فیلتر کند. این می‌تواند زمان زیادی ببرد.

ایدهٔ پشت ذخیره‌سازی ستون‌گرا ساده است: همهٔ مقادیر یک سطر را با هم ذخیره نکنید، بلکه همهٔ مقادیر هر ستون را با هم ذخیره کنید. اگر هر ستون در فایل جداگانه ذخیره شود، پرس‌وجو فقط ستون‌های استفاده‌شده را می‌خواند و parse می‌کند که کار زیادی صرفه‌جویی می‌کند. این اصل در شکل ۳-۱۰ نشان داده شده.

ذخیره‌سازی ستونی در مدل رابطه‌ای آسان‌تر فهمیده می‌شود، اما به دادهٔ غیررابطه‌ای هم اعمال می‌شود. مثلاً Parquet [۵۷] قالب ذخیره‌سازی ستونی است که مدل دادهٔ سندی را پشتیبانی می‌کند، بر پایهٔ Dremel گوگل [۵۴].

شکل ۳-۱۰. ذخیرهٔ دادهٔ رابطه‌ای بر اساس ستون، نه سطر.

چیدمان ذخیره‌سازی ستون‌گرا بر این استوار است که هر فایل ستون سطرها را به همان ترتیب دارد. پس برای بازسازی کل سطر می‌توانید ورودی ۲۳ام هر فایل ستون را بگیرید و کنار هم بگذارید تا سطر ۲۳ام جدول شود.

فشرده‌سازی ستون

علاوه بر بارگذاری فقط ستون‌های لازم از دیسک، می‌توان با فشرده‌سازی داده تقاضای بیشتری روی پهنای باند دیسک را کم کرد. خوشبختانه ذخیره‌سازی ستون‌گرا اغلب برای فشرده‌سازی بسیار مناسب است.

به دنبالهٔ مقادیر هر ستون در شکل ۳-۱۰ نگاه کنید: اغلب تکراری به نظر می‌رسند که نشانهٔ خوبی برای فشرده‌سازی است. بسته به دادهٔ ستون، تکنیک‌های فشرده‌سازی مختلف قابل استفاده‌اند. تکنیکی که در انبار داده به‌ویژه مؤثر است رمزگذاری بیت‌مپ (bitmap encoding) است، همان‌طور که در شکل ۳-۱۱ نشان داده شده.

شکل ۳-۱۱. ذخیرهٔ فشرده و ایندکس‌شده با بیت‌مپ یک ستون.

اغلب تعداد مقادیر متمایز در یک ستون نسبت به تعداد سطرها کم است (مثلاً خرده‌فروش ممکن است میلیاردها تراکنش فروش داشته باشد اما فقط ۱۰۰٬۰۰۰ محصول متمایز). می‌توانیم ستونی با n مقدار متمایز را به n بیت‌مپ جدا تبدیل کنیم: یک بیت‌مپ برای هر مقدار متمایز با یک بیت به ازای هر سطر. بیت ۱ است اگر سطر آن مقدار را دارد و ۰ اگر نه.

اگر n خیلی کم باشد (مثلاً ستون کشور حدود ۲۰۰ مقدار متمایز دارد)، آن بیت‌مپ‌ها را می‌توان با یک بیت به ازای هر سطر ذخیره کرد. اما اگر n بزرگ‌تر باشد، در بیشتر بیت‌مپ‌ها صفر زیاد است (می‌گوییم پراکنده یا sparse هستند). در آن حالت بیت‌مپ‌ها را می‌توان با رمزگذاری طول اجرا (run-length encoding) فشرده‌تر کرد، همان‌طور که در پایین شکل ۳-۱۱ نشان داده شده. این می‌تواند رمزگذاری یک ستون را فوق‌العاده فشرده کند.

ایندکس‌های بیت‌مپ مانند این برای پرس‌وجوهای رایج در انبار داده بسیار مناسب‌اند. مثلاً:

WHERE product_sk IN (30, 68, 69): : سه بیت‌مپ برای product_sk = 30، 68 و 69 را بارگذاری کنید و OR بیتی سه بیت‌مپ را محاسبه کنید که بسیار کارآمد است.

WHERE product_sk = 31 AND store_sk = 3: : بیت‌مپ‌های product_sk = 31 و store_sk = 3 را بارگذاری و AND بیتی محاسبه کنید. این کار می‌کند چون ستون‌ها سطرها را به همان ترتیب دارند، پس بیت kام یک بیت‌مپ با بیت kام بیت‌مپ ستون دیگر به همان سطر مربوط است.

طرح‌های فشرده‌سازی دیگری برای انواع مختلف داده وجود دارد که جزئیاتشان را نمی‌گوییم — برای مرور [۵۸] را ببینید.

ذخیره‌سازی ستون‌گرا و خانواده‌های ستون

Cassandra و HBase مفهوم column family را از Bigtable [۹] به ارث برده‌اند. اما نامیدن آن‌ها ستون‌گرا گمراه‌کننده است: درون هر column family همهٔ ستون‌های یک سطر با هم و همراه کلید سطر ذخیره می‌شوند و از فشرده‌سازی ستون استفاده نمی‌کنند. پس مدل Bigtable عمدتاً همچنان سطر‌گراست.

پهنای باند حافظه و پردازش برداری

برای پرس‌وجوهای انبار داده که باید میلیون‌ها سطر را اسکن کنند، گلوگاه بزرگ پهنای باند انتقال داده از دیسک به حافظه است. اما تنها گلوگاه نیست. توسعه‌دهندگان پایگاه‌های تحلیلی هم به استفادهٔ کارآمد از پهنای باند حافظه اصلی به کش CPU، اجتناب از پیش‌بینی اشتباه شاخه و حباب در خط لولهٔ پردازش دستورالعمل CPU، و بهره‌گیری از دستورالعمل‌های SIMD (تک‌دستورالعمل–چندداده) در CPUهای مدرن [۵۹، ۶۰] اهمیت می‌دهند.

علاوه بر کاهش حجم داده‌ای که باید از دیسک بارگذاری شود، چیدمان ذخیره‌سازی ستون‌گرا برای استفادهٔ کارآمد از چرخه‌های CPU هم خوب است. مثلاً موتور پرس‌وجو می‌تواند تکه‌ای از دادهٔ ستون فشرده که راحت در کش L1 CPU جا می‌شود بگیرد و در حلقهٔ تنگ (بدون فراخوانی تابع) روی آن تکرار کند. CPU چنین حلقه‌ای را بسیار سریع‌تر از کدی که برای هر رکورد فراخوانی و شرط زیاد می‌خواهد اجرا می‌کند. فشرده‌سازی ستون اجازه می‌دهد سطرهای بیشتری از یک ستون در همان مقدار کش L1 جا شوند. عملگرهایی مانند AND و OR بیتی توصیف‌شده می‌توانند مستقیماً روی چنین تکه‌های دادهٔ ستون فشرده طراحی شوند. این تکنیک پردازش برداری (vectorized processing) [۵۸، ۴۹] نامیده می‌شود.

ترتیب مرتب‌سازی در ذخیره‌سازی ستونی

در مخزن ستونی، لزوماً مهم نیست سطرها به چه ترتیبی ذخیره شوند. ساده‌ترین راه ذخیره به ترتیب درج است، چون درج سطر جدید فقط افزودن به هر فایل ستون است. اما می‌توانیم ترتیبی را تحمیل کنیم، همان‌طور که با SSTableها کردیم، و از آن به‌عنوان مکانیزم ایندکس استفاده کنیم.

توجه کنید مرتب‌سازی هر ستون جداگانه معنا ندارد، چون دیگر نمی‌دانیم کدام آیتم‌ها در ستون‌ها به یک سطر تعلق دارند. فقط می‌توانیم سطر را بازسازی کنیم چون می‌دانیم آیتم kام یک ستون به همان سطر آیتم kام ستون دیگر تعلق دارد.

بلکه داده باید کل سطر را یک‌جا مرتب کند، حتی اگر بر اساس ستون ذخیره شود. مدیر پایگاه داده می‌تواند با دانش پرس‌وجوهای رایج ستون‌هایی را که جدول باید بر اساس آن‌ها مرتب شود انتخاب کند. مثلاً اگر پرس‌وجوها اغلب بازهٔ تاریخ مانند ماه گذشته را هدف می‌گیرند، منطقی است date_key اولین کلید مرتب‌سازی باشد. آنگاه بهینه‌ساز پرس‌وجو فقط سطرهای ماه گذشته را اسکن می‌کند که بسیار سریع‌تر از اسکن همهٔ سطرهاست.

ستون دوم می‌تواند ترتیب مرتب‌سازی سطرهایی با همان مقدار در ستون اول را تعیین کند. مثلاً اگر date_key اولین کلید مرتب در شکل ۳-۱۰ باشد، منطقی است product_sk دومین کلید باشد تا همهٔ فروش‌های همان محصول در همان روز در ذخیره‌سازی گروه‌بندی شوند. این به پرس‌وجوهایی که باید فروش را بر اساس محصول در بازهٔ تاریخی گروه‌بندی یا فیلتر کنند کمک می‌کند.

مزیت دیگر ترتیب مرتب کمک به فشرده‌سازی ستون‌هاست. اگر ستون کلید مرتب‌سازی اولیه مقادیر متمایز زیادی نداشته باشد، پس از مرتب‌سازی دنباله‌های طولانی تکرار همان مقدار پشت سر هم می‌آید. رمزگذاری سادهٔ طول اجرا، مانند بیت‌مپ‌های شکل ۳-۱۱، می‌تواند آن ستون را به چند کیلوبایت فشرده کند — حتی اگر جدول میلیاردها سطر داشته باشد.

این اثر فشرده‌سازی روی کلید مرتب‌سازی اول قوی‌ترین است. کلیدهای دوم و سوم بیشتر درهم می‌شوند و دنباله‌های تکرار طولانی کمتری ندارند. ستون‌های پایین‌تر در اولویت مرتب‌سازی تقریباً تصادفی‌اند و احتمالاً خوب فشرده نمی‌شوند. اما مرتب بودن چند ستون اول در مجموع برد است.

چند ترتیب مرتب‌سازی مختلف

گسترش هوشمندانهٔ این ایده در C-Store معرفی و در انبار دادهٔ تجاری Vertica پذیرفته شد [۶۱، ۶۲]. پرس‌وجوهای مختلف از ترتیب‌های مرتب مختلف سود می‌برند، پس چرا همان داده را به چند روش مرتب ذخیره نکنیم؟ داده به هر حال باید روی چند ماشین تکرار شود تا با خرابی یک ماشین از دست نرود. می‌توان همان دادهٔ تکراری را به روش‌های مرتب مختلف ذخیره کرد تا هنگام پردازش پرس‌وجو از نسخه‌ای استفاده کنید که با الگوی پرس‌وجو بهتر می‌خواند.

داشتن چند ترتیب مرتب در مخزن ستونی کمی شبیه داشتن چند ایندکس ثانویه در مخزن سطر‌گراست. اما تفاوت بزرگ این است که مخزن سطر‌گرا هر سطر را در یک جا نگه می‌دارد (در فایل heap یا ایندکس خوشه‌ای) و ایندکس‌های ثانویه فقط اشاره به سطرهای منطبق دارند. در مخزن ستونی معمولاً اشاره‌گری به دادهٔ جای دیگر نیست، فقط ستون‌های حاوی مقادیر.

نوشتن در ذخیره‌سازی ستون‌گرا

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

رویکرد به‌روزرسانی درجا، مانند درخت B، با ستون‌های فشرده ممکن نیست. اگر بخواهید سطری را وسط جدول مرتب درج کنید، احتمالاً باید همهٔ فایل‌های ستون را بازنویسی کنید. چون سطرها با موقعیتشان در ستون شناسایی می‌شوند، درج باید همهٔ ستون‌ها را به‌طور سازگار به‌روز کند.

خوشبختانه راه‌حل خوبی را قبلاً در این فصل دیدیم: LSM-treeها. همهٔ نوشتن‌ها ابتدا به مخزن درون‌حافظه می‌روند، به ساختار مرتب اضافه و برای نوشتن روی دیسک آماده می‌شوند. مهم نیست مخزن درون‌حافظه سطر‌گرا باشد یا ستون‌گرا. وقتی نوشتن‌های کافی جمع شد، با فایل‌های ستون روی دیسک ادغام و به‌صورت انبوه به فایل‌های جدید نوشته می‌شوند. اساساً همین کاری است که Vertica انجام می‌دهد [۶۲].

پرس‌وجوها باید هم دادهٔ ستون روی دیسک و هم نوشتن‌های اخیر در حافظه را بررسی و ترکیب کنند. اما بهینه‌ساز پرس‌وجو این تمایز را از کاربر پنهان می‌کند. از دید تحلیل‌گر، داده‌ای که با درج، به‌روزرسانی یا حذف تغییر کرده فوراً در پرس‌وجوهای بعدی منعکس می‌شود.

تجمیع: مکعب داده و نماهای مادی‌شده

هر انبار داده لزوماً مخزن ستونی نیست: پایگاه‌های سنتی سطر‌گرا و چند معماری دیگر هم به‌کار می‌روند. اما ذخیره‌سازی ستونی می‌تواند برای پرس‌وجوهای تحلیلی ad hoc به‌طور قابل توجهی سریع‌تر باشد و به‌سرعت محبوب‌تر می‌شود [۵۱، ۶۳].

جنبهٔ دیگر انبار داده که ارزش اشارهٔ مختصر دارد تجمیع‌های مادی‌شده (materialized aggregates) است. همان‌طور که گفتیم، پرس‌وجوهای انبار داده اغلب تابع تجمیعی مانند COUNT، SUM، AVG، MIN یا MAX در SQL دارند. اگر همان تجمیع‌ها در پرس‌وجوهای زیاد استفاده شوند، هر بار خرد کردن دادهٔ خام اتلاف است. چرا برخی شمارش‌ها یا مجموع‌های پرکاربرد را کش نکنیم؟

یک راه ساخت چنین کشی نمای مادی‌شده (materialized view) است. در مدل رابطه‌ای اغلب مانند نمای (مجازی) استاندارد تعریف می‌شود: شیء شبیه جدول که محتوایش نتیجهٔ پرس‌وجویی است. تفاوت این است که نمای مادی‌شده کپی واقعی نتایج پرس‌وجو است که روی دیسک نوشته شده، در حالی که نمای مجازی فقط میان‌بری برای نوشتن پرس‌وجوست. وقتی از نمای مجازی می‌خوانید، موتور SQL آن را روی پرواز به پرس‌وجوی زیرین گسترش می‌دهد و پرس‌وجوی گسترش‌یافته را پردازش می‌کند.

وقتی دادهٔ زیرین تغییر می‌کند، نمای مادی‌شده باید به‌روز شود چون کپی غیرنرمال‌شدهٔ داده است. پایگاه داده می‌تواند این را خودکار انجام دهد، اما چنین به‌روزرسانی‌هایی نوشتن را گران‌تر می‌کند و به همین دلیل نماهای مادی‌شده در پایگاه‌های OLTP کمتر به‌کار می‌روند. در انبارهای دادهٔ با خواندن سنگین می‌تواند معقول‌تر باشد (آیا واقعاً خواندن را بهبود می‌دهد به مورد بستگی دارد).

مورد ویژهٔ رایج نمای مادی‌شده مکعب داده (data cube) یا مکعب OLAP [۶۴] نامیده می‌شود. شبکه‌ای از تجمیع‌هاست که بر اساس ابعاد مختلف گروه‌بندی شده‌اند. شکل ۳-۱۲ نمونه‌ای نشان می‌دهد.

شکل ۳-۱۲. دو بعد از یک مکعب داده، تجمیع داده با جمع.

فعلاً فرض کنید هر واقعیت فقط به دو جدول بعد کلید خارجی دارد — در شکل ۳-۱۲ تاریخ و محصول. می‌توانید جدول دوبعدی بکشید با تاریخ در یک محور و محصول در دیگری. هر سلول تجمیع (مثلاً SUM) ویژگی (مثلاً net_price) همهٔ واقعیت‌ها با آن ترکیب تاریخ-محصول را دارد. سپس همان تجمیع را در هر سطر یا ستون اعمال می‌کنید و خلاصه‌ای با یک بعد کمتر می‌گیرید (فروش بر اساس محصول صرف‌نظر از تاریخ، یا فروش بر اساس تاریخ صرف‌نظر از محصول).

به‌طور کلی، واقعیت‌ها اغلب بیش از دو بعد دارند. در شکل ۳-۹ پنج بعد وجود دارد: تاریخ، محصول، فروشگاه، پروموشن و مشتری. تصور مکعب پنج‌بعدی سخت‌تر است، اما اصل همان است: هر سلول فروش برای ترکیب خاص تاریخ-محصول-فروشگاه-پروموشن-مشتری را دارد. این مقادیر را می‌توان بارها در هر بعد خلاصه کرد.

مزیت مکعب دادهٔ مادی‌شده این است که برخی پرس‌وجوها بسیار سریع می‌شوند چون عملاً از پیش محاسبه شده‌اند. مثلاً اگر بخواهید فروش کل هر فروشگاه دیروز را بدانید، فقط به مجموع‌ها در بعد مناسب نگاه می‌کنید — نیازی به اسکن میلیون‌ها سطر نیست.

عیب مکعب داده انعطاف کمتری نسبت به پرس‌وجوی دادهٔ خام دارد. مثلاً راهی برای محاسبهٔ سهم فروش اقلامی با قیمت بالای ۱۰۰ دلار نیست چون قیمت یکی از ابعاد نیست. بیشتر انبارهای داده سعی می‌کنند تا حد ممکن دادهٔ خام را نگه دارند و تجمیع‌هایی مانند مکعب داده فقط به‌عنوان تقویت عملکرد برای برخی پرس‌وجوها به‌کار برند.

خلاصه

در این فصل سعی کردیم به عمق برویم و ببینیم پایگاه‌داده‌ها چگونه ذخیره‌سازی و بازیابی را مدیریت می‌کنند. وقتی داده را در پایگاه داده ذخیره می‌کنید چه می‌گذرد، و وقتی بعداً داده را می‌پرسید پایگاه داده چه می‌کند؟

در سطح بالا دیدیم موتورهای ذخیره‌سازی به دو دستهٔ گسترده می‌افتند: آن‌هایی که برای پردازش تراکنش (OLTP) بهینه شده‌اند، و آن‌هایی که برای تحلیل (OLAP). تفاوت‌های بزرگی بین الگوهای دسترسی در این موارد استفاده وجود دارد:

• سیستم‌های OLTP معمولاً رو به کاربرند و ممکن است حجم عظیمی درخواست ببینند. برای مدیریت بار، برنامه‌ها معمولاً در هر پرس‌وجو فقط تعداد کمی رکورد را لمس می‌کنند. برنامه با نوعی کلید رکوردها را درخواست می‌کند و موتور ذخیره‌سازی با ایندکس دادهٔ کلید درخواستی را پیدا می‌کند. زمان seek دیسک اغلب گلوگاه اینجاست.
• انبارهای داده و سیستم‌های تحلیلی مشابه کمتر شناخته‌شده‌اند چون عمدتاً توسط تحلیل‌گران کسب‌وکار استفاده می‌شوند نه کاربران نهایی. حجم پرس‌وجوی کمتری نسبت به OLTP دارند، اما هر پرس‌وجو معمولاً بسیار سنگین است و باید میلیون‌ها رکورد را در زمان کوتاه اسکن کند. پهنای باند دیسک (نه زمان seek) اغلب گلوگاه اینجاست و ذخیره‌سازی ستون‌گرا راه‌حل روزبه‌روز رایج‌تری برای این بار کاری است.

در سمت OLTP، موتورهای ذخیره‌سازی از دو مکتب اصلی دیدیم:

• مکتب ساختاریافته بر پایهٔ لاگ، که فقط افزودن به فایل‌ها و حذف فایل‌های منسوخ را مجاز می‌داند اما هرگز فایل نوشته‌شده را به‌روز نمی‌کند. Bitcask، SSTableها، LSM-treeها، LevelDB، Cassandra، HBase، Lucene و دیگران به این گروه تعلق دارند.
• مکتب به‌روزرسانی درجا، که دیسک را مجموعه‌ای از صفحات با اندازهٔ ثابت می‌بیند که می‌توان بازنویسی کرد. درخت‌های B بزرگ‌ترین نمونهٔ این فلسفه‌اند و در همهٔ پایگاه‌های رابطه‌ای اصلی و بسیاری از غیررابطه‌ای‌ها به‌کار می‌روند.

موتورهای ساختاریافته بر پایهٔ لاگ توسعهٔ نسبتاً اخیرند. ایدهٔ کلیدی‌شان تبدیل سیستماتیک نوشتن‌های دسترسی تصادفی به نوشتن‌های ترتیبی روی دیسک است که به‌خاطر ویژگی‌های عملکردی هارد و SSD توان نوشتن بالاتری می‌دهد.

در پایان سمت OLTP، گشتی کوتاه به ساختارهای ایندکس پیچیده‌تر و پایگاه‌داده‌هایی زدیم که برای نگه‌داشتن همهٔ داده در حافظه بهینه شده‌اند. سپس از درون موتورهای ذخیره‌سازی منحرف شدیم و معماری سطح بالای یک انبار دادهٔ معمولی را دیدیم. این زمینه توضیح داد چرا بارهای تحلیلی با OLTP این‌قدر متفاوت‌اند: وقتی پرس‌وجوها نیاز به اسکن ترتیبی روی تعداد زیادی سطر دارند، ایندکس‌ها کمتر اهمیت دارند. در عوض فشرده‌سازی داده بسیار مهم می‌شود تا حداقل داده‌ای که پرس‌وجو باید از دیسک بخواند. دیدیم ذخیره‌سازی ستون‌گرا چگونه به این هدف کمک می‌کند.

به‌عنوان توسعه‌دهندهٔ برنامه، اگر این دانش دربارهٔ درون موتورهای ذخیره‌سازی را داشته باشید، در موقعیت بهتری برای دانستن اینکه کدام ابزار برای برنامهٔ خاص شما مناسب‌تر است قرار می‌گیرید. اگر بخواهید پارامترهای تنظیم پایگاه داده را تغییر دهید، این درک به شما کمک می‌کند اثر مقدار بالاتر یا پایین‌تر را تصور کنید.

اگرچه این فصل شما را در تنظیم یک موتور ذخیره‌سازی خاص متخصص نکرد، امیدواریم واژگان و ایده‌های کافی داده باشد تا بتوانید مستندات پایگاه دادهٔ انتخابی‌تان را بفهمید.

منابع

[۱] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman: Data Structures and Algorithms. Addison-Wesley, 1983. ISBN: 978-0-201-00023-8

[۲] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, 3rd edition. MIT Press, 2009. ISBN: 978-0-262-53305-8

[۳] Justin Sheehy and David Smith: "Bitcask: A Log-Structured Hash Table for Fast Key/Value Data," Basho Technologies, April 2010.

[۴] Yinan Li, Bingsheng He, Robin Jun Yang, et al.: "Tree Indexing on Solid State Drives," Proceedings of the VLDB Endowment, volume 3, number 1, pages 1195–1206, September 2010.

[۵] Goetz Graefe: "Modern B-Tree Techniques," Foundations and Trends in Databases, volume 3, number 4, pages 203–402, August 2011. doi:10.1561/1900000028

[۶] Jeffrey Dean and Sanjay Ghemawat: "LevelDB Implementation Notes," leveldb.googlecode.com.

[۷] Dhruba Borthakur: "The History of RocksDB," rocksdb.blogspot.com, November 24, 2013.

[۸] Matteo Bertozzi: "Apache HBase I/O – HFile," blog.cloudera.com, June, 29 2012.

[۹] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, et al.: "Bigtable: A Distributed Storage System for Structured Data," at 7th USENIX Symposium on Operating System Design and Implementation (OSDI), November 2006.

[۱۰] Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil: "The Log-Structured Merge-Tree (LSM-Tree)," Acta Informatica, volume 33, number 4, pages 351–385, June 1996. doi:10.1007/s002360050048

[۱۱] Mendel Rosenblum and John K. Ousterhout: "The Design and Implementation of a Log-Structured File System," ACM Transactions on Computer Systems, volume 10, number 1, pages 26–52, February 1992. doi:10.1145/146941.146943

[۱۲] Adrien Grand: "What Is in a Lucene Index?," at Lucene/Solr Revolution, November 14, 2013.

[۱۳] Deepak Kandepet: "Hacking Lucene—The Index Format," hackerlabs.org, October 1, 2011.

[۱۴] Michael McCandless: "Visualizing Lucene's Segment Merges," blog.mikemccandless.com, February 11, 2011.

[۱۵] Burton H. Bloom: "Space/Time Trade-offs in Hash Coding with Allowable Errors," Communications of the ACM, volume 13, number 7, pages 422–426, July 1970. doi:10.1145/362686.362692

[۱۶] "Operating Cassandra: Compaction," Apache Cassandra Documentation v4.0, 2016.

[۱۷] Rudolf Bayer and Edward M. McCreight: "Organization and Maintenance of Large Ordered Indices," Boeing Scientific Research Laboratories, Mathematical and Information Sciences Laboratory, report no. 20, July 1970.

[۱۸] Douglas Comer: "The Ubiquitous B-Tree," ACM Computing Surveys, volume 11, number 2, pages 121–137, June 1979. doi:10.1145/356770.356776

[۱۹] Emmanuel Goossaert: "Coding for SSDs," codecapsule.com, February 12, 2014.

[۲۰] C. Mohan and Frank Levine: "ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging," at ACM International Conference on Management of Data (SIGMOD), June 1992. doi:10.1145/130283.130338

[۲۱] Howard Chu: "LDAP at Lightning Speed," at Build Stuff '14, November 2014.

[۲۲] Bradley C. Kuszmaul: "A Comparison of Fractal Trees to Log-Structured Merge (LSM) Trees," tokutek.com, April 22, 2014.

[۲۳] Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, et al.: "Designing Access Methods: The RUM Conjecture," at 19th International Conference on Extending Database Technology (EDBT), March 2016. doi:10.5441/002/edbt.2016.42

[۲۴] Peter Zaitsev: "Innodb Double Write," percona.com, August 4, 2006.

[۲۵] Tomas Vondra: "On the Impact of Full-Page Writes," blog.2ndquadrant.com, November 23, 2016.

[۲۶] Mark Callaghan: "The Advantages of an LSM vs a B-Tree," smalldatum.blogspot.co.uk, January 19, 2016.

[۲۷] Mark Callaghan: "Choosing Between Efficiency and Performance with RocksDB," at Code Mesh, November 4, 2016.

[۲۸] Michi Mutsuzaki: "MySQL vs. LevelDB," github.com, August 2011.

[۲۹] Benjamin Coverston, Jonathan Ellis, et al.: "CASSANDRA-1608: Redesigned Compaction, issues.apache.org, July 2011.

[۳۰] Igor Canadi, Siying Dong, and Mark Callaghan: "RocksDB Tuning Guide," github.com, 2016.

[۳۱] MySQL 5.7 Reference Manual. Oracle, 2014.

[۳۲] Books Online for SQL Server 2012. Microsoft, 2012.

[۳۳] Joe Webb: "Using Covering Indexes to Improve Query Performance," simple-talk.com, 29 September 2008.

[۳۴] Frank Ramsak, Volker Markl, Robert Fenk, et al.: "Integrating the UB-Tree into a Database System Kernel," at 26th International Conference on Very Large Data Bases (VLDB), September 2000.

[۳۵] The PostGIS Development Group: "PostGIS 2.1.2dev Manual," postgis.net, 2014.

[۳۶] Robert Escriva, Bernard Wong, and Emin Gün Sirer: "HyperDex: A Distributed, Searchable Key-Value Store," at ACM SIGCOMM Conference, August 2012. doi:10.1145/2377677.2377681

[۳۷] Michael McCandless: "Lucene's FuzzyQuery Is 100 Times Faster in 4.0," blog.mikemccandless.com, March 24, 2011.

[۳۸] Steffen Heinz, Justin Zobel, and Hugh E. Williams: "Burst Tries: A Fast, Efficient Data Structure for String Keys," ACM Transactions on Information Systems, volume 20, number 2, pages 192–223, April 2002. doi:10.1145/506309.506312

[۳۹] Klaus U. Schulz and Stoyan Mihov: "Fast String Correction with Levenshtein Automata," International Journal on Document Analysis and Recognition, volume 5, number 1, pages 67–85, November 2002. doi:10.1007/s10032-002-0082-8

[۴۰] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze: Introduction to Information Retrieval. Cambridge University Press, 2008. ISBN: 978-0-521-86571-5, available online at nlp.stanford.edu/IR-book

[۴۱] Michael Stonebraker, Samuel Madden, Daniel J. Abadi, et al.: "The End of an Architectural Era (It's Time for a Complete Rewrite)," at 33rd International Conference on Very Large Data Bases (VLDB), September 2007.

[۴۲] "VoltDB Technical Overview White Paper," VoltDB, 2014.

[۴۳] Stephen M. Rumble, Ankita Kejriwal, and John K. Ousterhout: "Log-Structured Memory for DRAM-Based Storage," at 12th USENIX Conference on File and Storage Technologies (FAST), February 2014.

[۴۴] Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker: "OLTP Through the Looking Glass, and What We Found There," at ACM International Conference on Management of Data (SIGMOD), June 2008. doi:10.1145/1376616.1376713

[۴۵] Justin DeBrabant, Andrew Pavlo, Stephen Tu, et al.: "Anti-Caching: A New Approach to Database Management System Architecture," Proceedings of the VLDB Endowment, volume 6, number 14, pages 1942–1953, September 2013.

[۴۶] Joy Arulraj, Andrew Pavlo, and Subramanya R. Dulloor: "Let's Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems," at ACM International Conference on Management of Data (SIGMOD), June 2015. doi:10.1145/2723372.2749441

[۴۷] Edgar F. Codd, S. B. Codd, and C. T. Salley: "Providing OLAP to User-Analysts: An IT Mandate," E. F. Codd Associates, 1993.

[۴۸] Surajit Chaudhuri and Umeshwar Dayal: "An Overview of Data Warehousing and OLAP Technology," ACM SIGMOD Record, volume 26, number 1, pages 65–74, March 1997. doi:10.1145/248603.248616

[۴۹] Per-Åke Larson, Cipri Clinciu, Campbell Fraser, et al.: "Enhancements to SQL Server Column Stores," at ACM International Conference on Management of Data (SIGMOD), June 2013.

[۵۰] Franz Färber, Norman May, Wolfgang Lehner, et al.: "The SAP HANA Database – An Architecture Overview," IEEE Data Engineering Bulletin, volume 35, number 1, pages 28–33, March 2012.

[۵۱] Michael Stonebraker: "The Traditional RDBMS Wisdom Is (Almost Certainly) All Wrong," presentation at EPFL, May 2013.

[۵۲] Daniel J. Abadi: "Classifying the SQL-on-Hadoop Solutions," hadapt.com, October 2, 2013.

[۵۳] Marcel Kornacker, Alexander Behm, Victor Bittorf, et al.: "Impala: A Modern, Open-Source SQL Engine for Hadoop," at 7th Biennial Conference on Innovative Data Systems Research (CIDR), January 2015.

[۵۴] Sergey Melnik, Andrey Gubarev, Jing Jing Long, et al.: "Dremel: Interactive Analysis of Web-Scale Datasets," at 36th International Conference on Very Large Data Bases (VLDB), pages 330–339, September 2010.

[۵۵] Ralph Kimball and Margy Ross: The Data Warehouse Toolkit: The Definitive Guide to Dimensional Modeling, 3rd edition. John Wiley & Sons, July 2013. ISBN: 978-1-118-53080-1

[۵۶] Derrick Harris: "Why Apple, eBay, and Walmart Have Some of the Biggest Data Warehouses You've Ever Seen," gigaom.com, March 27, 2013.

[۵۷] Julien Le Dem: "Dremel Made Simple with Parquet," blog.twitter.com, September 11, 2013.

[۵۸] Daniel J. Abadi, Peter Boncz, Stavros Harizopoulos, et al.: "The Design and Implementation of Modern Column-Oriented Database Systems," Foundations and Trends in Databases, volume 5, number 3, pages 197–280, December 2013. doi:10.1561/1900000024

[۵۹] Peter Boncz, Marcin Zukowski, and Niels Nes: "MonetDB/X100: Hyper-Pipelining Query Execution," at 2nd Biennial Conference on Innovative Data Systems Research (CIDR), January 2005.

[۶۰] Jingren Zhou and Kenneth A. Ross: "Implementing Database Operations Using SIMD Instructions," at ACM International Conference on Management of Data (SIGMOD), pages 145–156, June 2002. doi:10.1145/564691.564709

[۶۱] Michael Stonebraker, Daniel J. Abadi, Adam Batkin, et al.: "C-Store: A Column-oriented DBMS," at 31st International Conference on Very Large Data Bases (VLDB), pages 553–564, September 2005.

[۶۲] Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, et al.: "The Vertica Analytic Database: C-Store 7 Years Later," Proceedings of the VLDB Endowment, volume 5, number 12, pages 1790–1801, August 2012.

[۶۳] Julien Le Dem and Nong Li: "Efficient Data Storage for Analytics with Apache Parquet 2.0," at Hadoop Summit, San Jose, June 2014.

[۶۴] Jim Gray, Surajit Chaudhuri, Adam Bosworth, et al.: "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals," Data Mining and Knowledge Discovery, volume 1, number 1, pages 29–53, March 2007. doi:10.1023/A:1009726021843