بخشی از مقاله
الگوریتم زمانبند چندگانه برای کنترل همزمانی سیستمهای پایگاه داده موازی
چکیده :
تلاشها و تحقیقات توسعه یافته در طول دهه اخیر از سیستم پایگاه داده موازی یک واقعیت ساخته است. الگوریتم کنترل همزمانی رایج در سیستم پایگاه داده موازی از روش تک زمانبند استفاده می کند. روش تک زمانبند دارای ضعفهایی از قبیل جدولهای قفل بسیار بزرگ، سربار زیاد برای زمانبندهای متمرکز و تعداد زیاد پیامها می باشد. در این مقاله امکان چند زمانبند را بررسی نموده و به این نتیجه رسیدیم که الگوریتم تک زمانبند در شکل کنونی نمی تواند به محیط چند زمانبند انتقال داده شود. لذا یک روش چند زمانبند برای کنترل همزمانی سیستم های پایگاه داده موازی که امکان زمانبندی را برای عناصر پردازشی مرتبط به هم توزیع می کند، پیشنهاد کرده ایم. در ادامه الگوریتم پیاده سازی روش یاد شده را ارائه و صحت آن را اثبات نموده ایم.
کلید واژه ها : پایگاه داده موازی، کنترل همزمانی، زمانبند چندگانه، پی در پی پذیری
1 ) مقدمه
افزایش میزان داده های ذخیره شده و نیازمندی به زمان پاسخگویی سریع انگیزه تحقیق در سیستم پایگاه داده موازی را ایجاد کرده است. سیستمهای پایگاه داده موازی به ویژه در نیازمندیهای بانکهای اطلاعاتی خیلی بزرگ مورد استفاده قرار می گیرند. اما جالب اینکه در زمینه پردازش موازی تراکنشها و کنترل همزمانی برای رسیدن به نیازهای خاص سیستم پایگاه داده موازی کار خیلی کمی انجام شده است. روش تک زمانبند و پی در پی پذیر [3] به عنوان یک معیار صحت برای کنترل همزمانی مورد استفاده قرار می گیرد. سطح کارایی بالا و سیستمهای پایگاه داده چند پردازشی مثل سیستمهای پایگاه داده موازی (PDS) [1.2] و سیستمهای پایگاه داده توزیع یافته (DDS) [10] و سیستمهای پایگاه داده بلادرنگ (RTDS) [8.9] نظریه پی در پی پذیری برخورد (confilict serializability) [3] را به عنوان یک معیار صحت ناکافی ساخته است.
این مقاله یک معیار پی در پی پذیری جدید با عنوان شبه پی در پی پذیری پایگاه داده موازی (Parall Database Quasi-serializability) پیشنهاد کرده و یک الگوریتم کنترل چند زمانبد را برای پاسخ دادن به نیازمندیهای PDS ایجاد نموده است. تمرکز ما بر روی مشکل اجرای همزمان تراکنشها در PDS می باشد. پی در پی پذیری به عنوان یک معیار صحت، وجود یک تک زمانبند را برای تضمین تداوم پایگاه داده درنظر می گیرد.
اما برآورده شدن نیازمندیهای PDS به وسیله تک زمانبند ممکن نیست. بنابراین استراتژی تک زمانبند امکان انتقال مستقیم به محیط چند زمانبند را ندارد. این مشکل با جزئیات بیشتر در بخش بعدی مورد بحث قرار گرفته است.
طرح تک زمانبند ضعفهایی ذاتی دارد که نمونه هایی از آن به شرح ذیل است :
1 ) به علت زمانبندی متمرکز قفل جدول در زمانبند خیلی بزرگ می شود.
2 ) قدرت محاسبه پردازشگرهای چندگانه به طور کامل مورد استفاده قرار نمی گیرد.
3 ) همه سایتها باید با یک زمانبند مرکزی ارتباط داشته باشند و این امر تعداد پیامهای سیستم را افزایش می دهد.
4 ) بعضی وقتها تصمیم درباره سایت هماهنگ کننده (Coordinator Nod) مشکل است.
الگوریتم چند زمانبند پیشنهادی برای کنترل همزمانی، ضعفهای ذکر شده را به دلایل واضح کاهش می دهد. هدف این تحقیق توضیح موضوعاتی در کنترل همزمانی سیستمهای پایگاه داده موازی می باشد که از زمانبندهای چندگانه استفاده می کنند. این مقاله دو جنبه مهم را شامل می شود :
1 ) ما نشان می دهیم که الگوریتمهای کنترل همزمانی اجرا شده در محیط تک زمانبند ممکن است نتایج نادرستی را در محیط چند زمانبد به وجود آورد. برخلاف محیط تک زمانبند، ما برای توزیع بار از زمانبندهای چندگانه استفاده می کنیم.
2 ) در ادامه، یک الگوریتم کنترل همزمانی چند زمانبند را پیشنهاد می دهیم که مسئولیت های زمانبندی را به عناصر پردازشی مربوطه توزیع می کند و یک زمانبند شبه پی در پی پذیر برای پایگاه داده موازی تضمین می نماید. البته باید تاکید کنیم این مفهوم با اینکه به پایگاه داده چندگانه پی در پی پذیر (MDBS) شبیه است ولی در عین حال با آنها تفاوتهایی دارد. HDDBS , MDBS دو سطح تراکنش محلی و عمومی را درنظر می گیرند و با آنها به طور متفاوت رفتار می کنند اما الگوریتم پیشنهادی با همه تراکنشها به طور یکسان رفتار می کند. برای مقایسه و توصیف جزئی تر مراجعه کنید. [10 ، 9 ، 8 ، 2]
بقیه این مقاله بدین صورت سازمان یافته است : بخش دوم تعریف های اساسی درباره مفاهیم پایگاه داده و PDS ارائه می دهد. بخش سوم درباره انگیزه این کار بحث می کند. بخش چهارم مدل رسمی PDS که ما آن را برای الگوریتم خود درنظر گرفته ایم ارائه می نماید. بخش پنجم الگوریتم پیشنهادی را شرح می دهد و نهایتاً بخش ششم از مقاله نتیجه گیری می کند و درباره گسترش بیشتر کار بحث می کند.
2 ) زمینه بحث
در این بخش ابتدا یک تعریف پایه ای در مورد پایگاه داده که در طول مقاله استفاده کرده ایم، ارائه میدهیم. سپس به طور خلاصه درباره طراحی خیلی معمول PDS بحث می کنیم.
2 . 1 ) تعاریف پایه ای
قبل از ارائه الگوریتم پیشنهادی، به طور خلاصه تراکنش (Transaction) و خصوصیات تراکنش تراکنش را تعریف می کنیم. از نقطه نظر کاربر، تراکنش به طور معمول عبارت از اجرای عملیاتی است که به اطلاعات اشتراکی در پایگاه داده دست می یابد.
تعریف 1 ) یک تراکنش Ti مجموعه ای از commit (ci) , abort (ai) , write (wi) , read (ri) است. Ti یک ترتیب جزئی با رابطه ترتیبی می باشد، به طوریکه :
1 )
2 )
3 ) اگر t عبارت از ai یا ci باشد برای هر عملیات دیگر p داریم :
4 ) آنگاه : یا
تعریف 2 ) یک تاریخچه کامل (یا زمانبندی ) H روی T ( T را مجموعه ای از تراکنشها درنظر می گیریم T = { T1, T2 , … Tn } ) عبارت از یک ترکیب جزئی با رابطه ترتیبی می باشد، به طوریکه [3] :
1 )
2 )
3 ) برای هر زوج عملیات برخودار داریم : یا
تعریف 3 ) زمانبندی H پی در پی پذیر (SR) است اگر تراکنشهای خاتمه یافته آن C(H) معادل با یک زمانبندی سریال Hs باشد [3] .
تعریف 4 ) زمانبندی پایگاه داده Hs سریال است اگر و فقط اگر [3] :
زمانبندی H پی در پی پذیر است اگر و فقط اگر گراف پی در پی پذیری آن غیرحلقوی باشد [11 ، 3 ، 1 ] .
2 . 2 ) سیستمهای پایگاه داده موازی
حجم گسترده و پیچیدگی اطلاعاتی که باید به وسیله سیستمها پردازش شود، نیاز به افزایش عملکرد سیستمهای پایگاه داده را ضروری می سازد. علت های بروز مشکلات مرتبط با حجم زیاد اطلاعات عبارتند از :
1 ) پردازش تربیتی اطلاعات
2 ) ترافیک ورودی و خروجی اجتناب ناپذیر.
سیستمهای پایگاه داده موازی به منظور جلوگیری از این بن بستها به وجود آمده اند. در محیط چند پردازشی به منظور پاسخگویی به نیازهای خاص، استراتژیهای مختلفی برای مدیریت حافظه و داده مورد استفاده قرار می گیرد [11] . در معماری حافظه اشتراکی (Shared Memory) پردازشگرها به دیسکها و یک حافظه عمومی دسترسی مستقیم دارند. این طراحی برای ایجاد تعادل مناسب است. در معماری دیسک اشتراکی (Shared Disk) پردازنده ها به همه دیسکها دسترسی مستقیم دارند اما حافظه هر یک اختصاصی می باشد. معماری غیراشتراکی (Shared Nothing) برای هر پردازنده، حافظه و دیسک اختصاصی دارد که هر کدام یک گره یا عنصر پردازشی (Processing Element) نامیده می شوند. برای بحث جزئی تر مقایسه ببینید [8 ، 5 ، 2 ، 1]. ما در این مقاله معماری غیراشتراکی را درنظر گرفته ایم.
2 . 3 ) مثال انگیزشی
مثال زیر نشان می دهد که انتقال مستقیم الگوریتمهای تک زمانه برای برآوردن نیازمندیهای محیط چند زمانه امکان پذیر نیست. ما برای اینکه انگیزه کارمان را به وضوح نشان دهیم. دو عنصر پردازشی (PE) و چهار شیء داده ای (O1 , O2 , O3 , O4) درنظر گرفته ایم. دو عنصر پردازشی P1 , P2 نامیده می شوند و داده ها به صورت زیر قرار می گیرند :
P1 = O1 , O2 P2 = O3 , O4
اکنون دو تراکنش از پایگاه داده را به صورت زیر درنظر می گیریم :
T1 = r1 (O1) r1(o2) w1(O3)w1(O1)C1
T2 = r2 (O1) r2(O3) w2(O4)w2(O1)C2
هر تراکنش طبق محل شیء داده به 2 تراکنش فرعی (زیرتراکنش) تقسیم شده و از T2 , T1 زیرتراکنش های زیر به دست آمده است :
T11 = r11 (O1) r11(O2) w11(O1)C11
T12 = w12 (O3)C12
T12 = r21 (O1) w21(O1)C21
T12 = r22 (O3) w22(O4)C22
T11 به عنوان زیرتراکنشی از تراکنش 1 در T12 , PE1 زیرتراکنشی از تراکنش 1 در PE2 خوانده شده است. فرض کنیم زمانبندیهای زیر به وسیله زمانبند محلی در عناصر پردازشگر تهیه شده باشد :
H2 = r11 (O1) r11(O2) w11(O1)C11r21(O1)w21(O1)C21
H2 = r22 (O3) w22(O4)C22w12(O3)C12
H2 , H1 دو زمانبندی به ترتیب در PE2 , PE1 می باشند. هر دو زمانبند محلی زمانبندی SR را با ترتیب سریال زیر تولید می کنند :
تراکنش 2 تراکنش 1 : زمانبند 1
تراکنش 1 تراکنش 2 : زمانبند 2
به طوریکه ملاحظه می شود دو ترتیب سریال فوق متناقض هستند. اگرچه هر یک از زمانبندها، زمانبندی سریال تولید می کنند اما اثر ترکیبی یک چرخه تولید می نماید. . بنابراین مسئولیت زمانبند در هر عنصر پردازشگر (PE) خیلی زیادتر از انچه که در محیط تک زمانه وجود دارد، می باشد.
لذا نتیجه می گیریم، استراتژیهای کنترل همزمانی که در تک زمانه ها قابل ارجا است، ممکن نیست در شکل کنونی به محیط چند زمانه انتقال یابد.
ضعفهای الگوریتمهای تک زمانبند ما را برانگیخت که مسئولیتهای زمانبندی را به PE مرتبط توزیع نمائیم و زمانبند چندگانه را درنظر بگیریم. لذا یک معیار جدید شبه پی در پی پذیری (Quasi - serializability) برای پاسخ به نیازمندیهای کنترل همزمانی چند زمانبند پیشنهاد می کنیم.
2 . 4 ) مدلی از سیستم پایگاه داده موازی
در این مقاله سیستم پایگاه داده موازی غیراشتراکی درنظر گرفته شده است. برای سادگی کار فقط دو عنصر پردازشگر دنظر گرفته ایم که الگوریتم ما را توضیح دهد.
فرض می کنیم که زمانبندهای محلی برای تولید زمانبندی پی در پی پیذر (SR) توانا هستند. بخشهای مختلف این مدل به شکل زیر توصیف شده است.
الف ) تقسیم کننده (Splitter) : شامل اطلاعاتی درباره داده های تخصیص داده شده به عناصر پردازشی است . تراکنش را با توجه به محل داده ها به زیر تراکنشهای چندگانه تقسیم می کند. در این مقاله Splitter مسئولیت زمانبند مرکزی را دارد (مطابق شکل 2).
ب ) عناصر پردازشی (PE) : شامل یک پردازنده، یک حافظه و بخشی از یک پایگاه داده که در طراحی غیراشتراکی مورد بحث قرار گرفت. (بخش 2)
ج ) زمانبندها در هر PE : زمانبندها مسئول ایجاد یک زمانبندی پی در پی پذیر هستند. به طوریکه در قسمتهای پیشین بحث شد، مسئولیت هر زمانبند خیلی بیشتر از محیط تک زمانه می باشد.
د ) تراکنشها : تراکنشها همانند محیط تک پردازنده خصوصیات تعریف 1 را دارند.
2 . 5 ) الگوریتم و استدلال SR پیشنهادی
در این بخش درباره معیار صحت برای الگوریتم کنترل همزمانی زمانبند چندگانه که شبه پی در پی پذیری در پایگاه داده موازی (PDQ-SR) نامیده می شود، بحث می کنیم و آن را توضیح می دهیم.
2 . 5 . 1 ) شبه پی در پی پذیری در پایگاه داده موازی (PDQ-SR)
مسئولیت زمانبندی در PDS بر طبق داده های تقسیم شده به PE مرتبط توزیع شده است. مثال انگیزشی نشان داد که اگرچه زمانبندهای مجزا تاریخچه های سریال را در پایگاه داده تولید می کنند اما در یک حالت سازگار نیستند. لذا باید معیارهای جدیدی برای کنترل همزمانی توسط چند زمانبند تعریف شود. ما یک معیار SR جدید پیشنهاد می کنیم که دو نوع تراکنش را جدا می کند؛ تراکنشهایی که فقط یک زیرتراکنش دارند و تراکنشهایی که بیش از یک زیرتراکنش دارند. تعریف زیر معیار صحت برای PDS را بیان می کند.
تعریف 5 ) تاریخچه سریال زمانبند چندگانه (MS-Serial) در سیستم پایگاه داده موازی درنظر گرفته شده است. یک تاریخچه MS-Serial است، اگر و فقط اگر :
1 ) هر PE تاریخچه پی در پی پذیر تولید کند و
2 ) هر تراکنش که بیش از یک زیرتراکنش داشته باشد، یعنی به بیش از یک PE دسترسی داشته باشد، بر طبق ترتیب کلی اجرا می شود. به عنوان نمونه ترتیب کلی برای دو تراکنش Tj , Ti می تواند بدین صورت توصیف شود : اگر Ti در هر PE ، مقدم بر Tj را باشد انگاه در همه PE هایی که هر دوی آنها حضور دارند، همه عملیات Ti از عملیاتهای Tj پیشی می گیرند.
شرط بعدی مانند «شبه پی در پی پذیری» می باشد. بنابراین معیار صحت را با عنوان «شبه پی در پی پذیری پایگاه داده موازی » (Parallel Database Quasi-Seriazliability) نامگذاری می کنیم.
تعریف 6 ) یک تاریخچه در محیط زمانبند چندگانه –PDQ پی در پی پذیر (PDQ-serializable) است اگر و فقط اگر معائل یک تاریخچه MS- سریال باشد. (تعریف هم ارزی از [3] صفحه 30).
2 . 5 . 2 ) قضیه PDQ-SERIALIZABILTY پیشنهادی
پی در پی پذیری PDQ در یک تاریخچه به وسیله گراف های شبه پی در پی پایگاه داده موازی (PDQ-serializability) تعیین می شود. تعریف زیر گراف(PDQ-serializability) را توصیف می کند.
تعریف 7 ) با استفاده از یک گراف که با سه ترتیب (T1,Tn,A) تعریف می شود، زمانبندیهایی از همه زمانبندها در هر PE برای نمونه داده شده، می تواند ارائه شود. این گراف به عنوان گراف پی در پی پذیری چندگانه (MSG) منتسب می شود.
Ti : مجموعه ای از راس های نشان دارد است که بیانگر تراکنشهایی با بیش از یک زیر ترکنش می باشد.
Tn : مجموعه ای از راس های نشان دار است که بیانگر تراکنشهایی با بیش از یک زیر تراکنش می باشد.
A : مجموعه ای از کمانهایی که بیانگر ترتیب تراکنش در هر PE می باشد.
در ادامه این مقاله ما فقط تراکنش هایی را که بیش از یک زیر تراکنش دارند، در نظر خواهیم گرفت و آنرا با T نشان می دهیم. تراکنش های با یک زیر تراکنش بوسیله PE مجزا در نظر گرفته می شوند و هیچ خطری برای مسئله مورد نظربه وجود نمی آورند. بر اساس تعریف MSG قضیۀ زیر را تدوین می کنیم.
قضیۀ 1 ) یک تاریخچه در محیط زمانبند چندگانه PDQ پی در پی پذیر ( PDQ – serializable) است اگر و فقط اگر MSG غیر حلقوی باشد.
اثبات : ( اگر ) فرض کنیم ( H )C از مجموعه ( T1,T2,…,Tn) تشکیل شده باشد. Tn,…,T2,T1 تراکنشهایی با بیش از یک زیر ترکنش هستند. فرض می کنیم که همۀ عناصر پردازشی همیشه تراکنشهای زمانبندی شده با ترتیب پی در پی باشند. n راس از MSG ( T1,T2,…,Tn) غیر حلقوی هستند و بنابراین ممکن است از لحاظ توپولوژی مرتب شده باشند. ( تعریف توپولوژی مرتب شده از [3]). فرض کنید Ti1,Ti2,…,Tin یک توپولوژی مرتب از تاریخچه زمانبندی چندگانه برای جایگشتی از 1,2,…,n باشد. فرض کنید تاریخچه Ti1,Ti2,…,Tin زمانبندی MS – serial باشد. نشان می دهیم که : C(H) = MS – serial . فرض کنید Ti P وT q و p.q برخودار باشند بطوریکهq H>p .
این بدان معنی است که در MSG یک کمان ازTi به Tj وجود دارد. بنابراین در هر توپولوژی مرتب از تاریخچۀ زمانبند چند گانه، Ti قبل از Tj قرار می گیرد. لذا در همۀ ترتیبهای توپولوژی همۀ عملیات Ti قبل از همۀ عملیات Tj قرار می گیرد. بنابراین C(H) = MS – serial و از تعریف 6 تاریخچۀ H زمانبندی PDQ – serializable است.
( فقط اگر ): فرض کنیم تاریخچه H زمانبندی PDQ – serializable باشد. و Hs را یک تاریخچۀ MS – serial هم ارز با H قرار دهید. در نظر بگیرید که در MSG یک کمان از Ti به Tj وجود دارد. این نشان می دهد که آنجا دو عملگر برخوردار Ti P وT q وجود دارد بطوریکه در برخی از PEi ها H q p . این شرایط در هر دو دستور برخورد دار در همان PEi صحیح است. از آنجائیکه H Hs در آن PEi خاص تمام عملیاتهای Ti قبل از Tj اتفاق می افتد. فرض کنیم که یک چرخه MSG وجود دارد. این نشان می دهد که در زمانبندی MS – serial در هر PEiدیگر Ti Tj. اما می دانیم که Ti در PEi قبل از Tj قرار می گیرد و این با فرض قبلی مخالف است.
2 . 5 . 3 ) تایم استمپ بیس (TIMESTAMP BASED) الگوریتم کنترل همزمانی زمانبند چندگانه
در این بخش ما یک تایم استمپ بیش برای الگوریتم کنترل همزمانی زمانبند چندگانه (TMCC) فرض می کنیم که برای تضمین پی در پی PDQ ترکیب کلی را در زمانبند وارد می کند. ترتیب کلی فقط به آن تراکنشهای برخودار نیاز دارد که به بیش از یک PE دسترسی دارند و آن PE به وسیله سایر تراکنش های فعال مورد دسترسی قرار گرفته است.
