ویرگول
ورودثبت نام
Kian
Kianفعال در مهندسی نرم‌افزار با اندکی تجربه از صنعت (عمدتا گوگل) و آکادمی (عمدتا اتلاف عمر). علاقمندم آموخته‌هامون رو رد و بدل کنیم.
Kian
Kian
خواندن ۷ دقیقه·۶ سال پیش

مساله‌های جالب از دنیای واقعی - الگوریتم / ML / علوم داده / سیستم‌های توزیع شده

تلاش می‌کنم چند نمونه از مساله‌های جالبی که استثنای این یادداشت بوده رو ساده‌سازی و قابل انتقال در چند خط کنم و به مرور به این یادداشت اضافه کنم. مساله‌های زیر جدا جدا نوشته شده و سپس به ویرگول منتقل شده‌اند و ارتباط یا نظم خاصی ندارند.

۱. کارکرد بهینه‌ی cache آفلاین (الگوریتم/‌بهینه‌سازی)

فرض کنید با کاوش در داده‌های تعامل کاربران با YouTube می‌خوایم از اون‌ها «الگو» دربیاریم و بر اساسش «الگوریتم» cache serverهای CDN گوگل رو بهبود بدیم. چه الگوریتمی؟‌ این که هر سرور تصمیم بگیره چه قطعه‌هایی از داده رو در دیسکش ذخیره کنه یا نکنه تا hit rateاش (درصد دفعه‌هایی که می‌تونه قطعه‌ی درخواستی رو از دیسک خودش و بدون مراجعه به بالادست بده) بیشینه بشه.

چه الگویی؟ مثلا دریابیم که قطعه‌های نخست ویدیوها با چه احتمال بیشتری از بقیه دانلود می‌شن یا این شیب افت احتمال با چی هم‌بستگی داره یا دریابیم درخواست‌ها برای یک قطعه چه قدر هم‌محلی زمانی دارند (به شکل موج می‌آن) و الی آخر. این‌ها البته در توییت نمی‌گنجه و موضوع امروز نیست.

پرسش اساسی که پیش از جوگیری و سرمایه‌گذاری روی این داده‌کاوی‌ها باید بپرسیم چیه؟ اینه که ته تهش به چی می‌رسیم؟ یعنی تحلیل کران بالا. مثلا اگر hit rateها الان حدود ۶۰٪ است، بیشترین hit rate ممکن اصلا چنده؟ همون ۶۵-۶۰٪ یا ۹۰٪؟

این، موضوع مساله‌ی ساده شده و خوش‌تعریف امروزمونه: فرض کنید تنها یک سرور داریم با ظرفیت N MB دیسک. ورودی، دنباله‌ای از درخواست‌هاست (دنباله‌ای از «شناسه‌ی قطعه‌ی درخواستی») و همه‌ی قطعه‌ها هم 1MB هستن. خروجی: برای هر درخواست، سرور باید تصمیم بگیره که {می‌خواد قطعه رو ذخیره کنه یا نه؛ اگر آره پس چه قطعه‌ای رو بیرون بندازه}. این تعریف کلاسیک یک cache است، فقط این‌جا گزینه‌ی cache نکردن هم داریم.

برای تحلیل کران بالا، کل مجموعه‌ی ورودی (دنباله‌ای از شناسه‌ها) رو داریم، یعنی عملا داریم تقلب می‌کنیم و برای انتخاب این که قطعه‌ی X رو در زمان T ذخیره کنیم/نکنیم یا قطعه‌ی Y رو بیرون بندازیم، همه‌ی درخواست‌هایی که در آینده برای X و Y می‌آن رو داریم در همون زمان T می‌بینیمشون. هدف هم همینه: اگر در دنیای واقعی می‌تونستیم فرضا با معجزه، آینده رو دقیق پیش‌بینی کنیم، کران بالای hit rate چه قدر می‌بود؟ یعنی با ورودی و خروجی گفته شده، بیشینه‌ی hit rate رو چه طور حساب کنیم؟

نسخه‌ی ساده نشده: cache نکردن در واقع HTTP 302 redirect کردنه لذا تصمیم سرور به ذخیره کردن یا نکردن، دو هزینه‌ی جداگانه C1 و C2 دارن. اون هزینه رو کمینه کنید، اگر علاقه‌مندید.

روشنه که اگر C1 و C2 یکسان باشن، کمینه کردن این هزینه معادل با بیشینه کردن hit rate است که گفته شد.

(همین مساله در توییتر: این‌جا)

۲. نگاشت شبکه‌های کاربران به محل‌های سرویس (الگوریتم/‌بهینه‌سازی)

