الگوی LMAX Disruptor

مقدمه

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

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

در بخش بعد، مساله‌ی مدیریت ارتباط و مسیریابی بین نقاط مختلف شبکه‌ای مطرح و پاسخی عمومی به این مساله ارائه می‌شود. در بخش‌های دیگر، مشکلات مختلف این پاسخ عمومی بررسی و در نهایت به شرح الگوی Disruptor پرداخته می‌شود.

طراحی اولیه

در نگاه کلی، عمل‌کرد این نرم‌افزار بایستی به گونه‌ای باشد که از یک نقطه‌ی شبکه، بسته‌ای را دریافت و با توجه به منطق مسیریابی به نقطه‌ی بعدی ارسال کند. از این رو، می‌توان این ساختار را به شکل زیر تصور کرد:

طبق آن‌چه که در این شکل دیده می‌شود، تعدادی بسته به ترتیب وارد صف شده تا آماده‌ی مسیریابی شوند و به مقصدهای مطلوب ارسال شوند. پس استفاده از ساختار صف در تعامل مشترک با چند تولید کننده‌ی ورودی (نقطه ۳ و ۴) و مصرف کننده‌ی خروجی (نقطه ۱ و ۲) می‌تواند یک پاسخ به این مساله باشد. در اینجا نکته‌ای که باید به آن توجه کرد، هم‌زمانی در تولید و مصرف است.

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

در ادامه‌ی این بحث به بیان الگوی Disruptor پرداخته می‌شود که مشکل کارآیی یاد شده، یکی از چند فاکتوری است که در طراحی این الگو مورد توجه قرار گرفته است. این الگو (کتابخانه) که در گروه LMAX - شرکتی که با هدف مبادله‌ی مالی کارآ تاسیس شده است - توسعه داده شده است، یک ساختار داده‌ی صف حلقوی ارائه می‌دهد که در محیط‌های هم‌روند می‌تواند مورد استفاده قرار گیرد.

مسأله‌ی هم‌زمانی

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

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

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

طبق بررسی‌های انجام شده روی پردازنده‌ی Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz و اجرای ۵۰۰ میلیون عملیات جمع، تاخیرهای زیر به دست آمد:

همان‌طوری که از خروجی جدول بالا مشخص است، به کارگیری مکانیزم قفل منجر به ایجاد بیش‌ترین تأخیر در عملیات می‌شود. به صورت کلی، در مواجهه با مسأله هم‌زمانی، بهره‌گیری از روشی ایده‌آل است که در لحظه فقط یک نخ در حال نوشتن منبع مشترک باشد و باقی نخ‌ها در کمترین زمان ممکن از تغییرات منبع مشترک مطلع شوند. در پردازنده‌های مدرن، مطلع شدن نخ‌ها از تغییرات منبع مشترک با استفاده از دستورالعمل‌های Memory Barrier قابل انجام است که در سطوح بالاتر و در پیاده‌سازی Mutex و Semaphore از آن استفاده می‌شود.

خواندن از حافظه و نوشتن در آن

نکته‌ی پنهانی که در مسأله‌ی مطرح شده به ندرت مورد توجه قرار می‌گیرد، مسأله‌ی خواندن از حافظه و نوشتن در آن است. برای روشن‌تر شدن این مسأله، گریزی به مفهوم Cache Line در پردازنده می‌زنیم. پردازنده در تعامل با حافظه، هیچ‌گاه بلوکی به اندازه یک byte یا word را استفاده نمی‌کند و معمولاً از یک خط داده‌ای که بین ۳۲ تا ۲۵۶ بایت (معمولاً ۶۴ بایت) است، استفاده می‌کند.

در تعامل پردازنده و حافظه، زمانی اختلال در کارآیی پیش می‌آید که دو نخ بخواهند روی دو متغیری که در یک Cache Line قرار می‌گیرند، بنویسند. در این صورت تصادم در نوشتن پیش می‌آید. به این پدیده False Sharing می‌گویند. برای روشن‌تر شدن این مسأله، به آزمون زیر توجه کنید.

فرض کنید که در پردازنده‌ای با مشخصات Core i5 (I5-5257U) 2.7GHz، تعداد ۵۰۰ میلیون عملیات نوشتن را در فضای چند نخی (بین ۱ تا ۴ نخ) روی چند متغیر (بین ۱ تا ۴ متغیر) و در حالی‌که همه‌ی متغیرها در Cache Line های یکسان یا مختلف باشند، انجام دهیم. در این صورت خروجی زیر را خواهیم داشت.

برای حصول اطمینان از این که دو متغیر در یک Cache Line نیستند، یک کلاس تعریف کنید و متغیرهای خود را در آن جای دهید و کلاس را به نحوی پر کنید که مضرب صحیحی از اندازه Cache Line باشد. برای مثال، اگر یک داده‌ی ۴ بایتی (long) در جاوا داشته باشیم، در این صورت ساختاری مشابه زیر خواهیم داشت.

