تایمرهای چرخ هش – انجمن DEV

معرفی

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

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

پیاده سازی

بیایید به نمونه ای از پیاده سازی در جاوا بپردازیم:

package de.frosner;

import java.util.*;
import java.util.concurrent.*;
import java.time.Duration;

public class HashedWheelTimer {
    private final Duration tickDuration;
    private final List<ConcurrentLinkedQueue<Timeout>> wheel;
    private volatile int wheelCursor = 0;

    public HashedWheelTimer(int wheelSize, Duration tickDuration) {
        this.tickDuration = tickDuration;
        this.wheel = new ArrayList<>(wheelSize);
        for (int i = 0; i < wheelSize; i++) {
            wheel.add(new ConcurrentLinkedQueue<>());
        }
        start();
    }

    public void newTimeout(Runnable task, Duration delay) {
        long ticks = delay.isZero() ? 0 : delay.plus(tickDuration).dividedBy(tickDuration);
        int stopIndex = (wheelCursor + (int)(ticks % wheel.size())) % wheel.size();
        wheel.get(stopIndex).add(new Timeout(task, ticks / wheel.size()));
    }

    private void start() {
        Executors.newSingleThreadScheduledExecutor().scheduleAtFixedRate(() -> {
            System.out.println("Tick " + wheelCursor);
            ConcurrentLinkedQueue<Timeout> bucket = wheel.get(wheelCursor);
            List<Timeout> pendingTimeouts = new ArrayList<>();
            Timeout timeout;
            while ((timeout = bucket.poll()) != null) {
                System.out.println("Processing task " + timeout.task + " with " + timeout.remainingRounds + " remaining rounds");
                if (timeout.remainingRounds <= 0) {
                    timeout.task.run();
                } else {
                    timeout.remainingRounds--;
                    pendingTimeouts.add(timeout);
                }
            }
            bucket.addAll(pendingTimeouts);
            wheelCursor = (wheelCursor + 1) % wheel.size();
        }, tickDuration.toMillis(), tickDuration.toMillis(), TimeUnit.MILLISECONDS);
    }

    private static class Timeout {
        final Runnable task;
        long remainingRounds;

        Timeout(Runnable task, long remainingRounds) {
            this.task = task;
            this.remainingRounds = remainingRounds;
        }
    }
}

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

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

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

یک تست JUnit می تواند به بررسی این موضوع کمک کند HashedWheelTimer مطابق انتظار عمل می کند. بیایید یک مورد آزمایشی ساده ایجاد کنیم که در آن یک کار را برای افزایش یک مقدار پس از یک تاخیر مشخص برنامه‌ریزی می‌کنیم:

package de.frosner;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
import java.time.Duration;
import java.util.concurrent.atomic.AtomicBoolean;

public class HashedWheelTimerTest {
    @Test
    public void testTimer() throws InterruptedException {
        HashedWheelTimer timer = new HashedWheelTimer(10, Duration.ofSeconds(1)); // Wheel size 10, tick duration 1s

        AtomicBoolean value1 = new AtomicBoolean(false);
        AtomicBoolean value2 = new AtomicBoolean(false);

        timer.newTimeout(() -> value1.set(true), Duration.ofSeconds(11));
        timer.newTimeout(() -> value2.set(true), Duration.ofSeconds(5));

        Thread.sleep(2000);
        assertFalse(value1.get());
        assertFalse(value2.get());
        Thread.sleep(2000);
        assertFalse(value1.get());
        assertFalse(value2.get());
        Thread.sleep(2000);
        assertFalse(value1.get());
        assertTrue(value2.get());
        Thread.sleep(2000);
        assertFalse(value1.get());
        assertTrue(value2.get());
        Thread.sleep(2000);
        assertFalse(value1.get());
        assertTrue(value2.get());
        Thread.sleep(2000);
        assertTrue(value1.get());
        assertTrue(value2.get());
    }
}

