فصل ۶ — پارتیشن‌بندی

به‌وضوح باید از توالی‌گرایی فاصله بگیریم و کامپیوترها را محدود نکنیم. باید تعاریف را بیان کنیم و برای اولویت‌ها و توصیف داده‌ها تدارک ببینیم. باید روابط را بیان کنیم، نه رویه‌ها را. — گریس موری هاپر، Management and the Computer of the Future (۱۹۶۲)

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

i. پارتیشن‌بندی، همان‌طور که در این فصل بحث می‌شود، روشی برای شکستن عمدی یک پایگاه داده بزرگ به پایگاه‌های کوچک‌تر است. ربطی به پارتیشن‌های شبکه (netsplit) ندارد؛ نوعی خطا در شبکه بین گره‌ها. چنین خطاهایی را در فصل ۸ بررسی می‌کنیم.

سردرگمی اصطلاحی

آنچه اینجا پارتیشن می‌نامیم در MongoDB، Elasticsearch و SolrCloud shard نامیده می‌شود؛ در HBase region، در Bigtable tablet، در Cassandra و Riak vnode، و در Couchbase vBucket. با این حال partitioning رایج‌ترین اصطلاح است، پس همان را نگه می‌داریم.

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

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

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

پایگاه‌های داده پارتیشن‌بندی‌شده در دهه ۱۹۸۰ توسط محصولاتی مثل Teradata و Tandem NonStop SQL [1] پیشگام شدند، و اخیراً توسط پایگاه‌های داده NoSQL و انبارهای داده مبتنی بر Hadoop دوباره کشف شدند. برخی سیستم‌ها برای بارهای کاری تراکنشی طراحی شده‌اند و برخی دیگر برای تحلیل (به «پردازش تراکنش یا تحلیل؟» در صفحه ۹۰ مراجعه کنید): این تفاوت بر نحوه تنظیم سیستم اثر می‌گذارد، اما اصول پارتیشن‌بندی برای هر دو نوع بار کاری صدق می‌کند.

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

پارتیشن‌بندی و تکثیر

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

یک گره ممکن است بیش از یک پارتیشن ذخیره کند. اگر از مدل تکثیر leader–follower استفاده شود، ترکیب پارتیشن‌بندی و تکثیر می‌تواند شبیه شکل ۶-۱ باشد. leader هر پارتیشن به یک گره اختصاص داده می‌شود و followerهای آن به گره‌های دیگر. هر گره ممکن است leader برخی پارتیشن‌ها و follower پارتیشن‌های دیگر باشد.

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

شکل ۶-۱. ترکیب تکثیر و پارتیشن‌بندی: هر گره برای برخی پارتیشن‌ها leader و برای پارتیشن‌های دیگر follower است.

پارتیشن‌بندی داده کلید-مقدار

فرض کنید مقدار زیادی داده دارید و می‌خواهید آن را پارتیشن‌بندی کنید. چگونه تصمیم می‌گیرید کدام رکوردها روی کدام گره‌ها ذخیره شوند؟

هدف ما با پارتیشن‌بندی، پخش یکنواخت داده و بار پرس‌وجو روی گره‌هاست. اگر هر گره سهم منصفانه‌ای بگیرد، در تئوری — ۱۰ گره باید بتوانند ۱۰ برابر داده و ۱۰ برابر توان خواندن و نوشتن یک گره را مدیریت کنند (فعلاً تکثیر را نادیده می‌گیریم).

اگر پارتیشن‌بندی ناعادلانه باشد، طوری که برخی پارتیشن‌ها داده یا پرس‌وجوی بیشتری داشته باشند، آن را منحرف (skewed) می‌نامیم. وجود انحراف، پارتیشن‌بندی را بسیار کم‌اثر می‌کند. در حالت شدید، تمام بار می‌تواند روی یک پارتیشن متمرکز شود، پس ۹ گره از ۱۰ بیکارند و گلوگاه شما همان گره شلوغ است. پارتیشنی با بار نامتناسب بالا نقطه داغ (hot spot) نامیده می‌شود.

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

می‌توانیم بهتر عمل کنیم. فعلاً فرض کنیم مدل داده ساده کلید-مقدار دارید که همیشه با کلید اصلی به رکورد دسترسی پیدا می‌کنید. مثلاً در یک دایره‌المعارف کاغذی قدیمی، مدخل را با عنوان جستجو می‌کنید؛ چون همه مدخل‌ها بر اساس عنوان به‌صورت الفبایی مرتب‌اند، به‌سرعت آنچه می‌خواهید را پیدا می‌کنید.

پارتیشن‌بندی بر اساس بازه کلید

یکی از روش‌های پارتیشن‌بندی، اختصاص بازه پیوسته‌ای از کلیدها (از حداقلی تا حداکثری) به هر پارتیشن است، مثل جلدهای یک دایره‌المعارف کاغذی (شکل ۶-۲). اگر مرزهای بین بازه‌ها را بدانید، به‌راحتی می‌توانید تعیین کنید کدام پارتیشن کلید داده‌شده را دارد. اگر هم بدانید کدام پارتیشن به کدام گره اختصاص دارد، می‌توانید درخواست را مستقیماً به گره مناسب بفرستید (یا در مورد دایره‌المعارف، کتاب درست را از قفسه بردارید).

شکل ۶-۲. یک دایره‌المعارف چاپی بر اساس بازه کلید پارتیشن‌بندی شده است.

