‫دانشکده برق و کامپیوتر دانشگاه تهران‬
‫پایگاه داده های مقیم در حافظه‬
‫‪Main Memory Databases‬‬
‫‪1‬‬
‫ابوالفضل آل احمد ‪ -‬هادی امیری‬
‫منابع‬
[1] Stefan Manegold, Understanding, Modeling, and Improving Main-Memory
Database Performance, November 2002
[2]Monet Database, http://monetdb.cwi.nl/
[3]University of Konstanz – Mainmemory Databases , http://www.inf.unikonstanz.de/dbis/teaching/ws0203/main-memory-dbms/
[4] Hector Garcia-Molina, Member, IEEE, and Kenneth Salem, Member, IEEE,Main
Memory Database Systems: An Overview, December 1992
[5]Main-Memory Databases - “Introduction to MMDB” ,Maurice van Keulen, October
16, 2002
[6]Main-Memory Databases - “MIL introduction” ,Maurice van Keulen, October 29,
2002
2
‫منابع‬
[7]Main-Memory Databases - “Main-Memory DBMS architecture” ,Maurice van
Keulen, January 14, 2003
[8]FastDB - Main Memory Relational Database Management System ,
http://www.garret.ru/~knizhnik/fastdb.html
[9]Piyush Burte, Boanerges Aleman-Meza, D. Brent Weatherly, Rong Wu, Transaction
Management for a Main-Memory Database ,2002
[10] A Comparison Study of Main Memory Databases And Disk-Resident Databases,
Fahimeh Raja, Niloofar Razavi, Melody Siadaty, Maseud Rahgozar, Department of
ECE, University of Tehran, Tehran, Iran, 2005
[11] The Internals of the Monet Database, Bogdan Dumitriu Lee Provoost, June 6, 2005
[12] FastDB, http://www.garret.ru/~knizhnik/fastdb.html
3
‫پایگاه داده های مقیم در حافظه‬
‫‪‬‬
‫پایگاه داده هاي معمول با توجه به خصوصیات و مکانیزم هاي ذخیره‬
‫سازي روي دیسک بهینه شده اند‬
‫‪‬‬
‫پایگاه داده هاي مقیم درحافظه مکانیزم متفاوتي جهت سازماندهي و‬
‫ساختار دادن به داده ها استفاده مي کنند‬
‫‪‬‬
‫حافظه هاي نیمه هادي روز به زور ارزان تر مي شوند و عالوه بر آن‬
‫حجم آنها نیز زیاد تر مي شود که استفاده از ‪ MMDB‬را توجیه مي کند‬
‫‪4‬‬
‫تفاوت هاي اصلي حافظه اصلي و دیسک‬
‫‪‬‬
‫دسترسي به حافظه اصلي بسیار کمتر از دیسک زمان بر است‪.‬‬
‫‪‬‬
‫حافظه اصلي فرار است در حالي که دیسک پایدار است‪.‬‬
‫‪‬‬
‫دسترسي ترتیبي به دیسک سریع تر از دسترسي اتفاقي است در‬
‫حالي که در ‪ MMDB‬تفاوتي نمي کند‬
‫‪‬‬
‫داده هاي موجود در حافظه اصلي مستقیما توسط ‪ CPU‬قابل‬
‫دسترسي هستند در حالي که دیسک این طور نیست‬
‫‪5‬‬
MMDB ‫برخی از کاربردهای‬
Embedded/Small Foot Print System

Real Time Databases

Parallel High Performance DBMSs

Virtual Memory DBMS

