تقسیم‌بندی و تکثیر داده‌ها

تقسیم‌بندی داده‌ها (Data partitioning) یک پایگاه داده را برای مقیاس‌پذیری در چندین گره توزیع می‌کند، در حالی که تکثیر (replication) برای دسترسی‌پذیری و بهبود عملکرد خواندن، کپی‌هایی از داده‌ها را در چندین گره نگه می‌دارد؛ این دو با هم تعیین می‌کنند که یک پایگاه داده توزیع‌شده چگونه مقیاس‌پذیر می‌شود و در برابر خطاها مقاومت می‌کند.

Definition

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

Scope

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

Core questions

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

Key concepts

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

Key theories

تقسیم‌بندی افقی و عمودی

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

هش‌سازی سازگار

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

مدل‌های تکثیر و مبادلات

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

Clinical relevance

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

History

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

Key figures

• M. Tamer Özsu
• Patrick Valduriez
• David Karger

Seminal works

• ozsu2011
• karger1997

Frequently asked questions

تفاوت بین تقسیم‌بندی و تکثیر چیست؟

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

چرا به جای تقسیم‌بندی هش ساده از هش‌سازی سازگار استفاده می‌شود؟

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