مقدمه‌ای بر ساختمان‌داده‌های Lock-Free

بعد از چند ماه که از فضای سی++ دور بودم و باعث شد که بخشی از مطالعاتم رو فراموش کنم، امروز شروع کردم کتاب Concurrency in Action رو از ابتدای فصل ۷ دوباره خوندن(عجیبه که بعضی جاهاش رو خوب نمیفهمم! قبلا میفهمیدم!). در این پست راجع به چیستی و چراییِ ساختمان‌داده‌های Lock Free صحبت می‌کنم و باهمدیگه ویژگی‌های این ساختمان‌داده‌ها رو بررسی می‌کنیم.

فصل قبل کتاب - که من خلاصه‌ش رو ننوشتم - راجع به طراحی و پیاده‌سازی ساختمان‌داده‌های Concurrent با استفاده از Lock و Mutexها بود. میوتکس‌ها مکانیزم‌های قوی‌ای برای حفظ کردن ایمنی و صحت دسترسی به ساختمان‌داده‌ها و جلوگیری از race conditionها هستن. نکتهٔ دیگه‌ای که راجع به میوتکس‌ها وجود داره اینه که فهم نحوهٔ کارکدشون خیلی راحت‌ و سرراست هست. البته میوتکس‌ها هم مشکلات مربوط به خودشون رو (مثل Deadlock و حفظ concurrency) دارند.

بنابراین به صورت کلی میشه گفت که اگر ما ساختمان‌داده‌ای بنویسیم که مشکلات یادشده رو نداشته باشه، یک ساختمان‌دادهٔ Lock-Free ایجاد کردیم. اما ساختن این چنین ساختارهایی راحت نیست. معمولا فهم و دیباگ این ساختمان‌داده‌ها سخته و شرایطی که ممکنه باعث بشن طراحی ما fail بشه ممکنه خیلی خیلی نادر باشن و کم پیش بیان(ولی دقیقا موقعی که داریم نرم‌افزار رو برای سرمایه‌گذار دمو می‌کنیم ایجاد بشن!).

توی این پست در اصل راجع به این صحبت می‌کنیم که اصلا یک ساختمان‌دادهٔ lock-free یعنی چی و چرا باید از این ساختمان‌داده‌ها استفاده کنیم.

چیستی و تعریف

به الگوریتم‌ها و ساختمان‌داده‌هایی که از میوتکس‌ها، condition variableها و futureها برای همگام‌سازی(synchronization) داده‌ها استفاده می‌کنند میگن الگوریتم‌ها یا ساختمان‌داده‌های Blocking. این اسم شامل توابعی از کتابخونه‌ها هم میشن که صدا زدنشون باعث میشه اجرای یک ترد suspend بشه تا زمانی که یک ترد‌ِ دیگه کار خودش رو انجام بده. دلیل اصلی که این توابع هم blocking خونده میشن اینه که ترد مورد نظر نمیتونه کار خودش رو ادامه بده تا زمانی که اون block برداشته بشه. معمولا سیستم‌عامل یک تردی بلاک شده رو خودش به صورت اتوماتیک suspend میکنه تا منابع اون ترد رو به یک ترد دیگه که میتونه کارش رو ادامه بده اختصاص بده تا زمانی که اون بلاک برداشته بشه. این «برداشتن بلاک» میتونه آنلاک کردن یک میوتکس باشه، میتونه notify کردن یک condition variable باشه یا ready کردن یک future باشه.

حالا به ساختمان‌داده‌ها و الگوریتم‌هایی که از توابع blocking استفاده نمی‌کنند میگن nonblocking. نکته مهم اینکه یک ساختمانم داده میتونه nonblocking باشه ولی lock-free نباشه!

انواع ساختمان‌داده‌های nonblocking

توی این پست ما یک mutex ساده و ابتدایی(درواقع یک spin lock) رو با استفاده از std::atomic_flag پیاده‌سازی کردیم:

class spinlock_mutex
{
    std::atomic_flag flag;

public:
    spinlock_mutex():
    flag(ATOMIC_FLAG_INIT)
    {}
    void lock()
    {
    	while(flag.test_and_set(std::memory_order_acquire));
    }
    void unlock()
    {
    	flag.clear(std::memory_order_release);
	}
};

مباحث پیچیده‌تر در memory ordering