بازه‌های کلید لزوماً به‌طور یکنواخت فاصله ندارند، چون داده شما ممکن است یکنواخت توزیع نشده باشد. مثلاً در شکل ۶-۲، جلد ۱ شامل واژه‌هایی است که با A و B شروع می‌شوند، اما جلد ۱۲ شامل واژه‌هایی است که با T، U، V، X، Y و Z شروع می‌شوند. داشتن یک جلد برای هر دو حرف الفبا منجر به جلدهایی می‌شود که بسیار بزرگ‌تر از بقیه‌اند. برای توزیع یکنواخت داده، مرزهای پارتیشن باید با داده سازگار شوند.

مرزهای پارتیشن ممکن است دستی توسط مدیر انتخاب شوند، یا پایگاه داده می‌تواند آن‌ها را خودکار انتخاب کند (انتخاب مرزهای پارتیشن را در «متعادل‌سازی مجدد پارتیشن‌ها» در صفحه ۲۰۹ با جزئیات بیشتر بحث می‌کنیم). این استراتژی پارتیشن‌بندی توسط Bigtable، معادل متن‌باز آن HBase [2, 3]، RethinkDB و MongoDB قبل از نسخه ۲.۴ [4] استفاده می‌شود.

در هر پارتیشن، می‌توانیم کلیدها را به ترتیب مرتب نگه داریم (به «SSTableها و درخت‌های LSM» در صفحه ۷۶ مراجعه کنید). مزیت این است که اسکن بازه‌ای آسان است و می‌توانید کلید را به‌عنوان نمایه الحاقی در نظر بگیرید تا چند رکورد مرتبط را در یک پرس‌وجو واکشی کنید (به «نمایه‌های چندستونی» در صفحه ۸۷ مراجعه کنید). مثلاً برنامه‌ای را در نظر بگیرید که داده از شبکه‌ای از حسگرها ذخیره می‌کند، که کلید آن برچسب زمانی اندازه‌گیری است (سال-ماه-روز-ساعت-دقیقه-ثانیه). اسکن بازه‌ای در این مورد بسیار مفید است، چون به‌راحتی می‌توانید مثلاً همه قرائت‌های یک ماه خاص را واکشی کنید.

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

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

پارتیشن‌بندی بر اساس هش کلید

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

تابع هش خوب داده منحرف را یکنواخت توزیع می‌کند. فرض کنید تابع هش ۳۲ بیتی دارید که یک رشته می‌گیرد. هر بار رشته جدیدی به آن بدهید، عددی ظاهراً تصادفی بین ۰ و 2^32 − 1 برمی‌گرداند. حتی اگر رشته‌های ورودی بسیار شبیه باشند، هش‌هایشان یکنواخت در آن بازه اعداد پخش می‌شوند.

برای پارتیشن‌بندی، تابع هش لزوماً از نظر رمزنگاری قوی نیست: مثلاً Cassandra و MongoDB از MD5 استفاده می‌کنند و Voldemort از تابع Fowler–Noll–Vo. بسیاری از زبان‌های برنامه‌نویسی توابع هش ساده داخلی دارند (چون برای جدول‌های hash استفاده می‌شوند)، اما ممکن است برای پارتیشن‌بندی مناسب نباشند: مثلاً در Object.hashCode() جاوا و Object#hash روبی، یک کلید ممکن است در فرآیندهای مختلف مقدار هش متفاوتی داشته باشد [6].

وقتی تابع هش مناسب برای کلیدها دارید، می‌توانید به هر پارتیشن بازه‌ای از هش‌ها (نه بازه کلیدها) اختصاص دهید و هر کلیدی که هشش در بازه پارتیشن بیفتد در آن پارتیشن ذخیره می‌شود. این در شکل ۶-۳ نشان داده شده است.

شکل ۶-۳. پارتیشن‌بندی بر اساس هش کلید.

این تکنیک در توزیع منصفانه کلیدها میان پارتیشن‌ها خوب عمل می‌کند. مرزهای پارتیشن می‌توانند به‌طور یکنواخت فاصله داشته باشند، یا شبه‌تصادفی انتخاب شوند (که در این صورت تکنیک گاهی consistent hashing نامیده می‌شود).

هشینگ سازگار (Consistent Hashing)

هشینگ سازگار، همان‌طور که Karger و همکاران [7] تعریف کردند، روشی برای توزیع یکنواخت بار در سیستمی از کش‌ها در مقیاس اینترنت مثل شبکه تحویل محتوا (CDN) است. از مرزهای پارتیشن تصادفی برای اجتناب از نیاز به کنترل مرکزی یا اجماع توزیع‌شده استفاده می‌کند. توجه کنید که consistent اینجا ربطی به سازگاری replica (فصل ۵) یا سازگاری ACID (فصل ۷) ندارد، بلکه رویکرد خاصی به متعادل‌سازی مجدد را توصیف می‌کند.

همان‌طور که در «متعادل‌سازی مجدد پارتیشن‌ها» در صفحه ۲۰۹ می‌بینیم، این رویکرد خاص در عمل برای پایگاه‌های داده خیلی خوب کار نمی‌کند [8]، پس به‌ندرت در عمل استفاده می‌شود (مستندات برخی پایگاه‌های داده هنوز به consistent hashing اشاره می‌کنند، اما اغلب نادرست است). چون این موضوع بسیار گیج‌کننده است، بهتر است از اصطلاح consistent hashing اجتناب کنید و فقط hash partitioning بگویید.

متأسفانه، با استفاده از هش کلید برای پارتیشن‌بندی، ویژگی خوب پارتیشن‌بندی بازه کلید را از دست می‌دهیم: توانایی انجام پرس‌وجوهای بازه‌ای کارآمد. کلیدهایی که قبلاً مجاور بودند حالا در همه پارتیشن‌ها پراکنده‌اند، پس ترتیب مرتب‌سازی‌شان از بین می‌رود. در MongoDB، اگر حالت sharding مبتنی بر هش را فعال کرده باشید، هر پرس‌وجوی بازه‌ای باید به همه پارتیشن‌ها فرستاده شود [4]. پرس‌وجوهای بازه‌ای روی کلید اصلی توسط Riak [9]، Couchbase [10] یا Voldemort پشتیبانی نمی‌شوند.

