یکی از اولین توانایی‌هایی که یک برنامه‌نویس فرا می‌گیرد، توانایی حل مساله است. از حل مسایل ساده تا مسایل بسیار پیچیده. اما چیزی که در این‌جا می‌خوام مطرح کنم حل مسایل بسیار ساده است که در نگاه اول، بسیار بدیهی و آسان به نظر می‌رسند ولی در عمل و در شرایط خاص، حل آن‌ها بسیار سخت و مشکل خواهد بود و برنامه‌نویسان باید بتوانند از پس این مسایل بربیان.
منظورم از مسایل ساده، مسایلی از این دست است:
و یا مسایل ساده‌ی دیگری از این جنس.
حل این مسایل بسیار ساده در بعضی شرایط بسیار سخت می‌شود.
در حل مسایلِ دنیای واقعی، ممکن است تمامی این شرایط یا بعضی از آن‌ها وجود داشته باشند و وجود همین شرایط باعث سخت شدن حل مسایل ساده‌ای خواهد شد که گفتم. وجود این شرایط همان چیزیه که ما با عنوان Big Data یا کلان داده می‌شناسیم.
داده‌ها از همه جا سرازیر می‌شوند، از شبکه‌های مجازی، از سنسورها، از تراکنش‌های مالی و .... از طرفی هم شرکت‌ها می‌خواهند که از داده‌ها سر در بیارن و از آن‌ها ارزش تولید کنند. این عوامل باعث رشد بسیار سریعِ بازارِ نرم‌افزارهای مرتبط با کلان داده شده است و به عنوان یک برنامه‌نویس در این بازار باید الگوریتم‌ها و داده‌ساختارهای مورد نیاز برای حل این مسایل را فرا بگیریم.
فرض کنید برنامه‌نویس یک مرورگر هستم، مثلا گوگل کروم! و قراره یک امکان به مرورگر اضافه کنم که از ورود به سایت‌های مشکوک جلوگیری کنه. به عبارت دیگه یک لیست چند میلیونی (معمولا بیش از ۲ میلیون) از آدرس‌های مربوط به این سایت‌ها دارم و برای هر آدرسی که کاربر در نوار آدرس مرورگر وارد می‌کنه، برنامه باید در این لیست چند میلیونی جستجو کنه و در صورتی که در این لیست وجود داشته باشد به کاربر اخطار بده. آیا برای این کار می‌توانم تمامی آدرس‌ها را در حافظه نگهداری کنم و به ازای هر درخواست در بین آن‌ها جستجو کنم؟
یا مثلا برای همین مرورگر، لیستی از تمامی رمزعبورهای لو رفته دارم (معمولا در حد چند میلیارد) و می‌خواهم در زمان‌هایی که کاربر، در سایتی رمز عبور وارد می‌کند، با این لیست مقایسه شود و در صورت استفاده از این رمز عبورها به کاربر اخطار داده شود. آیا برای این کار می‌توانم تمام رمزعبورها را در حافظه نگهداری کنم و در هر ورودِ رمزعبوری، در این لیست میلیاردی جستجو کنم؟ اصلا کار درستی است که پسور‌دها به صورت خام ذخیره شوند؟
فرض کنید که برنامه نویس سایت Medium یا ویرگول هستم! و قرار است که به هر کاربر چندین مقاله برای مطالعه پیشنهاد بدم، ولی می‌خوام مطمئن باشم که کاربر این مقاله را قبلا مطالعه نکرده باشه. به عبارت دیگر بعد از اینکه به کمک الگوریتم‌های توصیه‌گر، مجموعه‌ای از مقاله‌ها را برای کاربر ایجاد کردم، مقاله‌هایی که قبلا مطالعه کرده را از آن حذف کنم. بر اساس توئیت ویرگول در سال ۹۸ بیش از ۱۸ میلیون کاربر از ویرگول استفاده کرده‌اند. آیا برای این کار می‌توانم مقاله‌هایی که هر کاربر مطالعه کرده را در دیتابیس ذخیره کنم و برای حذف مقاله‌های قبلا خوانده شده از این دیتابیس استفاده کنم؟
فرض کنید من برنامه نویس Akamai یا ابرآروان هستم! و قرار است که الگوریتمی برای مسیردهی درخواست‌ها ایجاد کنم به طوری که درخواست‌ها به کَش سروری مسیردهی شوند که پاسخ این درخواست در آن وجود دارد، و برای این کار باید تمامی کَش سرورها از اطلاعات کَش شده در دیگر کَش سرورها اطلاع داشته باشند (Cache Sharing)، آیا درست است که برای این کار، هر کَش سرور، آدرس درخواست‌هایی را که کَش کرده است را به تمامی کَش‌سرورها ارسال کند؟
فرض کنید من برنامه نویس سامانه سهام عدالت هستم!! و قرار است که وب‌سایتی راه‌اندازی کنم که ۸۰ میلیون ایرانی جستجو کنند که آیا سهام عدالت دارند یا نه. آیا راه درستیه که به ازای هر درخواست من در دیتابیس چند ده میلیونی دارندگان سهام عدالت جستجو کنم؟
فرض کنید من برنامه نویس Fortigate یا یک شرکت ایرانی در این زمینه هستم! و قرار است بر روی یک پهنای باند ۱۰ گیگابیت در ثانیه، تمامی بسته‌ها (Packets) را بررسی کنم و لیستی از آی‌پی‌های پرتکرار بسازم. آیا می‌توانم به ازای هر بسته، در لیست آی‌پی‌ها جستجو کنم و شمارنده این آی‌پی را افزایش بدهم و در انتها با مرتب کردن تمامی این لیست، آی‌پی‌های پرتکرار را بسازم؟
فرض کنید من برنامه نویس توییتر هستم! و قرار است قسمت هشتگ‌های ترند شده را بسازم. به عبارت دیگر به ازای هر توییتی که می‌شود، هشتگ‌ها را استخراج کنم و در لیست احتمالا چند میلیاردی آن هشتگ را پیدا کنم و شمارنده‌اش را افزایش بدهم و هر چند دقیقه این لیست را مرتب کنم و هشتگ‌های ترند شده را بسازم. البته قرار است که این کار را به تفکیک برای ۱۰۰ کشور مختلط هم انجام دهم! آیا این راه درستی است؟
خوب فکر کنم مثال‌ها کافی هستند، برای اینکه نشان دهند که حل مسایل راحت در تولید سرویس‌ها و محصولات واقعی به راحتی امکان پذیر نیستند.
یکی از راه‌کارها برای حل این مسایل در دنیای واقعی استفاده از داده‌ساختارهای احتمالاتی است. داده‌ساختارهایی که برخی از آن‌ها در یکی دو سال گذشته معرفی شده‌اند و صد البته در سال‌های آینده می‌توانیم منتظر داده‌ساختارهای بهتری هم باشیم.
داده ساختارهای احتمالاتی، مانند دیگر داده‌ساختارها جواب قطعی نمی‌دهند و با یک احتمال قابل محاسبه‌ای می‌توان خطاهای احتمالی را تخمین زد و خوشبختانه خطاها و کمبودهای این داده‌ساختارها به واسطه حافظه کمی که اشغال می‌کنند، زمان پرس‌وجوی ثابتی که دارند و مقیاس پذیری آن‌ها قابل چشم پوشی هستند.
به عنوان مثال به کمک فیلتر کوکو (Cuckoo Filter) که یک داده‌ساختار احتمالاتی برای حل مساله عضویت (membership) در یک مجموعه است، برای پردازش یک میلیارد اِلِمان مجزا به کمی کمتر از یک گیگابایت حافظه نیاز دارد، پیچیدگی زمانی حذف و اضافه و جستجو O(1) است.
آیا خطا در داده‌ساختار قابل چشم پوشی است؟ در بسیاری از موارد بله، قابل چشم پوشی‌است، به عنوان نمونه داده‌ساختارهایی که برای حل مساله عضویت وجود دارند، مانند فیلتر کوکو، یا فیلتر بلوم؛ دارای خطای «مثبت کاذب» (False-Positive) هستند ولی خطای «منفی کاذب» ندارند.
به عنوان مثال، برای حل رمزعبورهای لو رفته، می‌توانیم از فیلتر بلوم استفاده کنیم به صورتی که فقط ۱ درصد خطای «مثبت کاذب» داشته باشد. یعنی ۱ درصد احتمال دارد رمزعبوری را لو رفته حساب کند در صورتی که رمزعبور امنی است و هیچ خطایی در شناسایی رمزعبوری که لو رفته است یعنی خطای «منفی کاذب» ندارد و در یک مرورگر این خطا قابل چشم‌پوشی است.
در داده‌ساختارهای احتمالاتی می‌توان، احتمال وقوع خطا را با بالابردن فضای اشغالی و بیشتر کردن پردازش کمتر کرد و به عبارتی قابل تنظیم است. به عنوان نمونه می‌توانید ماشین حساب فیلتر بلوم را ببینید.
پایه و اساس تمامی داده‌ساختارهای احتمالاتی توابع درهم‌ساز یا همان توابع هَش (Hash Functions) است.
توابع درهم‌سازی در دو دسته قرار می‌گیرند:
دسته اول برای استفاده در حوزه امنیت و رمزنگاری کاربرد دارند و معمولا به خاطر ویژگی‌هایی که دارند سرعت پردازشی کمتری به نسبت توابع درهم‌ساز دسته دوم دارند. به عنوان مثال SHA1-32 توانایی پردازش تقریبا ۳۰۰ مگابایت در ثانیه را دارد ولی MurMurHash3 توانایی پردازش نزدیک به ۳ گیگابایت در ثانیه، یا xxHash قدرت پردازشی نزدیک به 5.5 گیگابایت در ثانیه را دارد.
همانطور که حدس زده‌اید، در داده‌ساختارهای احتمالاتی از توابع درهم‌ساز غیر رمزنگارانه استفاده می‌شود که نرخ برخورد ( Collision Rate) کم و سرعت بسیار بالا دارند.
یکی از پیاده‌سازی‌های داده‌ساختارهای احتمالاتی که البته متعلق به نویسنده همین مطلب هم هست :-) در گیت‌هاب (github.com/zaghaghi/pdstl) قابل دسترس است. البته پیاده‌سازی‌های دیگری نیز به صورت متن‌باز وجود دارد ولی سعی شده و خواهد شد که در این پیاده‌سازی تقریبا بیشتر داده‌ساختارهای احتمالاتی به صورت یکجا و یک شکل پیاده‌سازی شود.
به عنوان مثال برای استفاده از فیلتر بلوم (Bloom Filter) به کمک کتابخانه PDSTL می‌توان به شکل زیر عمل کرد.
#include <membership/bloom_filter.h> #include <vector> #include <string> #include <iostream> int main() { // Read all urls from file or database into urls std::vector<std::string> urls; // Define bloom filter with 11 hash functions and 16M memory bits bloom_filter<11, 16000000> url_bloom_filter; std::for_each(urls.begin(), urls.end(), [&url_bloom_filter](auto& item) { // Insert items into bloom filter url_bloom_filter.insert(item); }); // Check that bloom filter contains an item or not if (url_bloom_filter.contains("https://gmail.com")) { std::cout << "FOUND!!!!!" << std::endl; } else { std::cout << "NOT FOUND" << std::endl; } }
یکی از مراجعی که برای خواندن در مورد این داده‌ساختارها وجود دارد، ویکی‌پدیا است. همچنین بهترین مرجع خود مقالات داده‌ساختارهاست و البته کتابی در سال ۲۰۱۹ منتشر شده که این داده‌ساختارها را یکجا جمع‌آوری کرده:
Probabilistic Data Structures and Algorithms for Big Data Applications by Andrii Gakhov, 2019, ISBN: 978-3748190486 (paperback) ASIN: B07MYKTY8W (e-book)