حالا که مباحث ابتدایی ترتیب‌های حافظه (memory ordering) رو باهم دیدیم، وقت اینه که یکم مسائل پیچیده‌تری رو بررسی کنیم.

وبلاگ سیْدپولرمور دانه‌کش

همونطور که می‌بینیم، این کد هیچ تابع blockingای رو صدا نمیزنه. تابع lock()‎ صرفا یک حلقه روی تابع test_and_set()‎ هست(حالا مشخص شد چرا اسمش هست spin lock؟ :) ). از اونجایی که توی این کد هیچ عامل blockingای وجود نداره که بخواد ترد رو suspend بکنه، این یک کد nonblocking هست و کدی که از این lock برای جلوگیری از race condition استفاده میکنه هم nonblocking هست. کدها nonblocking هستند اما lock-free نیستند چراکه همچنان یک میوتکس و lock داریم که میتونه در یک لحظه فقط توسط یک ترد قفل بشه. بنابراین صرفا دونستن اینکه آیا یک کدی nonblocking هست یا نه،‌ برای ارزیابی اون کد کافی نیست و ما به المان‌های دیگه‌ای هم نیاز داریم. برخی از مهم‌ترینِ اون المان‌ها اینها هستند:

• Obstruction-Free: کدی هست که در اون فقط اگر همهٔ تردها متوقف شده باشن و یک ترد بخواد شروع به کار بکنه، مشکلی برای ادامهٔ عملیاتش نداره.
• Lock-Free: به کدی گفته میشه که طی اون زمانی که چند ترد دارن روی یک ساختمان داده عملیات انجام میدن، «یکی از اون تردها» میتونه بعد از تعدادی عملیات «متناهی» میتونه عملیات خودش رو به شکل کامل انجام بده.
• Wait-Free:‌ بهترین چیزی هست که میشه بهش رسید. به ساختمان‌داده‌هایی گفته میشه که در اونها «چندین ترد» میتونن به صورت همزمان و بدون توجه به مابقی تردها کار خودشون رو در قالب تعدادی عملیات متناهی انجام بدن.

الگوریتم‌های obstruction-free زیاد بدردبخور نیستن و معمولا برای نشون دادن عدم پیاده‌سازی صحیح یک الگوریتم Lock-free ‌استفاده میشن.

ساختمان‌داده‌های Lock-Free

اگر یک ساختمان‌داده می‌خواد که در دسته‌بندیِ Lock-Free قرار بگیره باید حداقل این دوتا ویژگی رو داشته باشه:

۱- اون ساختمان‌داده باید قابلیت این رو داشته باشه که تعداد بیشتر از یک ترد بتونن به صورت همزمان به ساختمان‌داده دسترسی پیدا کنن.

۲- اگر در حین دسترسی همزمان تردها، یکی از اون تردها توسط scheduler سیستم‌عامل suspend شد، نباید اخلالی در کار تردِ دیگه بوجود بیاد و تردِ دیگه باید بتونه کارش تموم کنه بدون اینکه منتظر تردِ suspendشده بمونه.

یکی از چیزهایی که موقع طراحی و پیاده‌سازیِ ساختمان‌داده‌های lock-free باید بهش توجه کنیم، استفاده از عملیات‌های compare-exchange هست که معمولا همراه با حلقه‌های تکرار استفاده می‌شن. دلیل استفاده از عملیات‌های compare-exchange این هست که ممکنه در حین رسیدن به این عملیات‌ها، تردِ دیگه‌ای بیاد و دادهٔ موردنظر ما رو تغییر بدن؛ با استفاده از عملیات‌های compare-exchange میتونیم متوجه این تغییرات بشیم و با استفاده از حلقه‌های تکرار، عملیات‌ compare-exchange(یا عملیات‌های احتمالیِ قبلش) رو تکرار کنیم. نکتهٔ مهم این هست که این «تکرار» که انجام میشه اگر متناهی باشه، همچنان در زمره ساختمان‌داده‌های lock-free قرار داریم. اما اگر حتی با suspend شدن دیگر تردها همچنان این تکرار وجود داشته باشه، انگار عملا یک spinlock ایجاد کردیم که nonblocking هست ولی lock-free نیست!

ساختمان‌داده‌های wait-free