public final static class ContentedLong {
    public volatile long value = 0L;
    private volatile long p1, p2, p3, p4, p5, p6, p7; // not-used (padding)
}

همچین شما می‌توانید از نشانه‌ی Contended در جاوا استفاده کنید که کدتان به شکل زیر در خواهد آمد:

public final static class ContentedLong  {
    @sun.misc.Contended
    public volatile long value = 0L;
}

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

مشکلات استفاده از صف

مجدد به پاسخ مطرح شده برای مسأله‌ی ابتدایی برمی‌گردیم. استفاده از صف برای کنترل ترافیک ورودی و خروجی دارای چند مشکل جدی است که در ادامه به شرح آن‌ها می‌پردازیم.

- عموما برای ایجاد صف از ساختار داده‌ی لیست پیوندی یا آرایه استفاده می‌شود. اگر بیشینه طول صف نامحدود باشد، در این صورت به ازای هر ورودی، یک نمونه از داده‌ی صف ساخته و به آن اضافه می‌شود. حال اگر نرخ ورودی نسبت به نرخ خروجی بیش‌تر باشد، در این صورت برنامه دچار کمبود حافظه و شکست می‌شود. از این رو، بایستی اندازه‌ی صف محدود شود. (استفاده از آرایه یا حافظه با تضمین اندازه‌ی مشخص)

- پیاده‌سازی صف نیازمند رفع تصادم نوشتن در ابتدا، انتها و طول صف است. به صورت کلی، با توجه به نرخ تولید یا مصرف، در اغلب اوقات صف‌ها در وضعیت نسبتاً پر یا نسبتاً خالی هستند که این موضوع منجر به افزایش میزان تصادم می‌شود.

- در زبان‌های مبتنی بر بازیافت حافظه (مانند جاوا)، ساختار داده‌ی صف جزو منابع اصلی تولید اشیای بازیافتی در نرم‌افزار می‌باشند.

الگوی LMAX Disruptor

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

تخصیص حافظه

همان‌طوری که اشاره شد، ناهماهنگی نرخ ورودی به صف و خروجی از آن، منجر به استفاده‌ی بیش از حد از حافظه می‌شود که خود همین موضوع باعث طولانی‌تر شدن فرآیند بازیابی حافظه (چه به صورت دستی و چه با فرآیند بازیافت حافظه) می‌شود. از این رو، در نرخ بالای ورودی و خروجی روش مناسبی به نظر نمی‌رسد. همچنین در الگوریتم‌های بازیافت حافظه مانند CMS / G1، چون یک شئ چند نسل باید از ساخته شدن آن بگذرد تا بازیافت شود، از این رو هزینه‌ی جابه‌جایی شئ بین نسل‌های جدید و قدیم طولانی می‌شود و منجر به تأخیر در عمل‌کرد نرم‌افزار و افزایش زمان Stop the World بازیافت حافظه می‌شود.

در Disruptor، یک بافر حلقوی (با پیاده‌سازی آرایه محدود) در نظر گرفته شده است. قبل از استفاده از این ساختار داده، تمام حافظه‌ی مورد نیاز این بافر حلقوی تخصیص می‌یابد، بنابراین قابلیت استفاده مجدد دارد. به کارگیری آرایه‌ی محدود و تخصیص حافظه در همان ابتدا، منجر به نزدیک به صفر شدن زمان GC در زبان‌های با قابلیت بازیافت حافظه می‌شود.

نکته‌ی بعدی در استفاده از آرایه (حافظه ترتیبی) به جای لیست پیوندی، در نحوه‌ی تعامل پردازنده در زمان خواندن این حافظه است. در دسترسی پردازنده به اولین خانه‌ی آرایه، خانه‌های بعدی آرایه نیز به حافظه‌ی نهان پردازنده انتقال می‌یابند، از این رو سرعت دسترسی به باقی خانه‌ها به مراتب سریع‌تر و کارآمدتر خواهد بود. در حالی‌که این موضوع به دلیل فاصله دار بودن خانه‌های لیست پیوندی امکان‌پذیر نیست.

تصادم

در صف‌های محدود همواره تصادم در زمان نوشتن در صف (ابتدای صف) و خواندن از صف (انتهای صف) وجود دارد. اگر فضای مسأله به شکلی است که نیاز به یک تولید کننده دارید، در این حالت تصادمی در ابتدای صف ایجاد نمی‌شود ولی برای فضای چند تولید کننده، تولید‌کننده‌ها بایستی بر سر گرفتن خانه‌ی بعدی که باید در آن بنویسند با هم بجنگند که برای حل این مشکل می‌توان از دستورالعمل CAS استفاده کرد.

زمانی‌که داده وارد صف شد، این بار نوبت به مصرف‌کننده‌ها می‌رسد تا ورودی جدید را تصاحب کنند. برای کنترل این تصادم، دو راه پیش رو داریم. راه اول، استفاده از دستورات صلب قفل کردن منابع و راه دوم، به کارگیری حلقه‌های شرطی است که تا زمانی که داده‌ی جدید از راه برسد، مصرف کننده در حلقه می‌ماند. اگر درگیر نگه‌داشتن پردازنده برای شما هزینه‌ی بالایی دارد، از این رو استفاده از روش اول توصیه می‌شود و در صورتی‌که تأخیر پایین برای شما اهمیت بیش‌تری دارد، استفاده از روش دوم مناسب‌تر خواهد بود. تمام این استراتژی‌ها در الگوی Disruptor پیاده‌سازی شده است.

