بلینک و انجام آن: جستارهای فعل و انفعالی در داده های بسیار بزرگ Blink and It’s Done: Interactive Queries on Very Large Data

مقدمه

شرکت ها به طور فزاینده ای ارزش تجزیه و تحلیل حجم زیادی از داده های جمع آوری شده را استنباط نمودند. مواردی وجود دارد که تحلیلگران در آن از قابلیت اجرای جستارهای اکتشافی کوتاه بر روی این داده ها بهره مند می شوند. مثال هایی از چنین جستارهای اکتشافی شامل تحلیل ریشه ای وقایع(root-cause) و تشخیص مشکل در سیاهه های مربوط (مانند شناسایی علت راه اندازی طولانی در جریان ویدیویی وب سایت) و جستار تحلیل اثربخشی برنامه های تبلیغاتی(ad campaign) در زمان واقعی می باشد. اغتنام فرصت (timeliness ) در بسیاری از این جستارها، بیشتر از صحت کامل اهمیت دارد، جستارها موردی هستند (به عبارت دیگر، آنها پیشرفته نیستند) و شامل پردازش حجم زیادی از داده ها می باشند.

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

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید. این امر در صفحه اول نقل آن ذکر شده است. در غیر این صورت، نسخه برداری، چاپ مجدد، ارسال بر روی سرور یا توزیع مجدد در فهرست ها، مستلزم اجازه قبل و/ یا هزینه خاص می باشد. در 38 اُمین کنفرانس بین المللی بانک های اطلاعاتی بسیار بزرگ(Very Large Data Bases)، در بیست و هفتم - سی و یکم  آگوست 2012، استانبول، ترکیه خواسته شد تا مقالات این کتاب نتایج شان را ارائه دهند.

در این اثبات تجربی، BlinkDB را مطرح می نماییم که چارچوب پردازش جستار های تقریباً موازی بهینه سازی شده برای پاسخ های فعل و انفعالی در داده های با حجم بالا می باشد. می توان تجمع جستارها در  BlinkDBرا توسط محدودیت های حداکثر زمان اجرا یا خطا تفسیر نمود. به عنوان مثال، جدول زمان کاری ، ذخیره سازی زمان های کاری وب سایت مرورگرهای کاربران در وب سایت های رسانه ها ای، با پنج ستون را در نظر بگیرید: زمان کاریID (SessionID )، نوع(Genre)، OS  (در حال اجرا بر روی دستگاه کاربر)، شهر(City) و URL (وب سایت های بازدید شده توسط کاربر). جستار زیر درBlinkDB  ، فرکانس زمان کاری در حال جستجو در رسانه های نوع «غربی» را برای هر OS با خطای نسبی 10 ٪ و ضریب اطمینان 95٪ باز خواهد گرداند.

SELECT COUNT(*)

FROM Sessions

WHERE Genre = ’western’

GROUP BY OS

ERROR 0.1 CONFIDENCE 95%

Similarly, given the query below, BlinkDB returns an approximate

count within 5 seconds along with the estimated relative error at the

95% confidence level.

SELECT COUNT(*), ERROR AT 95% CONFIDENCE

FROM Sessions

WHERE Genre = ’western’

GROUP BY OS

WITHIN 5 SECONDS

به طور مشابه، با توجه به جستار زیر، BlinkDB تقریباً در 5 ثانیه همراه با خطای نسبی برآورد شده در سطح اطمینان 95٪ باز می گردد.

BlinkDB  این کار را توسط پیش محاسبه و مجموعه ای به دقت انتخاب شده از نمونه های داده ها و جستارهای در حال اجرا در یک نمونه مناسب و به منظور رفع خطا و محدودیت های زمانی جستار انجام می دهد. BlinkDB ، برای بررسی جستار ها در زیر گروه های نسبتاً نادر، مجموعه ای از نمونه های یکنواخت و همچنین مجموعه های مختلفی از نمونه های سوگیری شده را حفظ نموده و هریک را در زیر مجموعه ای از ستون ها طبقه بندی می نماید.