یکی از مشکلات ساختمان‌داده‌های lock-free این هست که یکی از تردها ممکنه دچار مشکل starvation یا گرسنگی بشه. یعنی چی؟ فرض کنیم دوتا ترد داریم که از یک متغییر اتمیک مشترک استفاده میکنن. حالا فرض کنیم زمانی که ترد اول میخواد یک عملیات compare-exchange رو انجام بده، ترد دوم یک تغییری در اون متغییر اتمیک ایجاد میکنه و کار خودش رو پیش میبره درحالی که ترد اول باید عملیات‌های خودش رو تکرار کنه(توی حلقهٔ تکراری که بالاتر ازش گفتم). حالا اگر این بدشانسی توی زمان‌بندیِ استفاده از اون متغییر اتمیک بخواد تکرار بشه، ترد اولی همش باید منتظر بمونه که یه فرصتی پیش بیاد تا کار خودش رو هم بتونه پیش ببره.

ساختمان‌داده‌های wait-free اومدن تا این مشکل رو رفع کنن. یک ساختمان‌دادهٔ wait-free، ساختمان‌داده‌ای هست که هر تردی که بهش دسترسی پیدا می‌کنه میتونه عملیات مورد نظر خودش رو طی یک‌سری مراحل متناهی انجام بده. این یعنی الگوریتم‌هایی که در اونها شرایطی ایجاد میشه که بخاطر اختلال یک ترد با بقیه تردها مجبور میشه تا زمانی که کارش انجام نشده و تا بی‌نهایت عملیاتش رو تکرار کنه، جزء wait-freeها محسوب نمی‌شن.

نوشتن یک ساختمان‌دادهٔ wait-free بسیار مشکل هست و اون ساختمان‌داده باید حداقل این دو ویژگی رو داشته باشه:

• برای اینکه مطمئن بشیم هر ترد میتونه کارهای خودش رو در طی تعداد عملیات‌های متناهی انجام بده، باید مطمئن باشیم که هر عملیات به صورت یکجا(single-pass) انجام میشه.
• باید مطمئن باشیم که عملیات‌های موجود توی هر ترد، روی کار بقیهٔ تردها تغییری ایجاد نمیکنه که منجر به fail شدن کار اون ترد بشه.

به صورت کلی، با توجه به اینکه فهم و طراحی و پیاده‌سازیِ ساختمان‌داده‌ای lock-free یا wait-free بسیار سخت هست،‌ باید حتما دلایل بسیار محکمی برای نوشتن چنین ساختمان‌داده‌هایی داشته باشیم تا مطمئن باشیم هزینهٔ پیاده‌سازی چنین چیزهایی از فایده‌ش بیشتر نمیشه!

مزایا و معایب ساختمان‌داده‌های lock-free

اولین دلیل که باعث میشه بخوایم یک ساختمان دادهٔ lock-free داشته باشیم این هست که maximum concurrency رو افزایش بدیم و درواقع همزمانی بیشتری توی اجرای کدهامون داشته باشیم. زمانی که ما از ساختمان‌داده‌های lock-based استفاده می‌کنیم، همیشه این پتانسیل وجود داره که یک ترد بلاک بشه و منتظر ترد دیگه‌ای بمونه که داره کار خودش رو انجام میده(اساسا دلیل استفاده از lock هم همین هست خب!). با استفاده از ساختمان‌داده‌های lock-free، «بعضی تردها» در هر کلاک به پیش میرن(یعنی ممکنه بعضی‌ها نیاز داشته باشن که برگردن و دوباره تلاش کنن. بنابراین «به پیش» نمیرن). در ساختمان‌داده‌های wait-free، «همهٔ تردها» در هر کلاک پیش میرن و کاری به دیگر تردهایی که دارن اجرا میشن ندارن. این مورد آخر خب خیلی چیز خفنیه و طبیعیه که بخوایم چنین چیزی در نرم‌افزارهامون داشته باشیم. اما مسئله این هست که پیاده‌سازی و درواقع رسیدن به چنین طرح و پیاده‌سازی‌ای بسیار مشکل هست و احتمال اینکه در نهایت کدی بنویسیم که عملا یک spinlock هست خیلی زیاده :))

