دستیابی به اطلاعات در پایگاه داده SQL
روشهاي دستيابي(Access Methods)
تعداد زيادي ساختار شاخص، مختص پايگاه داده هاي مقيم در حافظه اصلي ، طراحي و ارزيابي شده اند که از آن جمله، مي توان به انواع گوناگون hashing و درختها اشاره نمود.hashing در جستجو و بهنگام سازيِ سريع مفيد است ، ولي به اندازه ساختارهاي درختي در فضا، صرفه جويي نکرده و همچنين، از پرس و جو هاي بازه اي (range query) نيز، پشتيباني نمي کند.
يک نکته کلي در کليه روشهاي دستيابي در حافظه اصلي، اين مي باشد که نيازي به ذخيره سازي مقادير داده – که شاخصها بر روي آن ها ساخته مي شوند- در خود شاخص نمي باشد.توجه کنيد که دسترسي تصادفي در حافظه اصلي سريع بوده و اشاره گرها به آساني دنبال مي شوند، به همين دليل،ساختارهاي شاخص مي توانند به جاي مقادير داده ايي، اشاره گرهايي را به آنها ذخيره کنند،بدين ترتيب مشکل ذخيره سازي فيلدهايي با طول متغير در شاخص، حل شده و چون اشاره گرها کوچکتر از داده هايي هستند که به آنها اشاره مي کنند ، در ميزان حافظه مصرفي نيز به مقدار قابل توجهي، صرفه جويي مي شود.
نمايش داده ها (Data Representation )
از روش فوق ، همچنين مي توان به نحو مطلوبي در نمايش داده ها استفاده کرد، بدين ترتيب که : tupleهاي رابطه مي توانند به عنوان يک مجموعه از اشاره گر ها به مقادير ِ داده ايي، ارائه شوند.استفاده از اشاره گر،هنگامي که مقادير بزرگ چندين بار در پايگاه داده تکرار مي شوند، به صرفه مي باشد چرا که مقدار واقعي داده، تنها يکبار ذخيره خواهد شد.همچنين، اشاره گرها، مشکل فيلدهايي با طول متغير را با استفاده از اشاره گرهايي به يک Heap ، راحت تر کنترل خواهند کرد.
پردازش پرس و جو (Query Processing)
از آنجا كه دسترسي ترتيبي (sequential access ) در پايگاه داده مقيم در حافظه اصلي (MMDB) ،چندان سريعتر از دسترسي تصادفي (random access) نمي باشد، تكنيكهاي پردازش پرس و جو كه از سريعتر بودن دسترسي ترتيبي بهره مند مي باشد ،در پايگاه داده مقيم در حافظه اصلي چندان سودمند نيستند . بعنوان مثال مي توان از پردازش merge join sort نام برد كه ابتدا يك دسترسي ترتيبي به منظور sort کردن رابطه ها دارد. اگر چه رابطه هاي sort شده مي توانند به راحتي توسطpointer list در حافظه اصلي نمايش داده شوند .ولي در حقيقت به اين عمل sort كردن نيازي نيست زيرا بسياري از اهداف آن قبلا به دليل استفاده از MMDB از بين رفته است.
Application program Interface
MMDB مانند DRDB داراي يك cache بزرگ نمي باشد زيرا داده هاي درون cache كه توسط شاخص در دسترس واقع مي شوند، براي وقتي طراحي شده اند كه نياز به دسترسي به ديسك داشته باشيم بدين ترتيب كه دسترسي توسط buffer manager انجام مي شود كه يك آدرس از ديسك به آن داده شده و بررسی مي شود كه آيا بلاك مربوطه در cache حافظه اصلی وجود دارد يا نه و سپس آن را به محدوه کاری application در حافظه اصلی ،كپي مي كند.
در MMDB داده ها بطور مستقيم توسط ارجاع به آدرس حافظه دسترسي مي شوند.شكل هاي زير بياتگر اين امر مي باشند.
Application Program Interface for DRDB
Application Program Interface for MMDB
Recovery
دريك پايگاه داده مقيم در حافظه اصلي (MMDB) نسخه اصلي پايگاه داده در حافظه اصلي كه volatile است قرار دارد و اين باعث مي شود كه سيستم MMDB نسبت به پايگاه داده هاي مقيم در ديسك (DRDB) بيشتر در معرض failure باشند.
سيستم هايMMDB براي application هايي كه نيازبه بازده بالاو "زمان پاسخ" سريع دارند ايده آل مي باشند.با افزايش تقاضا براي سيستمهايي با performance بالا و كاهش مداوم قيمت حافظه ،MMDBها جايگزين مناسبي براي DRDB ها به نظر مي رسند.
يك معماري عمومي MMDB حاوي يك حافظه اصلي -كه با RAM استاندارد پياده سازی شده است- و يك حافظه nonvolatile (پايدار) مي باشد. حافظه اصلي شامل نسخه اصلي پايگاه داده مي باشد وحافظه پايدار log و يك نسخه پشتيبان از پايگاه داده را در خود نگه مي دارد . يك پروسه logger هم log ها را بصورت آسنكرون به ديسك flush مي كند. از طرف ديگر يك حافظه پايدار اضافي ديگر مي تواند به عنوان shadow memory استفاده شود.اين حافظه مي تواند براي نگه داشتن بهنگام سازی های ايجاد شده توسط تراکنشهای فعال و انتهاي log كه حاوي اطلاعاتي در مورد اين بهنگام سازی ها است، بكار رود.
اگرچهMMDBها مي توانند پاسخگوي performance بالاي بسياري از real-time applicationها باشند ولي در مقايسه با DRDBها ، ذاتا آسيب پذيرتر مي باشند. بنابراين مولفه ِrecovery يك سيستم MMDB بايستي بطور مناسبي طراحي ،پياده سازي و نگهداري شود.
سه جنبه يك زيرسيستم recovery باعث مي شود كه مطمئن باشيم از هر نوع failure مي توان recovery را انجام داد:,logging reloading , checkpointing .
Logging يك log از بهنگام سازی هايي كه در زمان اجراي تراکنشها انجام مي شود را نگه مي دارد.
Checkpointing به صورت متناوب يك snapshot از پايگاه داده گرفته و آن را به منظورپشتيبانی در حافظه ماندگار ذخيره مي كند. Checkpointing با كاهش تعداد ركوردهاي log كه بايستي در زمان restart كردن سيستم بررسی شوند ، ميزان كاري را كه بايستي در recovery از يك failure انجام شود کاهش می دهد.
سر انجام پس از يك system crash عمل reloading پايگاه داده را دوباره در يك وضعيت پايدار(consistent state) ذخيره مي كند.درreloading ابتدا نسخه پشتيبان كه از زمان آخرين checkpoint ثبت شده است ،دوباره در حافظه اصلي بارشده و سپس يك وضعيت پايدار از پايگاه داده با بكار بردن اطلاعات redo وundo ِثبت شده در log ،بدست مي آيد .
نتايج آزمايشات بيانگر اين است كه زمان recovery تقريبا بطور خطي با افزايش سايز پايگاه داده افزايش مي يابد و تعداد tupleها در پايگاه داده بيشتر از سايز يك tuple در زمان recovery تاثير دارد.
خلاصه اي از تكنيك هاي Recovery
Recovery manager در سيستم پردازش تراکنشها مسوول تامين انسجام (consistency) در سيستم پايگاه داده با وجود crash در سيستم يا تراکنش مي باشد. براي انجام اين كار اعمالي نظير loggingو checkpointing در حين اجراي نرمال سيستم لازم است.در اينجا پيرامون سه بخش از سيستم recovery در MMDB بحث خواهد شد.
Logging
در MMDB اطلاعات درون log در دو سطح مي تواند ثبت شود:physical logging و logical logging . در physical logging به ازای هر بهنگام سازی ، وضعيت پايگاه داده تغيير داده شده و محل فيزيكي (مثل page id و offset ) كه بهنگام سازی در آن انجام شده است، را ثبت مي كند.
Logical logging ، وضعيت تراکنش از پايگاه داده و محل منطقي كه بهنگام سازی روي آن اثر داشته است, را ثبت مي كند. مزيت logical logging اين است كه مي تواند با به كار بردن معاني operation ها آيتم هاي كمتري را log كند ولي از طرف ديگر در logical logging بايستي بررسي شود كه هر عملي كه commit شده است دقيقا يك بار انجام شده باشد و بطور مشابه هر عملي كه uncommitted است دقيقا يك بار undone شده است. بنابر اين logical logging باعث افزايش پيچيدگي پايگاه داده چه در حين اجراي نرمال و چه در حين recovery مي شود.
Write Ahead Logging (WAL)معروفترين نوع از قوانين logging است كه پذيرفته شده و استفاده مي شود. در WAL داده هاي log بايستي قبل از اينكه بهنگام سازی بتواند روي پايگاه داده انجام شود ، روي حافظه ماندگار نوشته شوند. پروتكل WAL باعث مي شود كه تاثير اعمال commit نشده بتواند undone شود . در مورد تراکنش هاي commit شده ، DBMS بايد همواره اثر بهنگام سازی ها را بدون در نظر گرفتن failure ها نشان دهد. بنابراين وقتي يك تراکنش ، commit مي شود اطلاعات Redo كه توسط اين تراکنش نوشته شده بايد به حافظه پايدار فرستاده شود.
Checkpointing
Checkpointing باعث مي شود كه ميزان كاري كه در حين restart كردن سيستم بعد از crash بايستي انجام شود كاهش يابد. الگوريتم checkpointing بايد به گونه اي باشد كه تداخل با اعمال نرمال تراکنش حداقل بوده و recovery به طور موثري بعد از crash بتواند انجام شود. روشهاي checkpointing درMMDB به سه دسته تقسيم مي شود:
Log-driven checkpointing, fuzzy checkpointing, non-fuzzy checkpointing
درnon-fuzzy checkpointing ، checkpointer ابتدا روي داده هايي كه بايستي checkpointing شوند lock مي گيرد بنابراين انسجام پايگاه داده حفظ خواهد شد. اين انسجام مي تواند مبتنی بر عمل(action oriented ) يا مبتنی بر تراکنش( (transaction oriented باشد.action oriented بهتر است و تداخل كمتري نسبت به transaction oriented ايجاد مي كند.
در fuzzy checkpointing ،checkpointer هيچ lock ايی نمي گيرد. براي همزمان بودن با تراکنش نرمال ، checkpointing يك ركورد را در log بعد از كامل شدن checkpointing مي نويسد.علاوه بر اين پايگاه داده در بخش هايي dump مي شود.
در log-driven checkpointing ، checkpointer به جاي dump كردن از MMDB ، log را روي dump قبلي اعمال مي كند تا dump جديدي ايجاد نمايد.اين تكنيك نسبت به flush كردن مستقيم dirty page ها ،كارايي كمتري داشته و اكثرا براي ايجاد remote backup از پايگاه داده بكار مي رود.
Reloading
Reloading آخرين و يكي از مهمترين بخش هاي پروسه recovery است. Reloading بايد اين اطمينان را حاصل كند كه پايگاه داده بعد از crash، منسجم (consistent) است. پايگاه داده از آخرين checkpoint بار مي شود و اعمال undo و redo انجام مي شود تا پايگاه داده به آخرين وضعيت پايدار,(consistent state) برسد. تكنيكهاي reloading موجود را مي توان در دو دسته تقسيم كرد: simple reloading و concurrent reloading .
در روش simple reloading سيستم عمل نرمال خود را تا وقتي كه همه پايگاه داده به حافظه برگردانده نشود ، شروع نمي كند. در concurrent reloading اعمال reloading و پردازش تراکنش بطور موازي انجام مي شوند. بطور خاص پايگاه داده در وقت نياز reload مي شود. اگرپايگاه داده بزرگ باشد ، simple reloading مي تواند زمان زيادي بگيرد. يك راه حل ممكن براي اين مشكل اين است كه بلاك هاي پايگاه داده در وقت نياز به حافظه بار شوند به جای اين که همه پايگاه داده به حافظه آورده شود. راه حل ديگر استفاده از disk striping يا disk arrays است كه در آن پايگاه داده روي چندين ديسك پخش شده و بطور موازي خوانده مي شود.براي اينكه اين روش كارا باشد بايستي مسيرهاي مختلفي از ديسك به حافظه وجود داشته باشد.
نتيجه گيري
مبحث قرار دادن كل پايگاه داده مقيم در حافظه اصلي يا MMDB اخيرا يك موضوع تحقيقاتي مورد بحث مي باشد. به دليل پيشرفت تكنولوژيكي حافظه فيزيكي پايدار ، استفاده از سرعت حافظه اصلي براي پايگاه داده، امري ممكن مي باشد بطوري كه از حافظه فيزيکی به عنوان محل ذخيره اصلی و از ديسک به عنوان backup استفاده مي شود.
استفاده از پايگاه داده مقيم در حافظه اصلي چندين مزيت دارد از جمله : افزايش چشگير کارايی با حذف نياز به I/O و در نتيجه کاهش زمان پردازش و افزايش throughput با حذف I/O overhead .
برای ممکن ساختن شيفت از پايگاه داده های معمولی به پايگاه داده مقيم در حافظه اصلي سيستم پايگاه داده از ابتدا بايستی دوباره طراحی شود تا علاوه بر بهره مند شدن از performance بالای پايگاه داده مقيم در حافظه اصلي، بتواند مسائل پياده سازی ناشی از تفاوت ديسک و حافظه را دربر گيرد که از جمله اين مسائل می توان به concurrency control، commit processing، access methods، query processing و recovery اشاره نمود.
منابع
-[1] Inseon Lee, Heon Y.Yeon, Taesoon Park, “A New Approach for Distributed Main Memory Database Systems: A Causal Commit Protocol”, IEICE TRANS. INF. & SYST., VOL.ES7, NO.1 JANUARY 2004
-[2] Nicholas Carriero, Michael V. Osier, Kei-Hoi Cheung, Peter Masiar, Perry L. Miller, Kevin White, Martin Schultz, “ Exploring the Use of Main Memory Database (MMDB) Technology for the Analysis of Gene Expression Microarray Data”, Technical report, April 2004
-[3] Stefan Manegold, “Understanding, Modeling, and Improving Main-Memory Database Performance”, November 2002
-[4] Philip Bohannon, Peter McIlroy, Rajeev Rastogi,”Main Memory Index Structures with Fixed Size Partial Keys”, ACM SIGMOD 2001 May 2124,Santa Barbara, California, USA
-[5] S. Manegold, P. A. Boncz, and M. L. Kersten. “Optimizing Main-Memory Join on Modern Hardware”, IEEE Transactions on Knowledge and Data Engineering (TKDE), 14(4):709–730, July 2002.
-[6] J. Rao and K. A. Ross. “Making B+-Trees Cache Conscious in Main Memory”, In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 475–486, Dallas, TX, USA, May 2000.
-[7] Tobin J. Lehman, Michael J. Carey, “A Study of Index Structures for Main Memory Database Management Systems”, Proceedings of the Twelfth International
Conference on Very Large Data Bases, Kyoto, August, 1986
-[8] Rajeev Rastogi, S. Seshadri, Philip Bohannon, Dennis Leinbaugh, “Logical and Physical Versioning in Main Memory Databases”, Proceedings of the 23rd VLDB Conference, Athens, Greece, 1997
-[9] Hector Garcia-Molina, Kenneth Salem, “Main Memory Database Systems: An overview”, IEEE 1992
-[10] Piyush Burte, Boanerges Aleman-Meza, D. Brent Weatherly, Rong Wu, “Transaction Management for a Main-Memory Database”
-[11] Tobin J. Lehman, Michael J. Carey, “Query Processing in Main Memory Database Management Systems”, ACM, 1986
-[12] Margaret H. Eich, “Main Memory Database Recovery”, IEEE 1986
-[13] J. Baulier, P. Bohannon, S. Gogate, C. Gupta, S. Haldar, S. Joshi, A. Khivesera, H. F. Korth, P. McIlroy, J. Miller, P. P. S. Narayan, M. Nemeth, R. Rastogi, S. Seshadri, A. Silberschatz, S. Sudarshan, M. Wilder, and C. Wei. “DataBlitz Storage Manager: Main-Memory Database Performance for Critical applications”, In Proceedings of theACM SIGMOD International Conference on Management of Data (SIGMOD), pages 519–520, Philadephia, PA, USA, June 1999