Cassandra سازشی بین دو استراتژی پارتیشن‌بندی دست می‌دهد [11, 12, 13]. جدول در Cassandra می‌تواند با کلید اصلی مرکب شامل چند ستون تعریف شود. فقط بخش اول آن کلید برای تعیین پارتیشن هش می‌شود، اما ستون‌های دیگر به‌عنوان نمایه الحاقی برای مرتب‌سازی داده در SSTableهای Cassandra استفاده می‌شوند. بنابراین پرس‌وجو نمی‌تواند بازه‌ای از مقادیر در ستون اول کلید مرکب را جستجو کند، اما اگر مقدار ثابتی برای ستون اول مشخص کند، می‌تواند اسکن بازه‌ای کارآمد روی ستون‌های دیگر کلید انجام دهد.

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

بارهای کاری منحرف و کاهش نقاط داغ

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

این نوع بار کاری شاید غیرمعمول باشد، اما ناشنیده نیست: مثلاً در یک سایت رسانه اجتماعی، کاربر مشهوری با میلیون‌ها دنبال‌کننده ممکن است با انجام کاری طوفان فعالیت ایجاد کند [14]. این رویداد می‌تواند حجم زیادی نوشتن به همان کلید منجر شود (که کلید شاید شناسه کاربر مشهور یا شناسه عملی باشد که مردم روی آن نظر می‌دهند). هش کردن کلید کمکی نمی‌کند، چون هش دو شناسه یکسان همچنان یکسان است.

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

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

شاید در آینده، سیستم‌های داده بتوانند بارهای کاری منحرف را به‌طور خودکار تشخیص داده و جبران کنند؛ اما فعلاً باید مبادلات را برای برنامه خودتان در نظر بگیرید.

پارتیشن‌بندی و نمایه‌های ثانویه

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

وضعیت پیچیده‌تر می‌شود اگر نمایه‌های ثانویه درگیر باشند (همچنین به «ساختارهای نمایه‌گذاری دیگر» در صفحه ۸۵ مراجعه کنید). نمایه ثانویه معمولاً رکورد را یکتا شناسایی نمی‌کند، بلکه راهی برای جستجوی وقوع یک مقدار خاص است: همه عملیات‌های کاربر ۱۲۳ را پیدا کن، همه مقالاتی که کلمه hogwash دارند را پیدا کن، همه ماشین‌هایی که رنگشان قرمز است را پیدا کن، و غیره.

نمایه‌های ثانویه نان و کره پایگاه‌های داده رابطه‌ای هستند و در پایگاه‌های داده سندی هم رایج‌اند. بسیاری از مخزن‌های کلید-مقدار (مثل HBase و Voldemort) به‌خاطر پیچیدگی پیاده‌سازی اضافی از نمایه‌های ثانویه اجتناب کرده‌اند، اما برخی (مثل Riak) شروع به افزودن آن‌ها کرده‌اند چون برای مدل‌سازی داده بسیار مفیدند. و در نهایت، نمایه‌های ثانویه دلیل وجود سرورهای جستجو مثل Solr و Elasticsearch هستند.

مشکل نمایه‌های ثانویه این است که به‌خوبی به پارتیشن‌ها نگاشت نمی‌شوند. دو رویکرد اصلی برای پارتیشن‌بندی پایگاه داده با نمایه‌های ثانویه وجود دارد: پارتیشن‌بندی مبتنی بر سند و پارتیشن‌بندی مبتنی بر term.

پارتیشن‌بندی نمایه‌های ثانویه بر اساس سند

مثلاً فرض کنید وب‌سایتی برای فروش ماشین‌های دست‌دوم اداره می‌کنید (شکل ۶-۴). هر آگهی شناسه یکتایی دارد — آن را شناسه سند می‌نامیم — و پایگاه داده را بر اساس شناسه سند پارتیشن‌بندی می‌کنید (مثلاً شناسه‌های ۰ تا ۴۹۹ در پارتیشن ۰، شناسه‌های ۵۰۰ تا ۹۹۹ در پارتیشن ۱، و غیره).

می‌خواهید به کاربران اجازه جستجوی ماشین بدهید، با فیلتر بر اساس رنگ و برند، پس به نمایه ثانویه روی رنگ و برند نیاز دارید (در پایگاه داده سندی این‌ها فیلد هستند؛ در پایگاه داده رابطه‌ای ستون). اگر نمایه را اعلام کرده باشید، پایگاه داده می‌تواند نمایه‌گذاری را خودکار انجام دهد.

ii. اگر پایگاه داده شما فقط مدل کلید-مقدار را پشتیبانی می‌کند، ممکن است وسوسه شوید نمایه ثانویه را خودتان با ایجاد نگاشتی از مقادیر به شناسه‌های سند در کد برنامه پیاده‌سازی کنید. اگر این مسیر را می‌روید، باید دقت زیادی کنید نمایه‌ها با داده زیرین سازگار بمانند. شرایط رقابتی و خطاهای متناوب نوشتن (که برخی تغییرات ذخیره شدند اما برخی نه) به‌راحتی می‌توانند باعث ناهمگامی داده شوند — به «نیاز به تراکنش‌های چندشیء» در صفحه ۲۳۱ مراجعه کنید.

شکل ۶-۴. پارتیشن‌بندی نمایه‌های ثانویه بر اساس سند.

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