در این تست یک a را ایجاد می کنیم HashedWheelTimer و دو AtomicBooleans با مقدار اولیه false. ما یک کار را برنامه ریزی می کنیم تا اولین بولی را بعد از 11 ثانیه تغییر دهد و دیگری را برای تغییر حالت بولی دوم بعد از 5 ثانیه. سپس رشته تست را هر 2 ثانیه از سر می گیریم و مقدار عدد صحیح را تا 11 ثانیه بررسی می کنیم.

از آنجایی که ما در هر تیک و همچنین برای هر کار پردازش شده، تعدادی دستور اشکال زدایی داریم، اجرای آزمایش یک ردیابی مفید نیز به ما می دهد:

Tick 0
Tick 1
Processing task de.frosner.HashedWheelTimerTest$$Lambda$352/0x0000000800cac000@6f1364d9 with 1 remaining rounds
Tick 2
Tick 3
Tick 4
Tick 5
Processing task de.frosner.HashedWheelTimerTest$$Lambda$353/0x0000000800cac408@592d000b with 0 remaining rounds
Tick 6
Tick 7
Tick 8
Tick 9
Tick 0
Tick 1
Processing task de.frosner.HashedWheelTimerTest$$Lambda$352/0x0000000800cac000@6f1364d9 with 0 remaining rounds

این تست به بررسی اینکه کارها قبل از مدت زمان تأخیر اجرا نشده اند و تقریباً بعد از مدت زمان مناسب اجرا می شوند کمک می کند. البته توجه داشته باشید که به دلیل ماهیت اجرای threaded و زمان‌بندی سیستم، اگر سیستم تحت بار سنگین باشد یا مشکلات دیگری که باعث تاخیرهای قابل‌توجه می‌شوند، ممکن است این تست به طور بالقوه با شکست مواجه شود.

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

بحث

مزایای تایمر چرخ هش:

• بهره وری: تایمر چرخ هش شده پیچیدگی زمانی O(1) را برای عملیات درج و حذف فراهم می کند. برای مدیریت تعداد زیادی از رویدادهای تایمر همزمان عالی است.

• سربار کم: تایمر فقط باید تعداد ثابتی از سطل ها را مدیریت کند، مهم نیست که چند رویداد تایمر وجود دارد. این منجر به سربار کمتری در مقایسه با سایر مکانیسم های مدیریت تایمر می شود.

معایب تایمر چرخ هشد:

• وضوح: وضوح تایمر با طول مدت تیک و اندازه چرخ تعیین می شود. اگر به یک تایمر با وضوح بالا نیاز باشد، اندازه چرخ ممکن است بسیار بزرگ شود که استفاده از حافظه را افزایش می دهد.

• عدم دقت: وظایف تایمر دقیقاً پس از تأخیر آنها اجرا نمی شود. یک عدم دقت وجود دارد که برابر با مدت تیک است. این ممکن است برای بسیاری از موارد استفاده مشکلی ایجاد نکند، اما چیزی است که باید از آن آگاه بود.

جایگزین های تایمر چرخ هش شده:

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

• تایمرهای مبتنی بر فهرست: این تایمرها فهرست مرتب شده ای از رویدادهای تایمر را حفظ می کنند. درج رویداد تایمر در این مورد O(n) است، اما حذف رویداد در سر لیست O(1) است. این می تواند در سناریوهای خاص یک معامله قابل قبول باشد.

خلاصه

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

مکانیسم های مدیریت تایمر جایگزین، مانند تایمرهای مبتنی بر پشته و تایمرهای مبتنی بر لیست، بسته به نیازهای خاص سیستم می توانند مورد استفاده قرار گیرند. مانند هر تصمیم فنی دیگری، انتخاب مکانیسم مدیریت تایمر باید بر اساس درک کامل ویژگی های آن و الزامات مورد استفاده در دست انجام شود.

منابع