باید شبکه‌های کاربران در دنیا را (مثلا هر IP subnet یک شبکه) به محل‌های سرویس (PoPهایمان) اختصاص دهیم. هر شبکه یک حجم ترافیکِ «نیاز» دارد و هر محل سرویس یک «ظرفیت». دادن شبکه‌ی X به محلY هزینه‌ی C_{X, Y} دارد. مثلا اگر Y نسبت به X محلی باشد هزینه صفر و اگر از مسیر peering باشد این هزینه احتمالا ناچیز و اگر ناچار به گذر از لینک‌های ترانزیت اینترنت باشد این هزینه بیشتر است. خلاصه C_{X, Y} را داریم (واحد: دلار بر واحد حجم ترافیک) و همچنین نیاز هر X و ظرفیت هر Y (واحد: حجم ترافیک).

نسخه‌ی نخست مساله: همین تخصیص با کمترین هزینه. نیاز X به کدام Y یا Yها با چه نسبتی برود؟ پس ورودی ما هست: V_Xها که نیازها هستن و S_Yها که ظرفیت‌ها هستن و C_{X, Y} که گفته شد. این مساله‌ی کلاسیکی‌ست و اگر از پیش می‌شناسید در نوشتن پاسخ درنگ کنید.

نسخه‌ی دوم مساله: لینک‌های peering ظرفیت مشخصی دارند. اگر مسیر چند X به چند Y از لینک مشترکی به ظرفیت W بگذرد، تنها تا سقف W قابل تخصیص است و برای باقی باید Yهای دیگری یافت. این که مسیر هر X به هر Y از چه لینک‌هایی می‌گذرد را داریم (معمولا یک لینک ولی اگر بیشتر باشد فرض کنید حجم به تساوی تقسیم می‌شود؛ بجویید ecmp). ظرفیت هر لینک را هم داریم (واحد: حجم ترافیک). پس ورودی اضافه‌ی ما نسبت به مساله‌ی نخست هست: مجموعه‌ای از N لینک و ظرفیت W_1 و ... و W_N برای آن‌ها، و همچنین این که مسیر هر X به Y از کدام لینک یا لینک‌ها رد می‌شود.

(همین مساله در توییتر: این‌جا)

۳. مدل‌سازی علامت‌های پیش‌گیرنده از تصادف (ML/علوم داده)

فرض کنید داده‌های تقاطع جاده‌ها با ریل‌های آهن را داریم: برای هر تقاطع، چه علامت‌های بازدارنده‌ای نصب بوده (چراغ چشمک‌زن، سرعت‌گیر، تابلوی خطر، …) و چند حادثه داشته. می‌خواهیم میزان بازدارندگی هر علامت نسبت به بقیه را اندازه بگیریم: یک مدل یادگیری می‌سازیم که وجود علامت‌های بازدارنده، featureها و تعداد حادثه‌ها، labelهای آن است، و با داده‌ها آموزشش می‌دهیم. سپس به مدل، ورودی {هیچ علامتی} و {علامت الف} داده و تفاوت خروجی (چند حادثه کمتر) را به عنوان بازدارندگی الف به دست می‌آوریم. مقاله‌اش هم چاپ شده. آیا این راه حل درست است؟ چرا؟

شفاف‌سازی: فرض کنید از مدل، دقت خوبی می‌گیریم، یعنی خطا روی داده‌ی آزمون (test data) پایین است. کمبود feature نداریم.

(همین مساله در توییتر: این‌جا)

پاسخ: همان‌طور که برخی دوستان به درستی اشاره کردند، راه حل فرضی ما در صورتی که مدلِ گفته شده غیرخطی / شبکه‌ی عصبی باشد (که در مقاله چنین بود)، نادرست است، چون با گرفتن تفاضل خروجی بین ورودی {هیچ علامت} و ورودی {علامت الف} داریم برداشت خطی می‌کنیم. اما اگر مدل خطی بود چه؟ دوستان به «تاثیر الف فقط در کنار بقیه‌ معنی دارد» اشاره کردند. دقت کنید این اشکال در صورت مدل خطی لزوما وارد نیست (و گفتیم که دقت مدل خوب است و مساله نیست). چه مدل خطی؟ مدلی که با منظم‌سازی L1 آموزش دهیم مثلا Lasso که خیلی خشن وزن‌ها را صفر می‌کند و مدل تُنک (sparse) می‌سازد. یعنی اگر الف به تنهایی قابلیت بازدارندگی داشت وزن مثلا ۱ و بقیه همگی ۰ می‌گیرند و اگر الف در کنار ب بازدارنده بود الف و ب وزن ۰/۵ می‌گیرند و چنین چیزی. یعنی وزنی که چنین مدل خشنی به الف بدهد---تفاضل خروجی مدل بین {هیچ علامت} و {علامت الف}---تخمین معقولی از «اثرگذاری الف» است.

۴. شهود از منظم‌سازی L1 و L2 (ML/علوم داده)

این پرسش کمی یادگیری ماشینی (MLای) ولی بیشتر علوم‌داده‌ای (data scienceای) است - رگرسیون خطی در آمار.