با این حال، خواندن از نمایه پارتیشن‌بندی‌شده بر اساس سند نیاز به دقت دارد: مگر اینکه کاری خاص با شناسه‌های سند کرده باشید، دلیلی نیست همه ماشین‌های با رنگ یا برند خاص در همان پارتیشن باشند. در شکل ۶-۴، ماشین‌های قرمز در هر دو پارتیشن ۰ و ۱ ظاهر می‌شوند. بنابراین، اگر بخواهید ماشین‌های قرمز را جستجو کنید، باید پرس‌وجو را به همه پارتیشن‌ها بفرستید و همه نتایج برگشتی را ترکیب کنید.

این رویکرد پرس‌وجوی پایگاه داده پارتیشن‌بندی‌شده گاهی scatter/gather نامیده می‌شود و می‌تواند پرس‌وجوهای خواندن روی نمایه‌های ثانویه را بسیار پرهزینه کند. حتی اگر پارتیشن‌ها را به‌صورت موازی پرس‌وجو کنید، scatter/gather مستعد تقویت تأخیر دم (tail latency amplification) است (به «صدک‌ها در عمل» در صفحه ۱۶ مراجعه کنید). با این حال، به‌طور گسترده استفاده می‌شود: MongoDB، Riak [15]، Cassandra [16]، Elasticsearch [17]، SolrCloud [18] و VoltDB [19] همه از نمایه‌های ثانویه پارتیشن‌بندی‌شده بر اساس سند استفاده می‌کنند. اکثر فروشندگان پایگاه داده توصیه می‌کنند طرح پارتیشن‌بندی را طوری ساختار دهید که پرس‌وجوهای نمایه ثانویه از یک پارتیشن سرو شوند، اما این همیشه ممکن نیست، به‌ویژه وقتی چند نمایه ثانویه در یک پرس‌وجو استفاده می‌کنید (مثل فیلتر همزمان ماشین‌ها بر اساس رنگ و برند).

شکل ۶-۵. پارتیشن‌بندی نمایه‌های ثانویه بر اساس term.

پارتیشن‌بندی نمایه‌های ثانویه بر اساس term

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

شکل ۶-۵ نشان می‌دهد این می‌تواند چه شکلی باشد: ماشین‌های قرمز از همه پارتیشن‌ها زیر color:red در نمایه ظاهر می‌شوند، اما نمایه پارتیشن‌بندی شده تا رنگ‌هایی که با حروف a تا r شروع می‌شوند در پارتیشن ۰ و رنگ‌هایی که با s تا z شروع می‌شوند در پارتیشن ۱ باشند. نمایه برند ماشین هم به‌طور مشابه پارتیشن‌بندی شده (با مرز پارتیشن بین f و h).

این نوع نمایه term-partitioned نامیده می‌شود، چون termی که دنبالش می‌گردیم پارتیشن نمایه را تعیین می‌کند. اینجا term مثلاً color:red است. نام term از نمایه‌های تمام‌متن (نوع خاصی از نمایه ثانویه) می‌آید، که termها همه واژه‌هایی هستند که در سند رخ می‌دهند.

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

مزیت نمایه سراسری (term-partitioned) نسبت به نمایه پارتیشن‌بندی‌شده بر اساس سند این است که خواندن را کارآمدتر می‌کند: به‌جای scatter/gather روی همه پارتیشن‌ها، کلاینت فقط به پارتیشنی که term موردنظر را دارد درخواست می‌فرستد. با این حال، معایب نمایه سراسری این است که نوشتن کندتر و پیچیده‌تر است، چون نوشتن یک سند ممکن است چند پارتیشن نمایه را تحت تأثیر قرار دهد (هر term در سند ممکن است روی پارتیشن متفاوتی، روی گره متفاوتی باشد).

در دنیای ایده‌آل، نمایه همیشه به‌روز است و هر سندی که به پایگاه نوشته می‌شود فوراً در نمایه منعکس می‌شود. با این حال، در نمایه term-partitioned، این نیاز به تراکنش توزیع‌شده روی همه پارتیشن‌های تحت تأثیر نوشتن دارد که در همه پایگاه‌های داده پشتیبانی نمی‌شود (فصل ۷ و فصل ۹ را ببینید).

در عمل، به‌روزرسانی‌های نمایه‌های ثانویه سراسری اغلب ناهمزمان است (یعنی اگر بلافاصله پس از نوشتن نمایه را بخوانید، تغییری که تازه دادید ممکن است هنوز در نمایه منعکس نشده باشد). مثلاً Amazon DynamoDB می‌گوید نمایه‌های ثانویه سراسری آن در شرایط عادی در کسری از ثانیه به‌روز می‌شوند، اما ممکن است در صورت خطا در زیرساخت تأخیر انتشار طولانی‌تری داشته باشند [20]. کاربردهای دیگر نمایه‌های سراسری term-partitioned شامل قابلیت جستجوی Riak [21] و انبار داده Oracle است که بین نمایه‌گذاری محلی و سراسری انتخاب می‌دهد [22]. در فصل ۱۲ به پیاده‌سازی نمایه‌های ثانویه term-partitioned برمی‌گردیم.

متعادل‌سازی مجدد پارتیشن‌ها

با گذشت زمان، در پایگاه داده چیزها تغییر می‌کنند:

• توان عملیاتی پرس‌وجو افزایش می‌یابد، پس می‌خواهید CPU بیشتری برای مدیریت بار اضافه کنید.
• اندازه مجموعه‌داده افزایش می‌یابد، پس می‌خواهید دیسک و RAM بیشتری برای ذخیره آن اضافه کنید.
• یک ماشین خراب می‌شود و ماشین‌های دیگر باید مسئولیت‌های ماشین خراب را بر عهده بگیرند.