6
‫تخصیص فضا در حافظه اصلی‬
‫‪‬‬
‫سرعت افزایش داده هاي پایگاه داده پایین است و حجم حافظه‬
‫اصلي زیاد است‬
‫‪‬‬
‫قسمت هایي از داده ها که زیاد مورد دسترسي قرار مي‬
‫گیرند‬
‫در سیستم بانک داري‪ ،‬اطالعات حساب ها زیاد مورد دسترسي قرار‬
‫مي گیرند و اطالعات مشتري ها کمتر و اطالعات فعالیت هاي‬
‫انجام شده در بانک کمتر از بقیه مورد دسترسي قرار مي گیرند‬
‫‪7‬‬
‫بحث فراربودن در ‪ MMDB‬و گارانتي توسط سخت افزار‬
‫استفاده از حافظه هاي ‪ Battery Backed up‬واستفاده از منبع برق مطمئن و ‪. . .‬‬
‫موارد دیگري كه بایست در نظر گرفت‪:‬‬
‫‪‬‬
‫‪‬‬
‫‪ Crash‬کردن سیستم عامل‬
‫احتمال از کار افتادن ‪ UPS‬و یا ‪Battery Backed Up‬‬
‫‪ Memory‬بسیار بیشتر از از کار افتادن دیسک است‬
‫راه حل‪:‬‬
‫‪ Back up ‬گرفتن از ‪ MMDB‬در فواصل کمتري باید انجام شود‬
‫که سربار زیادي دارد‬
‫‪8‬‬
‫تاثیر مقیم بودن داده در حافظه‬
Concurrency Control
Commit Processing
Access Methods
Query Processing
Recovery
Performance
Application Programming Interface &
Protection
Data Clustering & migration
.1
.2
.3
.4
.5
.6
.7
.8
9
‫تاثير مقيم بودن داده در حافظه‬
‫‪‬‬
‫‪ :Concurrency Control‬مکانیزم هاي کنترل ‪Lock‬‬
‫در ‪ MMDB‬راحت تر و سریع تر است‪ .‬مي توان در کنار‬
‫هر رکورد که در حافظه است چند بیت را جهت عملیات‬
‫‪ Lock‬در نظر گرفت‪.‬‬
‫‪‬‬
‫‪ :Commit Processing‬تراکنشي ‪ Commit‬شود مي‬
‫بایست رکوردهاي فعالیت هاي انجام شده آن را در ‪ log‬ثبت‬
‫کرد‪ .‬از یک حافظه پر سرعت پایدار جهت ذخیره ‪log‬‬
‫استفاده مي شود‪.‬‬
‫‪10‬‬
‫تاثير مقيم بودن داده در حافظه‬
‫‪‬‬
‫‪ :Access Methods‬در تمام مکانیزم هاي ایندکس سازي در‬
‫‪ MMDB‬از اشاره گرها به جاي مقدار داده ها در ایندکس استفاده مي‬
‫شود‪.‬‬
‫‪‬‬
‫‪ :Query Processing‬دسترسي ترتیبي نسبت به دسترسي‬
‫تصادفي در‪ MMDB‬زیاد سریع تر نیست بنابراین مکانیزم هاي‬
‫پردازش پرس و جو که بر اساس دسترسي ترتیبي بهینه شده اند اهمیت‬
‫خود را ازدست مي دهند (مانند ‪ .)Sort-Merg join‬پردازش‬
‫گرهاي پرس و جو مي بایست بر روي هزینه پردازش تمرکز داشته‬
‫باشند‪.‬‬
‫‪11‬‬
‫تاثير مقيم بودن داده در حافظه‬
‫‪‬‬
‫‪ :Recovery‬جهت برگشت به حالت اولیه ابتدا مي بایست‬
‫‪ MMDB‬تمامي داده ها را از دیسک بخواند و به حافظه‬
‫بیاورد و با استفاده از‪ log‬داده ها را بروز رساني کند‪.‬‬
‫‪‬‬
‫‪ :Performance‬کارایي کلي ‪ MMDB‬به کلیه اجزاء آن‬
‫وابسته است‪ .‬بجز قسمت ‪ Commit Processing‬که‬
‫وابسته به عملیات هاي دیسک است بقیه قسمت ها به زمان‬
‫پردازش وابسته هستند‪.‬‬
‫‪12‬‬
‫تاثير مقيم بودن داده در حافظه‬
‫‪‬‬
‫‪‬‬
‫‪13‬‬
‫‪ :Application Programming Interface & Protection‬در ‪MMDB‬‬
‫جهت دسترسي به اشياء از آدرس آنها استفاده مي شود‪ .‬جهت‬
‫بهبود کار مي توان بافر مخصوص برنامه ها را حذف کرد و‬
‫اجازه دسترسي مستقیم را به برنامه ها داد‪ ،‬زیرا بسیاري از‬
‫زمان تراکنش ها صرف کپي کردن داده بین بافرها مي شود‪.‬‬
‫‪ : Data Clustering & migration‬مشکلي در ‪ MMDB‬وجود‬
‫دارد که داده ها جهت انتقال به دیسک چگونه و کجا باید‬
‫ذخیره شوند‪ .‬یک راه حل این است که مدیر ‪ MMDB‬نحوه‬
‫‪ Clustering‬را مشخص کند و راه حل دوم این است که‬
‫‪ MMDB‬خود بر اساس دسترسي هایي که به داده ها انجام‬
‫مي گیرد ‪ Clustering‬را انجام دهد‪.‬‬
‫برترین پایگاه داده های مبتنی بر حافظه اصلی‬
FastDB
MonetDB
eXtremeDB

PrismaDB
DataBlitz
Times Ten
ERDB






14
MonetDB
CWI ‫توسعه داده شده در‬

the Institute for Mathematics and Computer Science
Research of The Netherlands
open source
‫کارا در حوزه های مختلف‬

