ダボにおけるタイムホイールアルゴリズムの応用

[[346568]]

1 スケジュールされたタスク

Netty、Quartz、Kafka、Linux にはすべてスケジュールされたタスク機能があります。

JDK に付属する java.util.Timer と DelayedQueue は、単純なスケジュールされたタスクを実装できます。基礎となるレイヤーはヒープを使用し、アクセスの複雑さは O(nlog(n)) ですが、大規模なスケジュールされたタスクをサポートすることはできません。

タスク量が多く、パフォーマンス要件が高いシナリオでは、タイムホイールアルゴリズムを使用して、タスクアクセスとキャンセル操作の時間計算量を O(1) に削減します。

2 タイムホイールモデルとその応用

スケジュールされたタスクを効率的にバッチ管理するためのスケジューリングモデル。これは通常、時計に似たリング構造として実装され、多くのスロットに分割され、1 つのスロットは時間間隔を表し、各スロットは双方向リンクリストを使用してスケジュールされたタスクを格納します。

ポインタは定期的にジャンプし、スロットにジャンプすると、そのスロットのタイミングタスクが実行されます。

ハッシュタイミングホイール構造図

障害回復
フロー制御
スケジューリングアルゴリズム
ネットワーク内のパケットのライフサイクルを制御する

タイマーの維持には費用がかかる

プロセッサはクロックごとに中断される
きめ細かいタイマーを使用する
未完成のタイマーが多数あります

全体的な割り込みオーバーヘッドを削減するには、効率的なタイマーアルゴリズムが必要です。

単層タイムホイールの容量と精度には限界があります。特に高い精度が求められるシナリオ、特に長い時間範囲、またはスケジュールする必要のある大量のタスクがある場合、通常は、マルチレベルタイムホイールと、永続ストレージとタイムホイールを組み合わせたソリューションが使用されます。

モデルとパフォーマンスの指標

モデルのルール

クライアントからの呼び出し:

START_TIMER(間隔、リクエストID、有効期限アクション)
STOP_TIMER (リクエストID)

タイマーティック呼び出し:

ティックごとのブックキーピング
有効期限処理

パフォーマンス指標

空間

データ構造で使用されるメモリ

遅れ

上記のルーチンの開始と終了にかかる時間

3 ダボのタイムホイール構造

Dubbo タイマーは、dubbo-common モジュールの org.apache.dubbo.common.timer パッケージに実装されています。次に、タイマーに関係するコアインターフェースと実装を分析します。

コアインターフェース

タイマータスク

Dubbo では、スケジュールされたすべてのタスクは TimerTask インターフェイスを実装する必要があります。定義されている run() メソッドは 1 つだけであり、入力パラメーターは Timeout インターフェイスオブジェクトです。

タイムアウト

Timeout オブジェクトは、スレッドプールによって返される Future オブジェクトとスレッドプールに送信されたタスクオブジェクトの関係と同様に、TimerTask オブジェクトと 1 対 1 で対応します。
Timeout オブジェクトを使用すると、スケジュールされたタスクのステータスを表示できるだけでなく、スケジュールされたタスクを操作することもできます (たとえば、関連するスケジュールされたタスクをキャンセルするなど)。

Timeout インターフェースのメソッド:

Timer インターフェイスはタイマーの基本的な動作を定義します。その中核となるのは newTimeout() です。つまり、スレッドプールにタスクを送信するのと同様に、時間制限付きタスク (TimerTask) を送信し、関連付けられた Timeout オブジェクトを返します。

ハッシュホイールタイムアウト

HashedWheelTimeout は、Timeout インターフェイスの唯一の実装であり、HashedWheelTimer の内部クラスです。 HashedWheelTimeout には 2 つの役割があります。

タイムホイール内の双方向リンクリストのノード、つまりHashedWheelTimer内のタイマータスクTimerTaskのコンテナ

タイマータスク TimerTask が HashedWheelTimer に送信された後に返されるハンドルは、タイムホイールの外部でタイマータスクを表示および制御するために使用されます。

コア分野

前へ、次へ。二重リンクリストは、HashedWheelTimerBucket でタイムアウトを連鎖するために使用されます。これは WorkerThread でのみ機能するため、同期/揮発性は必要ありません。

task 、スケジュールされている実際のタスク

期限、スケジュールされたタスクが実行される時間。 HashedWheelTimeoutを作成するときは、計算式を指定します：currentTime（HashedWheelTimeoutが作成された時刻）+ delay（タスク遅延時間）- startTime（HashedWheelTimerの開始時刻）、ns

状態、スケジュールされたタスクの現在の状態

オプションのステータス:

STATE_UPDATER は、状態変更のアトミック性を実装するために使用されます。

residualRounds : 現在のタスクに残っているクロックサイクルの数。タイムホイールが表すことができる時間の長さには制限があります。タスクの有効期限と現在の時刻の差が、タイムホイールの 1 回転で表すことができる時間の長さを超えると、ループが発生し、残りのクロックサイクルを表すためにこのフィールドの値が必要になります。

コアAPI

キャンセルされました()

期限切れです()

州（）
現在のHashedWheelTimeoutステータスを確認する

cancel()メソッド

expire()メソッド

取り除く（）

ハッシュホイールバケット

時の車輪の中の隙間。
タイムホイールのスロットは、実際には二重リンクリストをキャッシュして管理するためのコンテナーです。二重リンクリストの各ノードは、TimerTask タイミングタスクに関連付けられた HashedWheelTimeout オブジェクトです。