همه این تغییرات نیاز به جابه‌جایی داده و درخواست‌ها از یک گره به گره دیگر دارند. فرآیند جابه‌جایی بار از یک گره در خوشه به گره دیگر متعادل‌سازی مجدد (rebalancing) نامیده می‌شود.

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

• پس از متعادل‌سازی مجدد، بار (ذخیره داده، درخواست‌های خواندن و نوشتن) باید به‌طور منصفانه بین گره‌های خوشه تقسیم شود.
• در حین متعادل‌سازی مجدد، پایگاه داده باید به پذیرش خواندن و نوشتن ادامه دهد.
• داده بیش از حد لازم نباید بین گره‌ها جابه‌جا شود، تا متعادل‌سازی مجدد سریع باشد و بار شبکه و I/O دیسک به حداقل برسد.

استراتژی‌های متعادل‌سازی مجدد

چند روش مختلف برای اختصاص پارتیشن‌ها به گره‌ها وجود دارد [23]. هر کدام را به‌اختصار بررسی می‌کنیم.

روشی که نباید انجام دهید: hash mod N

وقتی بر اساس هش کلید پارتیشن‌بندی می‌کنیم، گفتیم (شکل ۶-۳) بهتر است هش‌های ممکن را به بازه‌ها تقسیم کنیم و هر بازه را به پارتیشنی اختصاص دهیم (مثلاً کلید را به پارتیشن ۰ اختصاص دهید اگر 0 ≤ hash(key) < b0، به پارتیشن ۱ اگر b0 ≤ hash(key) < b1، و غیره).

شاید پرسیده باشید چرا فقط از mod (عملگر % در بسیاری از زبان‌های برنامه‌نویسی) استفاده نمی‌کنیم. مثلاً hash(key) mod 10 عددی بین ۰ و ۹ برمی‌گرداند (اگر هش را به‌صورت عدد اعشاری بنویسیم، hash mod 10 آخرین رقم است). اگر ۱۰ گره شماره‌گذاری‌شده ۰ تا ۹ داشته باشیم، به نظر راه ساده‌ای برای اختصاص هر کلید به گره می‌رسد.

مشکل رویکرد mod N این است که اگر تعداد گره‌ها N تغییر کند، اکثر کلیدها باید از یک گره به گره دیگر منتقل شوند. مثلاً فرض کنید hash(key) = 123456. اگر ابتدا ۱۰ گره دارید، آن کلید روی گره ۶ شروع می‌شود (چون 123456 mod 10 = 6). وقتی به ۱۱ گره رشد می‌کنید، کلید باید به گره ۳ منتقل شود (123456 mod 11 = 3)، و وقتی به ۱۲ گره رشد می‌کنید، باید به گره ۰ منتقل شود (123456 mod 12 = 0). چنین جابه‌جایی‌های مکرر، متعادل‌سازی مجدد را بیش از حد پرهزینه می‌کند.

به رویکردی نیاز داریم که داده را بیش از حد لازم جابه‌جا نکند.

تعداد ثابت پارتیشن‌ها

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

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

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

شکل ۶-۶. افزودن گره جدید به خوشه پایگاه داده با چند پارتیشن در هر گره.

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

این رویکرد متعادل‌سازی مجدد در Riak [15]، Elasticsearch [24]، Couchbase [10] و Voldemort [25] استفاده می‌شود.

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

انتخاب تعداد درست پارتیشن‌ها دشوار است اگر اندازه کل مجموعه‌داده بسیار متغیر باشد (مثلاً اگر کوچک شروع شود اما با گذشت زمان بسیار بزرگ‌تر شود). چون هر پارتیشن کسری ثابت از کل داده را دارد، اندازه هر پارتیشن متناسب با کل داده در خوشه رشد می‌کند. اگر پارتیشن‌ها خیلی بزرگ باشند، متعادل‌سازی مجدد و بازیابی از خرابی گره پرهزینه می‌شود. اما اگر پارتیشن‌ها خیلی کوچک باشند، سربار زیادی دارند. بهترین عملکرد وقتی حاصل می‌شود که اندازه پارتیشن‌ها «درست» باشد — نه خیلی بزرگ نه خیلی کوچک — که اگر تعداد پارتیشن‌ها ثابت باشد اما اندازه مجموعه‌داده متغیر، دستیابی به آن سخت است.

پارتیشن‌بندی پویا

برای پایگاه‌های داده‌ای که پارتیشن‌بندی بازه کلید استفاده می‌کنند (به «پارتیشن‌بندی بر اساس بازه کلید» در صفحه ۲۰۲ مراجعه کنید)، تعداد ثابت پارتیشن‌ها با مرزهای ثابت بسیار ناراحت‌کننده است: اگر مرزها را اشتباه بگیرید، ممکن است همه داده در یک پارتیشن و بقیه پارتیشن‌ها خالی شوند. پیکربندی دستی مرزهای پارتیشن بسیار خسته‌کننده است.

به همین دلیل، پایگاه‌های داده پارتیشن‌بندی‌شده بر اساس بازه کلید مثل HBase و RethinkDB پارتیشن‌ها را به‌صورت پویا ایجاد می‌کنند. وقتی پارتیشنی از اندازه پیکربندی‌شده بزرگ‌تر می‌شود (در HBase، پیش‌فرض ۱۰ گیگابایت است)، به دو پارتیشن تقسیم می‌شود تا تقریباً نیمی از داده در هر طرف تقسیم بیفتد [26]. برعکس، اگر داده زیادی حذف شود و پارتیشنی زیر آستانه‌ای کوچک شود، می‌تواند با پارتیشن مجاور ادغام شود. این فرآیند شبیه آنچه در سطح بالای درخت B رخ می‌دهد است (به «درخت‌های B» در صفحه ۷۹ مراجعه کنید).