حفظ نمونه های طبقه بندی شده در همه زیر مجموعه های ستون مستلزم مقداری ذخیره نمایی و از این رو امری غیر عملی می باشد. از سوی دیگر، نمونه های طبقه بندی شده محدود درآن دسته از زیر مجموعه ی ستون ها که در جستارهای قبلی ظاهر شده، کاربردپذیری جستار موردی را محدود می نماید. بنابراین، برای تعیین طبقه مجموعه ای از ستون ها که در آن فرمول بهینه سازی توزیع داده ها، جستار های قبلی، محدودیت های ذخیره سازی و چندین عامل مرتبط با سیستم های دیگر در نظر گرفته شده،  بر یک چارچوب بهینه سازی تکیه می کنیم. BlinkDB  با استفاده از این ورودی ها، مجموعه ای از نمونه ها را انتخاب می کند که به پاسخ جستار متعاقب کمک خواهد نمود و در عین حال ذخیره سازی اضافی مورد استفاده برای کمیت قابل تنظیم کاربر را محدود می نماید. نمونه ها به خودی خود چند بعدی (به عبارت دیگر، با گرایش به ستون های مختلف) و دارای تفکیک پذیری چندگانه (multiresolution) می باشند. مورد دوم به معنای آن است که ما تنوع اندازه نمونه ها را حفظ می کنیم و در حین به حداقل رساندن زمان پاسخ (یا خطا) BlinkDB  را قادر به پاسخدهی موثر به محدودیت های مختلف (یا زمان) جستار می نماییم. جزئیات بیشتر در مورد این تدوین مشکل بهینه سازی را می توان در منبع [4] یافت.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید. همچنین می تواند درShark  (Hive  در Spark) ،که چارچوبی توسط  Hive دارای سازگاری برگشتی(backwards compatible ) می باشد، هم در لایه های ذخیره سازی و زبانی  اجرا شود و از Spark  برای اعتماد به مجموعه داده های حافظه نهان استفاده می شود. در نتیجه، جستارBlinkDB  که بر روی نمونه های ذخیره شده اجرا می شود، به جای چند دقیقه در چند ثانیه صورت می گیرد. BlinkDB  یک منبع باز است و تاکنون چندین شرکت خدمات آن لاین به استفاده از آن ابراز علاقه نمودند.

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید. از جستارها را با تمرکز بر شناسایی مشکلات در این فایل های ثبت وقایع نشان خواهیم داد. BlinkDB  و همچنین Hive و Shark  اصلاح نشده را اجرا خواهیم نمود و نشان می دهیم که سیستم ما می تواند پاسخ های محدود، تقریبی را در کسری از زمان سیستم های دیگر ارائه نماید. همچنین اجازه خواهیم داد که شرکت کنندگان جستار های خود را برای بررسی داده ها و عملکرد BlinkDB انتشار دهند.

2. مرور کلی سیستم

در این بخش، تنظیمات و مفروضاتی را توصیف می نماییم که در آن BlinkDB برای بهره برداری طراحی شده است و مروری کلی از طراحی و مولفه های کلیدی آن ارائه می نماید.

2.1. تنظیمات و مفروضات

BlinkDB   مانند یک انبار داده با یک جدول حقیقتی بزرگ طراحی شده است. ممکن است این جدول نیاز داشته باشد که با استفاده از کلیدهای خارجی به دیگر ابعاد جداول بپیوندد. در عمل، ابعاد جداول بطور قابل توجهی کوچکتر هستند و معمولا متناسب حافظه جمعی دسته ای می باشند. BlinkDB  تنها نمونه های طبقه بندی شده برای جداول حقیقی و پیوستن به ابعاد بزرگتر ستون جداول را ایجاد می نماید.

علاوه بر این، از آنجا که حجم کار ما در جستار های موردی هدف قرار داده شده است، به جای فرض این که جستار دقیق پیشینی شناخته شده است، فرض می کنیم که قالب های جستار  (به عنوان مثال، مجموعه ای از ستون های مورد استفاده در مادهWHERE و GROUP-BY) در طول زمان نسبتاً پایدار می مانند. از این فرض در زمان انتخاب نمونه ها استفاده می کنیم. این تصور بطور تجربی در انواع واقعی حجم کار تولید جهانی و همچنین مقدار حقیقی مسیر جستار مشاهده شده است و از آن برای ارزیابی اولیه (مسیر جستار  2 ساله شرکت Con-viva) استفاده می کنیم. ما دانش قبلی ارزش های خاص یا مسندهای مورد استفاده در این بند را در نظر نمی گیریم.

در نهایت، در این اثبات تجربی، بر روی مجموعه ای کوچک از اپراتورهای مجتمع تمرکز می نماییم: COUNT، SUM، MEAN ، MEDIAN/QUANTILE . با این حال، از برآورد خطای بسته برای ترکیبی از مجموعه های اساسی و همچنین تابع جبری میانگین ​​مانند و بطور مجانبی عادی پشتیبانی می نماییم، همانطور که در منبع [11] توصیف شده است.

2.2. ساختار