HashedWheelBucket は、双方向リンクリストの最初と最後のノード (先頭と末尾) を保持します。さらに、各 HashedWheelTimeout ノードは先行参照と後続参照を保持するため、リンクリスト全体を前方および後方にトラバースできます。

コアAPI

タイムアウトを追加します。

ポーリングタイムアウト()

取り除く（）
指定された HashedWheelTimeout ノードを二重リンクリストから削除します。

タイムアウトをクリアする()
pollTimeout() メソッドは周期的に呼び出され、二重リンクリスト全体を処理して、タイムアウトまたはキャンセルされていないすべてのタスクを返します。

有効期限切れ()
二重リンクリスト内のすべての HashedWheelTimeout ノードを走査します。期限切れのスケジュールされたタスクを処理する場合、そのタスクは remove() メソッドによって取り出され、expire() メソッドが呼び出されて実行されます。キャンセルされたタスクの場合は、remove() メソッドによって取り出された後、直接破棄されます。期限切れになっていないタスクの場合は、remainingRounds フィールド (残りのクロックサイクル数) が 1 つ減ります。

ハッシュホイールタイマー

タイムホイールアルゴリズムを通じてタイマーを実装する Timer インターフェイスの実装。

機能

現在のタイムホイールポインターに従って対応する HashedWheelBucket スロットを選択し、リンクリストの先頭から反復処理して、各 HashedWheelTimeout スケジュールタスクを計算します。

現在のクロックサイクルに属する場合は、取り出されて実行されます
グループに属していない場合は、残りのクロックサイクル数が 1 つ減少します。

コアドメイン

ワーカーステート
タイムホイールの現在の状態。AtomicIntegerFieldUpdater によってアトミックに変更される 3 つのオプション値。

開始時間
現在のタイムホイールの開始時刻。このタイムホイールに送信されたスケジュールされたタスクの期限フィールド値は、このタイムスタンプに基づいて計算されます。

車輪
タイムホイールの循環キュー。各要素はスロットです。タイムスロットの数がnと指定されている場合、nに最も近い2番目の累乗値が上方に取られます。

タイムアウト、キャンセルされたタイムアウト
HashedWheelTimer は、HashedWheelBucket の双方向リンクリストを処理する前に、これら 2 つのキューのデータを処理します。

タイムアウトキュー<br /> 外部送信タイムホイールでスケジュールされたタスクをバッファリングする

キャンセルされたタイムアウトキュー<br /> キャンセルされたスケジュールされたタスクを一時的に保存する

チェック
HashedWheelTimer$Workerにある、タイムホイールのポインター。ステップサイズが1の単調に増加するカウンター。

マスク
マスク、mask = wheel.length - 1、ticksとmaskを実行して対応するクロックスロットを見つけます

ティック期間
時間ポインターの各増分によって表される実際の時間はナノ秒単位です。

保留タイムアウト
現在のタイムラウンドに残っているスケジュールされたタスクの合計数。

ワーカースレッド
実際にタイミングタスクを実行するタイムホイール内のスレッド。

ワーカー
スケジュールされたタスクを実際に実行するロジックは、この Runnable オブジェクトにカプセル化されます。

新しいタイムアウト()

スケジュールされたタスクを送信します。スケジュールされたタスクがタイムアウトキューに入る前に、start() メソッドが呼び出されてタイムホイールが開始され、次の 2 つの重要な手順が完了します。

タイムホイールのstartTimeフィールドを決定する
workerThread スレッドを開始し、ワーカータスクの実行を開始します。

次に、スケジュールされたタスクの期限が startTime に従って計算され、最後にスケジュールされたタスクは HashedWheelTimeout にカプセル化され、タイムアウトキューに追加されます。

4 タイムホイールポインターの1回転の実行フロー

HashedWheelTimer$Worker.run():

タイムホイールのポインターが回転し、タイムホイールのサイクルが始まります
ユーザーによって積極的にキャンセルされたスケジュールされたタスクをクリーンアップします。これらのスケジュールされたタスクがユーザーによってキャンセルされると、cancelledTimeouts キューに記録されます。ポインタが動くたびに、タイムホイールはキューをクリアします
タイムアウトキューにキャッシュされたスケジュールされたタスクをタイムホイールの対応するスロットに転送します。
現在のポインタに従って対応するスロットを見つけ、スロットの双方向リンクリスト内のスケジュールされたタスクを処理します。
タイムホイールの状態を確認します。タイムホイールが実行状態にある場合、上記の手順が周期的に実行され、タイミングタスクが継続的に実行されます。タイマーが停止状態の場合、次の手順を実行して、実行されていない時間指定タスクを取得し、それらを unprocessedTimeouts キューに追加します。タイマー内の各スロットを走査して clearTimeouts() メソッドを呼び出し、タイムアウトキューに追加されていないスロットに対して poll() を周期的に呼び出します。
最後に、ユーザーによってアクティブにキャンセルされた、cancelledTimeouts キュー内のスケジュールされたタスクをクリアします。

5 スケジュールされたタスクアプリケーション

これは定期的な操作に直接使用されるのではなく、タイムホイールにスケジュールされた単一のタスクを送信するだけです。前のタスクが完了したら、newTimeout() メソッドを呼び出して現在のタスクを再度送信し、次のサイクルでタスクが実行されるようにします。タスク実行中に GC や I/O ブロッキングなどが発生し、タスクの遅延や詰まりが発生した場合でも、同じタスクが連続して送信されることはなく、タスクが蓄積されます。

Dubbo タイムホイールの用途は主に以下の分野です。