هر پارتیشن به یک گره اختصاص دارد و هر گره می‌تواند چند پارتیشن را مدیریت کند، مثل مورد تعداد ثابت پارتیشن‌ها. پس از تقسیم پارتیشن بزرگ، یکی از دو نیمه‌ها می‌تواند به گره دیگر منتقل شود تا بار متعادل شود. در HBase، انتقال فایل‌های پارتیشن از طریق HDFS، سیستم فایل توزیع‌شده زیرین انجام می‌شود [3].

مزیت پارتیشن‌بندی پویا این است که تعداد پارتیشن‌ها با حجم کل داده سازگار می‌شود. اگر فقط مقدار کمی داده باشد، تعداد کمی پارتیشن کافی است و سربار کم است؛ اگر حجم عظیمی داده باشد، اندازه هر پارتیشن به حداکثر قابل پیکربندی محدود می‌ماند [23].

با این حال، نکته‌ای این است که پایگاه داده خالی با یک پارتیشن شروع می‌شود، چون اطلاع قبلی درباره محل کشیدن مرزهای پارتیشن وجود ندارد. تا وقتی مجموعه‌داده کوچک است — تا جایی که اولین پارتیشن تقسیم شود — همه نوشتن‌ها باید توسط یک گره پردازش شوند در حالی که گره‌های دیگر بیکارند. برای کاهش این مشکل، HBase و MongoDB اجازه می‌دهند مجموعه اولیه‌ای از پارتیشن‌ها روی پایگاه داده خالی پیکربندی شود (pre-splitting نامیده می‌شود). در پارتیشن‌بندی بازه کلید، pre-splitting نیاز دارد از قبل بدانید توزیع کلیدها چگونه خواهد بود [4, 26].

پارتیشن‌بندی پویا فقط برای داده پارتیشن‌بندی‌شده بر اساس بازه کلید مناسب نیست، بلکه به‌خوبی با داده پارتیشن‌بندی‌شده بر اساس هش هم کار می‌کند. MongoDB از نسخه ۲.۴ هم پارتیشن‌بندی بازه کلید و هم هش را پشتیبانی می‌کند و در هر دو مورد پارتیشن‌ها را به‌صورت پویا تقسیم می‌کند.

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

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

گزینه سوم، که Cassandra و Ketama استفاده می‌کنند، تعداد پارتیشن‌ها را متناسب با تعداد گره‌ها می‌کند — به عبارت دیگر، تعداد ثابتی پارتیشن در هر گره [23, 27, 28]. در این مورد، اندازه هر پارتیشن متناسب با اندازه مجموعه‌داده رشد می‌کند در حالی که تعداد گره‌ها ثابت می‌ماند، اما وقتی گره‌ها را افزایش می‌دهید، پارتیشن‌ها دوباره کوچک‌تر می‌شوند. چون حجم داده بزرگ‌تر معمولاً به تعداد گره بیشتری برای ذخیره نیاز دارد، این رویکرد اندازه هر پارتیشن را نسبتاً پایدار نگه می‌دارد.

وقتی گره جدیدی به خوشه می‌پیوندد، به‌صورت تصادفی تعداد ثابتی از پارتیشن‌های موجود را برای تقسیم انتخاب می‌کند و سپس مالکیت نیمی از هر پارتیشن تقسیم‌شده را می‌گیرد در حالی که نیمه دیگر هر پارتیشن سر جایش می‌ماند. تصادفی‌سازی می‌تواند تقسیم‌های ناعادلانه تولید کند، اما با میانگین‌گیری روی پارتیشن‌های بیشتر (در Cassandra، پیش‌فرض ۲۵۶ پارتیشن در هر گره)، گره جدید سهم منصفانه‌ای از بار گره‌های موجود می‌گیرد. Cassandra 3.0 الگوریتم متعادل‌سازی مجدد جایگزینی معرفی کرد که از تقسیم‌های ناعادلانه اجتناب می‌کند [29].

انتخاب تصادفی مرزهای پارتیشن نیاز دارد پارتیشن‌بندی مبتنی بر هش استفاده شود (تا مرزها از بازه اعدادی که تابع هش تولید می‌کند انتخاب شوند). در واقع، این رویکرد بیشترین شباهت را به تعریف اصلی consistent hashing [7] دارد (به «هشینگ سازگار» در صفحه ۲۰۴ مراجعه کنید). توابع هش جدیدتر می‌توانند اثر مشابهی با سربار متادیتای کمتر داشته باشند [8].

عملیات: متعادل‌سازی مجدد خودکار یا دستی

سؤال مهمی درباره متعادل‌سازی مجدد وجود دارد که نادیده گرفتیم: آیا متعادل‌سازی مجدد به‌صورت خودکار یا دستی انجام می‌شود؟

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

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

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

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

مسیریابی درخواست

حالا مجموعه‌داده را روی چند گره روی چند ماشین پارتیشن‌بندی کرده‌ایم. اما سؤال باز مانده: وقتی کلاینت می‌خواهد درخواست بدهد، چگونه می‌داند به کدام گره وصل شود؟ با متعادل‌سازی مجدد پارتیشن‌ها، اختصاص پارتیشن‌ها به گره‌ها تغییر می‌کند. کسی باید این تغییرات را پیگیری کند تا به این سؤال پاسخ دهد: اگر بخواهم کلید «foo» را بخوانم یا بنویسم، به کدام آدرس IP و شماره پورت باید وصل شوم؟

این نمونه‌ای از مسئله عمومی‌تری به نام service discovery است که محدود به پایگاه‌های داده نیست. هر نرم‌افزاری که از طریق شبکه در دسترس است این مسئله را دارد، به‌ویژه اگر هدف دسترس‌پذیری بالا باشد (اجرای پیکربندی افزونگی روی چند ماشین). بسیاری از شرکت‌ها ابزارهای service discovery داخلی خود را نوشته‌اند و بسیاری از آن‌ها متن‌باز شده‌اند [30].