با این دو قابلیت آشنایید: منظم‌سازی L1، مدل را کوچک و تُنُک (sparse) می‌کند و L2، پایدار. مثلا بین سه گزینه‌ی {۰، ۱} و {۰/۲۵، ۰/۷۵} و {۰/۵، ۰/۵} برای وزن دو feature {الف، ب}، L2‌ گزینه‌ی سوم را برمی‌گزیند و شهودا روشن است چرا، ولی این که L1 گزینه‌ی نخست را، شهودا روشن نیست چون هر سه گزینه خطای L1 یکسان دارند. به نظر شما پس چرا منظم‌سازی L1 معمولا گزینه‌ی نخست را ترجیح می‌دهد؟ این شهود به ویژه برای یادگیری‌های خطی به درد می‌خورد - به درد بنده خورده وقتی مدل‌هایمان تُنُک نمی‌شدند.

(همین مساله در توییتر: این‌جا)

۵. توزیع بار برای بهینه‌سازی بهره‌گیری (سیستم توزیع شده)

زمینه: فصل ۱ از این یادداشت. سرویسی داریم برساخته از چند job، هر یک برساخته از تعدادی سرور (نمونه/instance). در پاسخ به درخواست‌ها، jobها یک‌دیگر را فراخوانی می‌کنند تا پاسخ آماده و پس فرستاده شود. یک سیستم توزیع بار برای ارتباط بین job الف و job ب طراحی کنید.

(پاسخ: این‌جا)

۶ و ۷. استقرار cache محاسباتی (سیستم توزیع شده و ML/علوم داده)

فرض کنید سرویسی داریم که هزاران/میلیون‌ها درخواست بر ثانیه گرفته و پاسخ می‌دهد. برای کنترل هزینه‌های سرسام‌آور پردازشی، پاسخ‌هایی که آماده کرده‌ایم را cache می‌کنیم (فرض کنید cache خودش یک job توزیع شده است) تا برای درخواست‌های مشابه، همان پاسخِ پیشین را برگردانیم. برای سادگی فرض کنید ظرفیت cache نامحدود ولی عمر (TTL) داده‌ها در cache تنها T دقیقه است. از این cache حدود ۵۰٪ hit rate می‌گیریم یعنی اگر cache نباشد بار پردازشی سیستم دو برابر می‌شود.

مساله‌ی ۶: فرض کنید سرویس ما در چند منطقه مستقر شده، و در هر منطقه مثلا در سه خوشه (cluster). هر خوشه، cache خودش را دارد. همچنین هر خوشه، ساز و کار کنترل بار دارد (مدیریت بار در سیستم‌های توزیع شده: این یادداشت). یعنی وقتی بار از سوی کاربران زیاد می‌شود و یکی از jobها به مرز ظرفیتش می‌رسد یعنی کل خوشه به مرز ظرفیتش رسیده (و معمولا خوشه‌های همسایه هم، چون بار بین خوشه‌های یک منطقه همگن توزیع می‌شود) و مثلا ظرف ۱ دقیقه تشخیص و واکنش نشان داده و بار اضافی را به منطقه‌های دیگر هدایت می‌کنیم. جنس بار با منطقه هم‌بستگی دارد، یعنی وقتی سرریز بار خوشه‌ی الف را به خوشه‌ی ب می‌فرستیم، برای cache خوشه‌ی ب کم و بیش غریبه‌اند و مثلا ۵ دقیقه طول می‌کشد تا جا بیفتند و cache به حالت ثابت (steady) برسد. حالت‌های خطا (failure mode) های این سیستم را تحلیل کنید و برایش راه حل پیشنهاد دهید.

مساله‌ی ۷: فرض کنید تنها یک منطقه داریم و سه خوشه، یعنی سه cache با فضای نامحدود و عمر (TTL) محدود T دقیقه برای داده. اگر cacheهای این خوشه‌ها را هم‌کاسه کنیم، یعنی یک سرویس کلی cache که هر سه خوشه با آن صحبت می‌کنند داشته باشیم، آیا hit rate تغییر می‌کند؟ اگر نه، چرا؟ اگر بله، چه اندازه؟ (تحلیل آماری).

نکته‌ی فرعی: چرا تحلیل آماری؟ رهیافت درست پیش از تخصیص نیرو و تعهد، انجام تحلیل‌های زود آشکار کننده‌ی شکست (fail fast) و تحلیل کران بالای فایده و چنین کارهایی‌ست. نخست تحلیل کم‌هزینه و نادقیق (مثلا تحلیل آماری با خودکار و کاغذ و spreadsheet)، سپس شاید تحلیل کمی پرهزینه‌تر (شبیه‌سازی) و ...

(همین مساله در توییتر و راهنمایی پاسخ: این‌جا)

۲
۰
Kian
Kian
فعال در مهندسی نرم‌افزار با اندکی تجربه از صنعت (عمدتا گوگل) و آکادمی (عمدتا اتلاف عمر). علاقمندم آموخته‌هامون رو رد و بدل کنیم.
شاید از این پست‌ها خوشتان بیاید