‫انجام همه عملیات در حافظه اصلی‬
‫جبر توسعه پذیر یا تعمیم پذیر‬
‫مدل رابطه باینری‬
‫استفاده موازی از حافظه‬

MonetDB is one of the first database systems to focus its
query optimization effort on exploiting CPU caches
MonetDB has played a pivotal role in the development of Data
Mining applications at DataDistilleries (now SPSS)


Data Mining, OLAP, GIS, XML Query, Text and Multimedia Retrieval,
(Real Time App)




15
Architecture
DBMS Architecture
16
Architecture
MonetDB Architecture
17
Architecture
MonetDB: architecture
Front-end/back-end
‫• پشتیبانی چندین مدل داده ای‬
‫• پشتیبانی چندین زبان‬
end-user languages
‫• استفاده در کاربردهای مختلف‬
18
‫‪Ideas‬‬
‫‪Monet Ideas‬‬
‫‪‬‬
‫ایده اول‪ :‬امکان استفاده از دستورات ‪Back-End‬‬
‫به این معني که شما مي توانید پرس و جوهایي را براي ‪ Back-End‬با استفاده از واسطي به نام‬
‫‪ Mapi Client‬بنویسید‪ .‬زباني که این واسط با آن کار مي کند ‪ MIL‬نام دارد‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪19‬‬
‫ایده دوم‪ :‬با جداول دودویي هر کاري مي توان کرد‬
‫ایده سوم‪ :‬عدم نیاز به اختراع دوباره سیستم عامل‬
‫ایده چهارم‪ :‬بهینه سازي اجراي پرس و جو در حافظه‬
Data Model
Monet Data Model
‫مقادیر ساده‬

Int,chr,str,oid,nil,intint(nil),chrchr(nil),strstr(nil),oidoid(nil)
Binary Association Tables (BATs)

‫ مي باشد‬BAT ‫ که شامل مقادیر ساده فوق و یا‬Head ‫ و‬Tail ‫جدولي است با دو ستون‬BAT
20
Data Model
Monet Data Model
BAT[oid,str]
BAT[oid,int]
BAT[oid, BAT[oid,int]]
21
Data Model
Storing Relations in MonetDB
22
Data Model
Relational Mapping
23
Data Model
Object-Oriented Mapping
24
Performance
Monet Performance
Monet ‫ با‬open source ‫مقایسه برخی از پایگاه داده های معروف و‬
build a binary table with the head representing an ordered sequence and
the tail a permutation over the values in the head


Response time is given in seconds while running on a dual Athlon 1400 with
25
1GB of RAM and 3.5GB of free space
-- DBtapestry Version=1.1 -- See http://monetdb.cwi.nl/DBtapestry/ -- (c) CWI 2004-2005 rows=100K --columns=2 -- Produced Sat Feb 26 23:41:51 2005
start transaction;
select now();
create table RKA( head int, tail int);
create table RKB( head int, tail int);
insert into RKA values(0,0);
insert into RKA values(1,360);
insert into RKA values(2,427);
……
insert into RKB select head+0, tail+0
from RKA;
insert into RKB select head+8192, tail+8192 from RKA;
……
drop table RKA;
update RKB set tail=(tail*47) % 102400;
……
create table tapestry( attr0 int , attr1 int);
insert into tapestry select R0.head, R0.tail from RKB R0;
drop table RKB;
select now();
commit;
-- actions=1249 -- tuplesRead= 1.07M tuplesWritten= 2.07M -- volumeRead= 8.59M
volumeWritten=16.59M
26
Language
Monet Interpreter Language (MIL)
27
Language
MIL Extensibility
28
‫‪Application‬‬
‫کاربردهای ‪Monet‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪29‬‬
‫کاربردهای مبتنی بر ‪Query‬‬
‫کاربردهای نیازمند کارایی زیاد‬
‫مدل های داده پیچیده‬
‫انجام پرس و جوی پیچیده‬
Application
Transactions (OLTP)
OLTP (Online Transaction Processing) is a form of transaction processing conducted via
computer network. Some applications of OLTP include electronic banking, order processing,
employee time clock systems, e-commerce, and eTrading.
30
Application
OLAP, Data Mining
On Line Analytical Processing. (OLAP) It is an approach to quickly provide the answer to
complex analytical queries. The typical applications of OLAP are in business reporting for
sales, marketing, management reporting, business performance management, budgeting and
forecasting, financial reporting and similar areas.
31
Application
‫حوزه های جديد‬
GIS:



New data types (point, polygon, etc..)
New search accelerators (R-Tree, etc..)
New primitives
boolean intersects(polygon,polygon)
Multimedia:


New data types (url, image, etc..)
new primitives (similarity search)
32
‫متشکریم!‬
‫‪33‬‬
Descargar

Top Main Memory DBs - دانشکده مهندسی برق