در سطح بالا، چند رویکرد مختلف برای این مسئله وجود دارد (شکل ۶-۷):

1. اجازه دهید کلاینت‌ها به هر گره‌ای تماس بگیرند (مثلاً از طریق load balancer round-robin). اگر آن گره تصادفاً مالک پارتیشنی باشد که درخواست به آن مربوط است، می‌تواند مستقیماً درخواست را مدیریت کند؛ در غیر این صورت، درخواست را به گره مناسب فوروارد می‌کند، پاسخ را دریافت می‌کند و به کلاینت می‌دهد.
2. همه درخواست‌های کلاینت‌ها را ابتدا به لایه مسیریابی بفرستید که گره مسئول هر درخواست را تعیین و درخواست را فوروارد می‌کند. این لایه مسیریابی خودش هیچ درخواستی را مدیریت نمی‌کند؛ فقط به‌عنوان load balancer آگاه از پارتیشن عمل می‌کند.
3. الزام کنید کلاینت‌ها از پارتیشن‌بندی و اختصاص پارتیشن‌ها به گره‌ها آگاه باشند. در این مورد، کلاینت می‌تواند مستقیماً به گره مناسب وصل شود، بدون واسطه.

در همه موارد، مسئله کلیدی این است: اجزای تصمیم‌گیرنده مسیریابی (که ممکن است یکی از گره‌ها، یا لایه مسیریابی، یا کلاینت باشد) چگونه از تغییرات در اختصاص پارتیشن‌ها به گره‌ها مطلع می‌شوند؟

شکل ۶-۷. سه روش مختلف برای مسیریابی درخواست به گره درست.

این مسئله چالش‌برانگیز است، چون مهم است همه شرکت‌کنندگان توافق داشته باشند — وگرنه درخواست‌ها به گره‌های اشتباه فرستاده می‌شوند و درست مدیریت نمی‌شوند. پروتکل‌هایی برای دستیابی به اجماع در سیستم توزیع‌شده وجود دارد، اما پیاده‌سازی درست آن‌ها سخت است (فصل ۹ را ببینید).

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

شکل ۶-۸. استفاده از ZooKeeper برای پیگیری اختصاص پارتیشن‌ها به گره‌ها.

مثلاً Espresso لینکدین از Helix [31] برای مدیریت خوشه استفاده می‌کند (که به نوبه خود به ZooKeeper تکیه دارد) و لایه مسیریابی مطابق شکل ۶-۸ پیاده‌سازی می‌کند. HBase، SolrCloud و Kafka هم از ZooKeeper برای پیگیری اختصاص پارتیشن استفاده می‌کنند. MongoDB معماری مشابهی دارد، اما به پیاده‌سازی config server خودش و daemonهای mongos به‌عنوان لایه مسیریابی تکیه می‌کند.

Cassandra و Riak رویکرد متفاوتی دارند: از پروتکل gossip بین گره‌ها برای پخش هر تغییری در وضعیت خوشه استفاده می‌کنند. درخواست‌ها می‌توانند به هر گره‌ای فرستاده شوند و آن گره به گره مناسب برای پارتیشن درخواست‌شده فوروارد می‌کند (رویکرد ۱ در شکل ۶-۷). این مدل پیچیدگی بیشتری روی گره‌های پایگاه داده می‌گذارد اما از وابستگی به سرویس هماهنگی خارجی مثل ZooKeeper اجتناب می‌کند.

Couchbase به‌صورت خودکار متعادل‌سازی مجدد نمی‌کند که طراحی را ساده می‌کند. معمولاً با لایه مسیریابی به نام moxi پیکربندی می‌شود که تغییرات مسیریابی را از گره‌های خوشه یاد می‌گیرد [32].

وقتی از لایه مسیریابی استفاده می‌کنید یا درخواست‌ها را به گره تصادفی می‌فرستید، کلاینت‌ها همچنان باید آدرس‌های IP برای اتصال را پیدا کنند. این‌ها به‌اندازه اختصاص پارتیشن‌ها به گره‌ها سریع تغییر نمی‌کنند، پس اغلب استفاده از DNS برای این منظور کافی است.

اجرای موازی پرس‌وجو

تا اینجا روی پرس‌وجوهای بسیار ساده تمرکز کردیم که یک کلید را می‌خوانند یا می‌نویسند (به‌علاوه پرس‌وجوهای scatter/gather در مورد نمایه‌های ثانویه پارتیشن‌بندی‌شده بر اساس سند). این تقریباً سطح دسترسیی است که اکثر مخزن‌های داده توزیع‌شده NoSQL پشتیبانی می‌کنند.

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

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

اجرای سریع موازی پرس‌وجوهای انبار داده موضوع تخصصی است و با توجه به اهمیت تجاری تحلیل، علاقه تجاری زیادی دارد. برخی تکنیک‌های اجرای موازی پرس‌وجو را در فصل ۱۰ بحث می‌کنیم. برای نمای کلی دقیق‌تر از تکنیک‌های پایگاه‌های داده موازی، به منابع مراجعه کنید [1, 33].

جمع‌بندی

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

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

دو رویکرد اصلی پارتیشن‌بندی را بحث کردیم:

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

رویکردهای ترکیبی هم ممکن است، مثلاً با کلید مرکب: استفاده از بخشی از کلید برای شناسایی پارتیشن و بخش دیگر برای ترتیب مرتب‌سازی.

