この記事は「nginx Advent Calendar 2022」の17日目の記事です。
ngx_http_limit_req_moduleを使うことでリミットの制限を行うことが出来る。ここで疑問に思ったがめちゃめちゃ大量にアクセス元があるサイトでこの実装をしたときどういうメモリの使い方をしてるんだろうと思って調べてみた。
アクセスログとかからアクセス元ごとにカウントする際のいい感じの方法って何になるんだろ？何も考えずにやるとアクセス元の数だけキーが増えてメモリ全然足らん！となりそう。
— Ryuichi@Gurasan:|| (@ryuichi_1208) 2022年12月17日
例えば全世界のパブリックIPから一度にアクセスを受けた際にメモリの制限をしていないと32bit(4byte)で格納しておくと43億あるので4[B] * 4,300,000,000 = 17.2 [GB]のメモリが必要となる。これはIPの例なのでありえないかも知れないが例えばパスごとに〜とかクエリパラメーターごとにみたいな用途があるとしたらこの数値は全然現実的に見えてくる。nginx + webappみたいな構成を取ってるとしてnginxのVMなりコンテナなりに10何GBも与えるケースってそんなに無い気がするのでこれを回避する方法を見てみた。
limit_req_zoneはサイズを引数に出来る
limit_req_zoneはサイズを指定することでそのサイズ以上のキーは全てexpireしてくれる仕組みになっている。
Syntax: limit_req_zone key zone=name:size rate=rate [sync]; Default: — Context:
実装を見る
本題はこれ。expireしてくれるのは予想通りだとして脳内で実装を考えてみたらハッシュテーブルを予め用意したサイズでキーとアクセス数をカウントして溢れたら古いものを線形探索して削除する？？みたいになった。この場合インクリメントはO(1)なので早いが溢れた際の処理がやばい。サイズを1MBにしておけばデータ量は10,000程度なので全然余裕だが100MBとか指定した際に顕著な性能劣化をしそうと思った。じゃあNginxはどうやってるんだろって思って調べてみた。
epireの処理は以下。アクセスごとのキーなどの情報は赤黒木で管理しておいてその情報をキューに格納して管理している。それぞれ平均で探索はO(logN)、挿入、削除はO(1)で行えるLRUのキューはdoubly-linked listで実装されている。探索してデータが既に有ればキューを削除して先頭に持ってくる。なければ先頭に追加するという処理になる。
static void ngx_http_limit_req_expire(ngx_http_limit_req_ctx_t *ctx, ngx_uint_t n) { ngx_int_t excess; ngx_msec_t now; ngx_queue_t *q; ngx_msec_int_t ms; ngx_rbtree_node_t *node; ngx_http_limit_req_node_t *lr; now = ngx_current_msec; /* * n == 1 一番古いものを削除しつつ1つか2つ別で削除 * n == 0 一番古いものを削除 * and one or two zero rate entries */ while (n < 3) { if (ngx_queue_empty(&ctx->sh->queue)) { return; } q = ngx_queue_last(&ctx->sh->queue); lr = ngx_queue_data(q, ngx_http_limit_req_node_t, queue); if (lr->count) { /* * There is not much sense in looking further, * because we bump nodes on the lookup stage. */ return; } ngx_queue_remove(q); // キューからの削除 } }
感想
最初に思いついたハッシュテーブル1つで頑張る方法と比べて全然処理が違くてデータ構造は大事だなぁと感じた。
