【Nginx】ファイルキャッシュの追い出しアルゴリズム

mogile.web.fc2.com

nginxが持っている機能のファイルキャッシュの追い出し方法について調べたので書いた。

ざっくり結論としてはキューを用いたLRUでキャッシュサイズが指定した値より大きい場合は要素の末尾を削除していくという実装

static time_t
ngx_http_file_cache_expire(ngx_http_file_cache_t *cache)
{
    for ( ;; ) {
        q = ngx_queue_last(&cache->sh->queue);

        fcn = ngx_queue_data(q, ngx_http_file_cache_node_t, queue);

        wait = fcn->expire - now;

        if (fcn->count == 0) {
            ngx_http_file_cache_delete(cache, q, name);
            goto next;
        }

キューの実装自体は以下のように双方向リストとなっている。

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};