همچنین تعامل بین پارتیشن‌بندی و نمایه‌های ثانویه را بحث کردیم. نمایه ثانویه هم باید پارتیشن‌بندی شود و دو روش وجود دارد:

• نمایه‌های پارتیشن‌بندی‌شده بر اساس سند (نمایه‌های محلی)، که نمایه‌های ثانویه در همان پارتیشن کلید اصلی و مقدار ذخیره می‌شوند. این یعنی فقط یک پارتیشن هنگام نوشتن نیاز به به‌روزرسانی دارد، اما خواندن نمایه ثانویه نیاز به scatter/gather روی همه پارتیشن‌ها دارد.
• نمایه‌های پارتیشن‌بندی‌شده بر اساس term (نمایه‌های سراسری)، که نمایه‌های ثانویه جداگانه پارتیشن‌بندی می‌شوند با استفاده از مقادیر نمایه‌شده. ورودی در نمایه ثانویه ممکن است شامل رکوردهایی از همه پارتیشن‌های کلید اصلی باشد. هنگام نوشتن سند، چند پارتیشن نمایه ثانویه باید به‌روز شوند؛ با این حال، خواندن می‌تواند از یک پارتیشن سرو شود.

در پایان، تکنیک‌های مسیریابی پرس‌وجوها به پارتیشن مناسب را بررسی کردیم که از load balancing ساده آگاه از پارتیشن تا موتورهای پیچیده اجرای موازی پرس‌وجو را در بر می‌گیرد.

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

منابع

[1] David J. DeWitt and Jim N. Gray: "Parallel Database Systems: The Future of High Performance Database Systems," Communications of the ACM, volume 35, number 6, pages 85–98, June 1992. doi:10.1145/129888.129894

[2] Lars George: "HBase vs. BigTable Comparison," larsgeorge.com, November 2009.

[3] "The Apache HBase Reference Guide," Apache Software Foundation, hbase.apache.org, 2014.

[4] MongoDB, Inc.: "New Hash-Based Sharding Feature in MongoDB 2.4," blog.mongodb.org, April 10, 2013.

[5] Ikai Lan: "App Engine Datastore Tip: Monotonically Increasing Values Are Bad," ikaisays.com, January 25, 2011.

[6] Martin Kleppmann: "Java's hashCode Is Not Safe for Distributed Systems," martin.kleppmann.com, June 18, 2012.

[7] David Karger, Eric Lehman, Tom Leighton, et al.: "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web," at 29th Annual ACM Symposium on Theory of Computing (STOC), pages 654–663, 1997. doi:10.1145/258533.258660

[8] John Lamping and Eric Veach: "A Fast, Minimal Memory, Consistent Hash Algorithm," arxiv.org, June 2014.

[9] Eric Redmond: "A Little Riak Book," Version 1.4.0, Basho Technologies, September 2013.

[10] "Couchbase 2.5 Administrator Guide," Couchbase, Inc., 2014.

[11] Avinash Lakshman and Prashant Malik: "Cassandra – A Decentralized Structured Storage System," at 3rd ACM SIGOPS International Workshop on Large Scale Distributed Systems and Middleware (LADIS), October 2009.

[12] Jonathan Ellis: "Facebook's Cassandra Paper, Annotated and Compared to Apache Cassandra 2.0," datastax.com, September 12, 2013.

[13] "Introduction to Cassandra Query Language," DataStax, Inc., 2014.

[14] Samuel Axon: "3% of Twitter's Servers Dedicated to Justin Bieber," mashable.com, September 7, 2010.

[15] "Riak 1.4.8 Docs," Basho Technologies, Inc., 2014.

[16] Richard Low: "The Sweet Spot for Cassandra Secondary Indexing," wentnet.com, October 21, 2013.

[17] Zachary Tong: "Customizing Your Document Routing," elasticsearch.org, June 3, 2013.

[18] "Apache Solr Reference Guide," Apache Software Foundation, 2014.

[19] Andrew Pavlo: "H-Store Frequently Asked Questions," hstore.cs.brown.edu, October 2013.

[20] "Amazon DynamoDB Developer Guide," Amazon Web Services, Inc., 2014.

[21] Rusty Klophaus: "Difference Between 2I and Search," email to riak-users mailing list, lists.basho.com, October 25, 2011.

[22] Donald K. Burleson: "Object Partitioning in Oracle," dba-oracle.com, November 8, 2000.

[23] Eric Evans: "Rethinking Topology in Cassandra," at ApacheCon Europe, November 2012.

[24] Rafał Kuć: "Reroute API Explained," elasticsearchserverbook.com, September 30, 2013.

[25] "Project Voldemort Documentation," project-voldemort.com.

[26] Enis Soztutar: "Apache HBase Region Splitting and Merging," hortonworks.com, February 1, 2013.

[27] Brandon Williams: "Virtual Nodes in Cassandra 1.2," datastax.com, December 4, 2012.

[28] Richard Jones: "libketama: Consistent Hashing Library for Memcached Clients," metabrew.com, April 10, 2007.

[29] Branimir Lambov: "New Token Allocation Algorithm in Cassandra 3.0," datastax.com, January 28, 2016.

[30] Jason Wilder: "Open-Source Service Discovery," jasonwilder.com, February 2014.

[31] Kishore Gopalakrishna, Shi Lu, Zhen Zhang, et al.: "Untangling Cluster Management with Helix," at ACM Symposium on Cloud Computing (SoCC), October 2012. doi:10.1145/2391229.2391248

[32] "Moxi 1.8 Manual," Couchbase, Inc., 2014.

[33] Shivnath Babu and Herodotos Herodotou: "Massively Parallel Databases and MapReduce Systems," Foundations and Trends in Databases, volume 5, number 1, pages 1–104, November 2013. doi:10.1561/1900000036