ترتیب‌گذاری

ساختار ترتیبی روشی است که در Disruptor به کار گرفته شده است تا هم‌روندی مدیریت شود. در این ساختار دو ترتیب پایه‌ای برای خواندن و نوشتن وجود دارد. به شکل زیر توجه کنید:

زمانی‌که یک تولید‌کننده بخواهد در صف بنویسد، بایستی ابتدا مقدار بعدی ترتیب نوشتن را دریافت (claimedSequence) و متناظر با آن در یک خانه‌ی صف حلقوی بنویسد. بعد از آن‌که عملیات نوشتن تمام شد، بایستی مقدار Cursor به آخرین خانه‌ی قابل خواندن تغییر یابد. در صورتی که یک تولید‌کننده داشته باشیم، ترتیب نوشتن را می‌توان با یک متغیر ساده و به روزرسانی ترتیب خواندن را با یک حلقه‌ی درگیر (Busy Spin) مانند زیر مدیریت کرد.

long expectedSequence = claimedSequence – 1;
while (cursor != expectedSequence);
cursor = claimedSequence;

با توجه به موضوعیت ترتیب در نوشتن و خواندن، زمانی مقدار cursor به مقدار claimedSequence تغییر می‌‌کند که cursor در خانه‌ی ماقبل آن باشد. برای مثال، فرض کنید که دو تولید کننده داشته باشیم و تولید‌کننده‌ی اول ترتیب ۱ و تولید‌کننده‌ی دوم ترتیب ۲ را گرفته باشند. در این صورت ابتدا بایستی تولید‌کننده‌ی ۱ مقدار cursor را به روز کند و سپس تولید‌کننده‌ی ۲ (حتی اگر تولید‌کننده‌ی دوم زودتر کارش را به اتمام برساند.)

اثر دسته‌ای

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

گراف وابستگی

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

بررسی کارآیی

برای بررسی کارآیی این روش، آزمایشی ترتیب دیده شد که در آن ۵۰ میلیون پیام در فاصله‌های زمانی ثابت (۱ میلی‌ثانیه) به صف حلقوی و به صورت مشابه در ArrayBlockingQueue تزریق شد. برای این آزمایش محیطی با پردازنده Core-i7 2720QM 2.2GHz، سیستم عامل Ubuntu 11.04 و نسخه‌ی ۱.۶.۰.۲۵ جاوا در نظر گرفته شد. طبق خروجی به دست آمده، میزان تاخیر ایجاد شده در این صف حلقوی حدود ۵۲ نانوثانیه و برای ArrayBlockingQueue به ۳۲۷۵۷ نانوثانیه رسید و دلیل این اختلاف، استفاده از روش‌های معمول مدیریت هم‌روندی (مانند قفل کردن منابع) بود.

جمع‌بندی

در این مقاله به معرفی ساختار داده‌ای برای مدیریت مؤثر تعامل بین تولید کننده و مصرف کننده‌ی پیغام‌ها و رویدادها پرداخته شد. این ساختار داده که به الگوی Disruptor معروف است، برای رفع مشکلات ناشی از استفاده از صف‌های معمول برای ذخیره ورودی یا خروجی داده طراحی شده است. از نکات طراحی دیده شده در این الگو می‌توان به استفاده از صف حلقوی به جای صف خطی نامحدود، تخصیص حافظه در زمان ساخت صف، جلوگیری از ایجاد پدیده False Sharing، استفاده از حلقه‌ی درگیر به جای روال‌های رایج هم‌روندی و ترتیب‌گذاری در نوشتن و خواندن هم‌روند در صف، بدون استفاده از روال‌های صلب هم‌روندی اشاره کرد.

طبق آزمون طراحی شده، تاخیر ایجاد شده بین تولید و مصرف داده در این الگو در مقایسه با ساختارهای مرسوم (پیاده‌سازی ArrayBlockingQueue) بسیار پایین و حدودا ۱/۱۰۰۰ شد. پیکربندی درست این الگو در محیط‌هایی که دغدغه‌ی جابه‌جایی داده بین ماژول‌ های مختلف داخلی وجود دارد، می‌تواند منجر به کاهش هزینه‌ی زمانی شود.

منابع

• https://lmax-exchange.github.io/disruptor/disruptor.html
• http://robsjava.blogspot.ru/2014/03/what-is-false-sharing.html
• https://en.wikipedia.org/wiki/Compare-and-swap
• https://shipilev.net/talks/jvmls-July2013-contended.pdf
• https://martinfowler.com/articles/lmax.html
• https://www.f5.com
• https://stackoverflow.com/a/12065801/860721