شکل1 ساختار کلی BlinkDBرا نشان می دهد که گسترش دهنده Hive وShark  می باشد. Shark  دارای سازگاری برگشتی(backwards compatible) با Hive می باشد، بر روی Spark قابل اجراست و یک چارچوب محاسبات خوشه ای می باشد که می تواند ورودی ها و داده های میانجی ​​در حافظه را پنهان نماید. BlinkDB  دو مولفه اصلی را با هم ترکیب می نماید(1) مولفه ای برای ایجاد و حفظ نمونه، (2) مولفه ای برای پیش بینی زمان پاسخ جستار و دقت و انتخاب نمونه ای که به بهترین حالت محدودیت های مشخص را ایفا می نمایند.

2.2.1. ایجاد و حفظ نمونه

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

شکل 1: ساختار BlinkDB

 نمونه ها بر اساس آمار جمع آوری شده از داده های متضمن (به عنوان مثال، نمودار هیستوگرام ها) و قالب های جستار  تاریخی ایجاد و به روز رسانی شده اند.BlinkDB  مجموعه ای از نمونه های یکنواخت و مجموعه ای متعددی از نمونه های طبقه بندی شده را ایجاد و حفظ می کند. مجموعه ای از ستون ها که در آن نمونه ها طبقه بندی شده اند، باید با استفاده از چارچوب بهینه سازی ای ایجاد شوندکه در آن مجموعه ای از ستون (ها) به دلایل ذیل برگزیده شده اند:(1) ارزیابی بسیار مفید قالب جستار  در حجم کار و (2) نمایش بزرگترین مورب ، به عبارت دیگر، دارای توزیعاتی هستند که در آن مقادیر بسیار نادر به احتمال زیاد از یک نمونه یکنواخت جدا شده اند. مجموعه ای از نمونه ها توسط ورود داده های جدید و زمان تغییرات حجم کاری به روز رسانی شده اند.

2.2.2. انتخاب نمونه حین اجرا

برای اجرای یک جستار، ابتدا مجموعه ای بهینه از نمونه (ها) را برای پاسخگویی به صحت یا محدودیت های زمانی پاسخ انتخاب می کنیم. چنین نمونه (هایی) با استفاده از ترکیبی از آمار از پیش محاسبه شده و با اجرای پویای جستار بر روی نمونه های کوچک تر و تخمین گزینندگی و پیچیدگی جستار انتخاب شده اند. این برآورد به بهینه ساز جستار در انتخاب یک برنامه اجرا(execution plan) و همچنین «بهترین» نمونه (ها) برای اجرای جستار کمک می کند- یعنی به شخص (اشخاص) کمک می کند تا خطا یا محدودیت های زمانی پاسخ کاربر را جبران نمایند.

2.3. یک مثال

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.

شکل 2: مثال نشان دهنده نمونه هایی از یک جدول پنج ستونه و حجم کار یک جستار مشخص می باشد

شکل 2 مجموعه ای از قالب های جستار و فراوانی نسبی شان را نشان می دهد. BlinkDB ، با توجه به این قالب ها و بودجه ذخیره سازی، بر اساس قالب های جستار و آمار مربوط به داده ها چندین نمونه ایجاد نمود. این نمونه ها در گروه های نمونه ای سازماندهی شدند که در آن هر گروه شامل نمونه های متعددی از دانه بندی های (granularities) مختلف می باشد. در مثال ما،BlinkDB تصمیم گرفت تا دو گروه نمونه از نمونه های طبقه بندی شده ایجاد نماید: یکی شهر(City) و دیگرب در (OS، URL).

برای هر جستار، BlinkDB گروه نمونه مناسب و نمونه ای با وضوح مناسب برای پاسخ به جستار انتخاب می کند. به طور کلی، ستون (ها) در بند (های) WHERE/GROUP BY  جستار نمی توانند دقیقاً با همه نمونه های طبقه بندی شده موجود مطابقت یابند. BlinkDB  پیرامون این مشکل، جستار کوچکترین تفکیک پذیری گروه های نمونه در دسترس را اجرا نمود و از این نتایج برای انتخاب نمونه مناسب استفاده کرد.

3. عملکرد 

در این بخش به طور خلاصه به بحث در مورد عملکرد BlinkDB در پارامترهای مختلف می پردازیم. مقایسه دقیق تر را می توان در منبع [4] یافت. تمام آزمایشات ما بر اساس 17 TB مسیر توزیع ناشناخته حجم کار با محتوی ویدئویی در دنیای واقعی و برگرفته از Conviva  می باشد. این داده ها در 100 نمونه بزرگEC2 جزء بندی شده اند و جستارهای ما مبتنی بر زیر مجموعه ای کوچک از مسیر جستار اصلی آنها می باشد. تمام داده ها حاوی حدود 5.5 میلیارد ردیف در یک جدول بزرگ واحد و 104 ستون بودند (مانند، شناسه مشتری(customer ID)، شهر، URL رسانه و غیره)

جهت مشاهده متن کامل، فایل ترجمه را دانلود نمایید.