دومین دلیلی که میتونیم برای استفاده از ساختمان‌داده‌های lock-free داشته باشیم،‌ robustness یا پایداری(نمیدونم ترجمهٔ صحیحی هست یا خیر) هست. یعنی چی؟ اگر یک ترد که یک lock رو نگهداشته یکهو وسط کار ازبین بره، کل اون ساختمان داده‌ای که lock براش نگهداشته شده احتمالا به فنا میره اما چنین چیزی در ساختمان‌داده‌های lock-free بوجود نمیاد :)

از اونجایی که هیچ lockای توی ساختمان‌داده‌های lock-free وجود نداره، باید از یک راه جایگزین برای جلوگیری از data race استفاده کنیم: استفاده از متغییرها و عملیات‌های اتمیک! ولی تنها استفاده کردن از متغییرها یا عملیات‌های اتمیک برای جلوگیری از data race کافی نیست و ترتیب اعمال شدن و visible شدن تغییرات برای تردهای مختلف هم بسیار مهم هستند. در نتیجه چیزهای بیشتری وجود دارند که باید بهشون توجه کرد و در نتیجه، این ساختمان‌داده‌ها پیچیده‌تر هستند.

زمانی که ما از lock استفاده می‌کردیم، چیزی به اسم deadlock داشتیم که باید ازش جلوگیری می‌کردیم. اما حالا که دیگه خبری از lock نیست پس احتمالا دیگه راحت هستیم. خیر عزیز دلم، در ساختمان‌داده‌های lock-free مفهومی به نام live lock وجود داره. live lock زمانی بوجود میاد که دوتا ترد سعی میکنن که ساختمان‌داده رو تغییر بدن ولی هرکدومشون کاری میکنن که عملیاتِ تردِ دیگه fail بشه و نیاز داشته باشه که دوباره کارش رو انجام بده(همون حلقهٔ تکراری که بالاتر راجع بهش حرف زدیم). البته این مشکل مثل deadlock دائمی نمیمونه و در خیلی زود ازبین میره چراکه این تصادم بین تردها نیازمند این هست که scheduling تردها هربار خیلی دقیق شبیه به هم دربیاد که معمولا این اتفاق نمیوفته و در نهایت صرفا پرفورمنس رو به صورت نقطه‌ای و short-term کاهش میدن. در نهایت چیزی هست که باید بهش توجه بشه.

البته خوبه بدونیم که در ساختمان‌داده‌های wait-free چنین مشکلی بوجود نمیاد چراکه در این ساختمان‌داده‌ها ما یک کرانِ بالا داریم که جلوی تکرار بیش از حد یک مجموعه از عملیات‌ها رو میگیره. اما این خودش پیاده‌سازی و طراحی ساختمان‌داده رو پیچیده‌تر میکنه و ممکنه به صورت کلی پرفورمنس بدتری هم داشته باشه اتفاقا :) (چون معمولا نیاز هست برای یک عملیات مشابه، مراحل بیشتری طی بشه).

نکات دیگه‌ای هم برای توجه بهشون  وجود داره که باعث میشه گزینهٔ پیاده‌سازی و استفاده از ساختمان‌داده‌های lock-free رو با دقت بیشتری انتخاب بکنیم. مثلا،‌ متغییرهای اتمیک نسبت به متغییرهای معمولی خیلی کندتر هستند و تعداد این متغییرها در ساختمان‌داده‌های lock-free بیشتر از lock-basedها هست. یا مثلا بحث cache ping-pong که زمانی بوجود میاد که چندین ترد سعی میکنن که به یک متغییر اتمیک دسترسی پیدا کنند و باعث میشن که پرفورمنس به شکل بسیار بسیار بدی افت بکنه.

نتیجهٔ نسبتاً کلی

به صورت کلی،‌ باید همهٔ جوانب استفاده از ساختمان‌داده‌های lock-free و lock-based رو بسنجیم و پرفورمنسشون رو در حالت‌های مختلف(مثلا میانگین زمان صبر کردن، زمان نهایی اجرا و ...) محاسبه کنیم تا بتونیم بهترین انتخاب رو داشته باشیم.

توی پستِ بعد(یا احتمالا پست‌های بعد، چون مطلب بعدی خیلی زیاده) راجع به پیاده‌سازی یک (Stack)استک lock-free و thread-safe صحبت می‌کنیم. خیلی مبحث چالشی‌ای خواهد بود! :)