دانلود با لینک مستقیم و پر سرعت .
لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه: 54
Main Memory Database
حافظه اصلی پایگاه داده ها
مقدمه
در اواسط دهه 1980، با نزول قیمت DRAM، این ایده مطرح شد که کامپیوترهای آتی با داشتن حافظه اصلی با ظرفیت بالا، می توانند بسیاری از پایگاه داده ها را درحافظه اصلی داشته باشند. در این شرایط می توان همه I/O ها (که بسیار هزینه بر می باشند) را از پردازش DBMS حذف نمود. بنابراین معماری DBMS دستخوش تغییرات جدی می شود و در یک MAIN MEMORY DBMS(MMDBMS)، مدیریت I/O دیگر نقشی نخواهد داشت.
نکته مهم در یک MMDB، چگونگی انجام تراکنشها و recovery بصورت کارا است. برخی از الگوریتمهای پیشنهادی براساس این فرض عمل می کنند که قسمت کوچکی از حافظه اصلی بصورت ماندگار وجود دارد که اطلاعاتش توسط باطری در صورت قطع برق از بین نخواهد رفت. این قسمت از حافظه اصلی برای نگهداری redo log ها استفاده می شود.
تعداد دیگری از الگوریتمهای پیشنهادی پیش فرض حافظه ماندگار را ندارند و همچنان از عملیات I/O برای نوشتن اطلاعات تراکنش در حافظه ماندگار استفاده می کنند. بنابراین در این الگوریتمها عملیات I/O بطور کامل حذف نمی شود، بلکه تعدادشان بسیار کمتر می شود زیرا I/Oمربوط به نوشتن اطلاعات صفحات buffer ها، حذف خواهد شد.
در یک MMDBMS، ساختارداده های ساده مانند T-Tree و همچنین bucket-chained hash جایگزین ساختارداده هایی چون B-Tree و linear hash در DBMS های مبتنی بر دیسک می شوند. بنابراین سرعت اجرای پرس و جو(پرس و جو) و بهنگام سازی بسیار افزایش می یابد و هزینه index lookup و نگهداری ،فقط مربوط به پردازنده و دسترسی به حافظه اصلی خواهد شد.
یکی از مشکلات اصلی در MMDBMS ها بهینه کردن درخواستهاست. عدم وجود I/O به عنوان فاکتور اصلی در هزینه ها به معنای پیچیدگی بیشتر مدل کردن هزینه در یک MMDBMS است زیرا در اینجا یکسری فاکتورهای فازی از قبیل هزینه اجرای پردازنده ، باید در نظر گرفته شوند. در این حالت باید با استفاده از تعامل روش coding، عوامل سخت افزاری مانند پردازنده و معماری حافظه و پارامترهای پرس و جو، به یک مدل قابل اطمینان از هزینه اجرا در حافظه اصلی رسید.
در دهه 1990، MMDBMS ها با افزایش سایز دیسکها و سایز مسائل همراه با افزایش ظرفیت DRAM ها، به اوج محبوبیت خود رسیدند. MMDBMS ها اغلب برای برنامه هایی که به پایگاه داده Real Time نیاز دارند (مانند سیستمهای embedded سوئیجهای تلفن) ، استفاده می شود. از آنجایط که سایز حافظه اصلی در کامپیوترها روز به روز در حال افزایش است، این امید وجود دارد که برای بسیاری از پایگاه داده هایی که امروزه امکان قرارگفتن آنها بصورت کامل در حافظه اصلی وجود ندارد، این شرایط مهیا شود.
مدلهای هزینه حافظه اصلی
متاسفانه تا کنون تلاشهای اندکی جهت مدل کردن هزینه کارایی MMDBMSها صورت گرفته است. تحقیقات اولیه روی طراحی ماشینهای پایگاه داده ها، بیشتر در زمینه وابستگیهای میان الگوریتمها و دسترسی حافظه صورت می گرفت.در صورتیکه امروزه به دلیل محدود شدن استفاده از MMDBMS ها به کاربرد در پایگاه داده های Real Time(به صورت پرس وجوهای ساده، مانند یک hash lookup در یک جدول)، اینگونه تحقیقات از اهمیت کمتری برخوردارند.
در تحقیقات اخیر در زمینه MMDBMS ها دو نمونه تحقیقاتی Office-By-Example (OBE) مربوط به شرکت IBM و Smallbase مربوط به شرکت HP مسائل ارزشمندی را درمورد بهینه سازی پرس وجو ها و مدلسازی هزینه حافظه اصلی مطرح کرده اند که در ادامه به بررسی این دو نمونه می پردازیم.
Office-By-Example (OBE)
OBE یک پایگاه داده در حافظه اصلی است که بسیاری از مفاهیمQuery-by-example(QBE)، را گسترش می دهد. برای بهینه سازی پرس و جو، مبتنی بر هزینه، OBE یک مدل کامل از هزینه را ارائه می دهد. باتوجه به این پیش فرض که داده هایی که پردازش می شوند در حافظه اصلی قرار گرفته اند، عامل اصلی هزینه در پایگاه داده های متداول که همان دسترسی I/O است حذف خواهد شد.
در این صورت هزینه محاسبات پردازنده از اهمیت بالایی برخوردار خواهد شد. این در حالیست که مدلسازی هزینه پردازنده بسیاردشوار است و پارامترهای زیادی از قبیل طراحی نرم افزار، معماری سخت افزار و حتی روش برنامه نویسی، در مدلسازی هزینه پردازنده دخیل هستند. بعلاوه تحلیل دقیق سیستمهای بزرگ به منظور شمارش تعداد سیکلهای پردازنده غیر ممکن می باشد.
راه حل پیشنهادی، استفاده از روشهای تجربی و روشهای تحلیلی در کنار یکدیگر است.
در ابتدا، bottleneck های سیستم با استفاده از یک تحلیلگرِ اجرا شناسایی می شوند. در این روش تنها bottleneck ها، برای مدلسازی هزینه پردازنده بکار می روند.
البته در این مرحله، بسیار مهم است که bottleneck ها تا حد ممکن توسط تلاشهای معقول اصلاح شوند.
مرحله بعد پیدا کردن وزن نسبی هریک از bottleneck ها و مشخص سازی واحد هزینه آنها توسط روشهای تجربی است.
برای OBE، bottleneck ها و واحدهای هزینه بصورت زیر مشخص می شوند :
- ارزیابی expression هایی که در predicate ها آمده اند. (واحد هزینه = C1)
- عملیات قیاسی که برای مشخص کردن خروجی نهایی predicate ها لازم است. (واحد هزینه = C2)
- بازیابی یک tuple از یک رابطه موجود در حافظه اصلی. (واحد هزینه = C3)
- واحد عملیاتِ ساختن شاخص (index) ( ساختن شاخص روی رابطه ای که n تا tuple دارد، nLog2n برابر واحد هزینه دارد. واحد هزینه = C4)
- واحد عملیات در مرتب سازی ،که در شرایط شاخصهای چند ستونی(multi-column index) مورد نیاز است. (واحد هزینه = C5)
جالبترین نتیجه بدست آمده از آزمایشات این است که، هزینه ارزیابی expression های سیستم، بیشترین هزینه از میان هزینه های مطرح شده در OBE می باشد.در حالیکه C2 تا C5 تقریبا یکسان می باشند، C1 به میزان قابل توجهی بیشتر از آنهامی باشد.
در ادامه به بررسی نمونه Smallbase می پردازیم.
Smallbase
در smallbase، مدل هزینه حافظه اصلی به سه گروه تقسیم می شود:
- Hardware-based
این مدل بسیار شبیه مدل هزینه مبتنی بر I/O در پایگاه داده های متداول است. به جای شمارش عملیات I/O، تعداد سیکلهای پردازنده شمارش می شود. علیرغم اینکه این روش بسیار ساده به نظر می رسد، از جهت پیاده سازی مشکلات عمده ای وجود دارد.بعلاوه، portability بسیار محدود خواهد شد زیرا این سیاستها میان معماریهای سخت افزار، متفاوت است. در هر حال این مدل بسیار دقیق و قابل لطمینان می باشد.
- Application-based
در این روش هزینه ها بر اساس هزینه bottleneck های سیستم بیان می شود.علیرغم اینکه این روش از جهت پیاده سازی بسیار ساده تر از روش hardware-based است، این نوع مدل از عمومیت کمتری برخوردار است.
Bottleneck ها بسیار وابسته به workload ِمورد استفاده برای شناسایی آنها، دارد و بنابراین نمی توان از این روش برای نمایش هزینه های همه انواع پرس و جو استفاده کرد.
در اصل،این مدل نسبت به مدل hardware-based از portability بالاتری (توسط تولید دوباره پروفیل) برخوردار است. به هر حال، این روش نه تنها باعث تفاوت در واحدهای هزینه می شود بلکه مجموعه bottleneck ها هم متفاوت خواهد شد.در این حالت اگر مدل، دستخوش تغییرات شود، هزینه توابعِ هزینه مربوط به عملیات پایگاه داده، باید دوباره بر اساس bottleneck های جدید فرمولسازی شود.
- Engine-based
این مدل هزینه، مابین مدل hardware-based - که دقیق و پیچیده است- و مدل application-based -که علیرغم سادگی از عمومیت کمتری برخوردار است-، قرار دارد. این مدل بر اساس هزینه عملیات ابتدایی که موتور اجرایی MMDBMS تامین می کند، عمل می کند.
در یک پروسه دو مرحله ای این مدل توضیح داده می شود:
در این مدل عمومی ابتدا عوامل اصلی هزینه شناخته می شوند و هزینه پردازش پرس و جو بر اساس عوامل شناخته شده بیان می گردد. سپس مدل با مشخص کردن مقادیر مربوط به این عوامل، مقداردهی اولیه شده و سپس ارزیابی می شود.
مرحله اول نیاز به اطلاعات کامل در مورد اجزای داخلی موتور اجرایی دارد و عموماً توسط دست انجام می شود. در مورد اینکه مدل تا چه حد باید جزئی و دقیق باشد، این پاسخ مطرح می شود که مدل باید تا آنجایی که به feasibility سیستم خدشه ای وارد نشود، بصورت جزئی مدل شود. یکسری ساده سازیها و بهبود و دوباره نگری در طی مرحله ارزیابی قابل انجام است.
برای سیستم smallbase ، هزینه های ابتدایی زیرشناسایی شده اند :
- Fetch کردن یک ستون ویا مقدار یک پارامتر
- انجام عملیات ریاضی و منطقی
- اجرای یک عمل مقایسه
- اجرای expression ایی که like داشته باشد
- scan کردن جدول، T-tree index، hash index، جدول موقت
- ساخت و از بین بردن T-tree index، hash index، جدول موقت
- مرتب سازی tuple ها
- انتخاب tuple های مشخص
- انجام عمل join (nested loop join، merge join)
به وابستگیهای هزینه به فاکتورهایی از قبیل سایز جداول، نوع داده ها و ... در مرحله دوم پرداخته می شود.
در مرحله دوم یک برنامه تست ،وظیفه مقداردهی اولیه و ارزیابی مدل را بصورت اتوماتیک برعهده دارد. برای هر واحد هزینه دو پرس و جو که هزینه اجرایشان، فقط در آن مقدار متفاوت باشد، در نظر گرفته می شود. بعلاوه فرمولهایی که وابستگی هر واحد هزینه را به سایز جدولها نشان می دهند، باید مشخص شوند.
برنامه تست هزینه سپس پارامترهای مربوطه و ارزیابی مدل را با اجرای هر زوج پرس و جو به تعداد مکرر با سایزهای متفاوت جداول انجام می دهد.
ساختارهای شاخص در حافظه اصلی
ساختارهای شاخصِ طراحی شده برای حافظه اصلی، متفاوت از طراحی های رایج برای سیتم های مبتنی بر دیسک می باشند.اهداف اصلی در طراحی یک شاخص مبتنی بردیسک عبارتند از : به حداقل رساندن تعداد دستیابی ها به دیسک و به حداقل رساندن فضای دیسک.در حالی که یک شاخص مبتنی بر حافظه اصلی ،در حافظه اصلی قرار گرفته واصلا دستیابی به دیسک وجود ندارد که حداقل شود از این رو، هدف اصلی از طراحی یک ساختار شاخص مبتنی بر حافظه اصلی ،کاهش زمان کلی محاسبات و در عین حال ، به کار گیری حداقل حافظه ممکن می باشد.
در یک پایگاه داده مبتنی بر حافظه اصلی، رابطه ها در حافظه قرار می گیرند،بنابراین،نیازی نخواهد بود که شاخص، مقادیر واقی صفات را ذخیره کند، در عوض می توان از اشاره گر هایی به tupleها استقاده نمود و با استفاده از این اشاره گرها ، مقادیر واقعی صفات را در هنگام لازم ، بازیابی نمود.
چنین روشی چندین مزیت دارد:
- با استقاده از اشاره گرِ tuple،شاخص، هم به مقادیر صفات آن tuple دسترسی دارد و هم به خود tuple ،بنابراین اندازه شاخص کاهش می یابد.
- این روش ، سبب کاهش پیچیدگی در سازماندهیِ رکوردهایی با اندازه های زیاد و متغیر،و روشهای فشرده سازی در شاخص ها می شود.
- با انجام عملیات بهنگام سازی،شاخص ها نیز باید بهنگام شوند، در این حالت، جابجایی اشاره گرها بسیار ارزان تر از جابحایی مقادیر صقاتِ (معمولاً) طولانی تر می باشد.
این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید
