APCuのTTLの仕様を深堀り

本記事は、[サムザップ Advent Calendar 2022](https://qiita.com/advent-calendar/2022/sumzap) の12/11の記事です。

APCuは、PHP用のインメモリのkey-valueストアです。
主にキャッシュ用に使われ、キャッシュ期間を指定するためのTTL(Time to Live)、つまりデータの保存期間を決めることが出来ます。
今回はこのTTLについて、実装を見ながら細かい仕様を探ります。

## 結論
TTLの期限切れには2種類ある。
- エントリーTTLに基づくハードな期限切れ
- グローバルTTLに基づくソフトな期限切れ

ハードに期限の切れたデータは、データにアクセスすると消えたものとして扱われる。
ソフトに期限の切れたデータは、データにアクセスはできるが、いつでも消え得る。

ただし、どのデータもメモリを掃除するキッカケが無ければ、メモリに居座り続ける。

---
まずは、TTLと期限切れの概念について確認します。

## 2種類のTTL

APCuには2種類のTTLが存在します。

- [`php.ini` 上で設定する `apc.ttl`](https://www.php.net/manual/ja/apcu.configuration.php#ini.apcu.ttl)
- [キャッシュエントリーを作成する際に指定するTTL](https://www.php.net/manual/ja/function.apcu-add.php)

ここでは、iniオプションに指定するTTLを**グローバルTTL**
エントリー作成時に指定するTTLを**エントリーTTL**と呼ぶことにします。

どちらもデフォルトの値は `0` です。APCu上では0の意味するところが2つのTTLで異なります。

- グローバルTTL : 設定されていない
- エントリーTTL : 期限が無い (基本的に常に残り続ける)

## 2種類の期限切れ

ここからはAPCuの実装を見ていきましょう。
実装を見ると、3種類の期限切れが定義されています。
```c
/* An entry is hard expired if the creation time if older than the per-entry TTL.
 * Hard expired entries must be treated indentially to non-existent entries. */
static zend_bool apc_cache_entry_hard_expired(apc_cache_entry_t *entry, time_t t) {
	return entry->ttl && (time_t) (entry->ctime + entry->ttl) < t;
}

/* An entry is soft expired if no per-entry TTL is set, a global cache TTL is set,
 * and the access time of the entry is older than the global TTL. Soft expired entries
 * are accessible by lookup operation, but may be removed from the cache at any time. */
static zend_bool apc_cache_entry_soft_expired(
		apc_cache_t *cache, apc_cache_entry_t *entry, time_t t) {
	return !entry->ttl && cache->ttl && (time_t) (entry->atime + cache->ttl) < t;
}

static zend_bool apc_cache_entry_expired(
		apc_cache_t *cache, apc_cache_entry_t *entry, time_t t) {
	return apc_cache_entry_hard_expired(entry, t)
		|| apc_cache_entry_soft_expired(cache, entry, t);
}
```
([引用元](https://github.com/krakjoe/apcu/blob/master/apc_cache.c#L130))

それぞれについて読み解きます。
<details>
<summary> コード上の変数について </summary>
<div>

`time_t t` 引数上の値。通常現在時刻が渡されます。
`cache->ttl` グローバルTTL
`entry->ttl` エントリーTTL
`entry->ctime` エントリーが作成された時刻

`!entry->ttl` のようなbool値は、その値が`0`であるときに `true` になります。

</div>
</details>


### hard expired
名の通り、ハードなexpiredです。
エントリーTTLを超えているかを判定していることが解ります。

**エントリーを存在しているものとして扱ってよいか**を確認する際に用いられます。

### soft expired
ソフトなexpiredです。(?)
エントリーTTLが設定されていない場合に、グローバルTTLを超えているかを確認しています。

この関数単体で用いられることはありません。

### expired
hardとsoftのORを取った結果です。
纏めると以下のような条件になります。

- エントリーTTLが0でなければ、そのTTLを超えているか確認
- エントリーTTLが0かつグローバルTTLが設定されていれば、グローバルTTLを超えているか確認
- エントリーTTLが0かつグローバルTTLが0であれば、常にfalse

**削除してよいデータであるか**を確認する際に用いられます。

---

それでは、TTLがどのように機能するかを具体的に確認します。
ここでは、「データ挿入時」「データ探索時」「メモリがあふれた時」の3つのパターンに分けて確認していきます。

## データ挿入時

この関数は、`apcu_add`や`apcu_put`等でデータを挿入する際に呼び出されます。

```c
static inline zend_bool apc_cache_wlocked_insert(
		apc_cache_t *cache, apc_cache_entry_t *new_entry, zend_bool exclusive) {
	zend_string *key = new_entry->key;
	time_t t = new_entry->ctime;

	/* process deleted list  */
	apc_cache_wlocked_gc(cache);

	/* make the insertion */
	{
		apc_cache_entry_t **entry;
		zend_ulong h;
		size_t s;

		/* calculate hash and entry */
		apc_cache_hash_slot(cache, key, &h, &s);

		entry = &cache->slots[s];
		while (*entry) {
			/* check for a match by hash and string */
			if (apc_entry_key_equals(*entry, key, h)) {
				/*
				 * At this point we have found the user cache entry.  If we are doing
				 * an exclusive insert (apc_add) we are going to bail right away if
				 * the user entry already exists and is hard expired.
				 */
				if (exclusive && !apc_cache_entry_hard_expired(*entry, t)) {
					return 0;
				}

				apc_cache_wlocked_remove_entry(cache, entry);
				break;
			}

			/*
			 * This is a bit nasty. The idea here is to do runtime cleanup of the linked list of
			 * entry entries so we don't always have to skip past a bunch of stale entries.
			 */
			if (apc_cache_entry_expired(cache, *entry, t)) {
				apc_cache_wlocked_remove_entry(cache, entry);
				continue;
			}

			/* set next entry */
			entry = &(*entry)->next;
		}

		/* link in new entry */
		new_entry->next = *entry;
		*entry = new_entry;

		cache->header->mem_size += new_entry->mem_size;
		cache->header->nentries++;
		cache->header->ninserts++;
	}

	return 1;
}
```
([引用元](https://github.com/krakjoe/apcu/blob/master/apc_cache.c#L338))

関係していそうな箇所を、順に確認していきます。

```c
		/* calculate hash and entry */
		apc_cache_hash_slot(cache, key, &h, &s);

		entry = &cache->slots[s];
```
まず、APCuのデータの持ち方として、いくつかのスロットに分けてデータが保存されていることが解ります。


```c
		while (*entry) {
			/* check for a match by hash and string */
			if (apc_entry_key_equals(*entry, key, h)) {
				/*
				 * At this point we have found the user cache entry.  If we are doing
				 * an exclusive insert (apc_add) we are going to bail right away if
				 * the user entry already exists and is hard expired.
				 */
				if (exclusive && !apc_cache_entry_hard_expired(*entry, t)) {
					return 0;
				}

				apc_cache_wlocked_remove_entry(cache, entry);
				break;
			}

			/*
			 * This is a bit nasty. The idea here is to do runtime cleanup of the linked list of
			 * entry entries so we don't always have to skip past a bunch of stale entries.
			 */
			if (apc_cache_entry_expired(cache, *entry, t)) {
				apc_cache_wlocked_remove_entry(cache, entry);
				continue;
			}

			/* set next entry */
			entry = &(*entry)->next;
		}
```

この`while`文の中で、keyが一致するエントリーが存在するかを確認していますね。

```c
				/*
				 * At this point we have found the user cache entry.  If we are doing
				 * an exclusive insert (apc_add) we are going to bail right away if
				 * the user entry already exists and is hard expired.
				 */
				if (exclusive && !apc_cache_entry_hard_expired(*entry, t)) {
					return 0;
				}
```

コメントを読むと、`apc_add`を行ったときに、ハードなexpiredでないエントリーが存在した場合はエラー、とするためのチェックであると分かります。(`apcu_add`でも同様です)
`apc_add`や`apcu_add`は、指定した`key`に既にエントリーがあった場合はエラーとなる操作です。
実装上でも**エントリーTTLが切れていないデータが存在する時は、`apcu_add`ではエラーとなる**ことが解りました。
逆に言えば、ここではグローバルTTLは関係しません。


さて、コードの中に気になる実装があります。
```c
			/*
			 * This is a bit nasty. The idea here is to do runtime cleanup of the linked list of
			 * entry entries so we don't always have to skip past a bunch of stale entries.
			 */
			if (apc_cache_entry_expired(cache, *entry, t)) {
				apc_cache_wlocked_remove_entry(cache, entry);
				continue;
			}
```
> これはちょっと意地悪です。
> ここでのアイデアは、エントリエントリのリンクリストの実行時クリーンアップを行うことで、常に古いエントリの束をスキップする必要がないようにすることです。

要するに、毎回期限切れのデータを含めて探索するのは非効率なので、データをお掃除します。という感じでしょうか。
ここでは、expiredであればエントリを削除しています。
つまり、**ハードかソフトかどちらかの期限が切れている場合は、挿入中に削除される可能性がある**という事です。

振り返ると、データはスロットリングされていたり、関数内では前述のチェックでアーリーリターンされることがあります。
つまり、どの期限切れのデータが削除されるかどうかは**予想できません**。

グローバルTTLでもエントリーTTLでも、期限切れのエントリーにアクセスする場合は、あればラッキー！程度に考えるべきですね。

## データ探索時

この関数は、`apcu_fetch`等でデータを取得する際に呼び出されます。

```c
/* Find entry, updating stat counters and access time */
static inline apc_cache_entry_t *apc_cache_rlocked_find(
		apc_cache_t *cache, zend_string *key, time_t t) {
	apc_cache_entry_t *entry;
	zend_ulong h;
	size_t s;

	/* calculate hash and slot */
	apc_cache_hash_slot(cache, key, &h, &s);

	entry = cache->slots[s];
	while (entry) {
		/* check for a matching key by has and identifier */
		if (apc_entry_key_equals(entry, key, h)) {
			/* Check to make sure this entry isn't expired by a hard TTL */
			if (apc_cache_entry_hard_expired(entry, t)) {
				break;
			}

			ATOMIC_INC_RLOCKED(cache->header->nhits);
			ATOMIC_INC_RLOCKED(entry->nhits);
			entry->atime = t;

			return entry;
		}

		entry = entry->next;
	}

	ATOMIC_INC_RLOCKED(cache->header->nmisses);
	return NULL;
}
```
([引用元](https://github.com/krakjoe/apcu/blob/master/apc_cache.c#L456))

データ挿入時とほぼ同様に、keyが一致するエントリーを探索していることが解ります。

```c
			/* Check to make sure this entry isn't expired by a hard TTL */
			if (apc_cache_entry_hard_expired(entry, t)) {
				break;
			}
```

エントリーが見つかっても、ハードなexpiredであれば、データは取得できなくなっています。
しかし、この際にはソフトなexpiredはチェックしていません。
つまり、**エントリーTTLを超えている場合、該当するエントリーがメモリ上に存在しても取得できないが、グローバルTTLを超えているだけならエントリーは取得できる**ことが解ります。

　
ところで、期限切れでエントリーを取得できなかった場合に、メモリ上からエントリーの削除はしていないようです。
データ取得を契機にメモリ上からエントリーが削除されることはなさそうです。

## メモリがあふれた時

最後に、APCuが使用できるメモリが満タンになった際に呼び出される関数を見てみましょう。

```c
PHP_APCU_API void apc_cache_default_expunge(apc_cache_t* cache, size_t size)
{
	time_t t;
	size_t suitable = 0L;
	size_t available = 0L;

	if (!cache) {
		return;
	}

	/* apc_time() depends on globals, don't read it if there's no cache. This may happen if SHM
	 * is too small and the initial cache creation during MINIT triggers an expunge. */
	t = apc_time();

	/* get the lock for header */
	if (!apc_cache_wlock(cache)) {
		return;
	}

	/* make suitable selection */
	suitable = (cache->smart > 0L) ? (size_t) (cache->smart * size) : (size_t) (cache->sma->size/2);

	/* gc */
	apc_cache_wlocked_gc(cache);

	/* get available */
	available = apc_sma_get_avail_mem(cache->sma);

	/* perform expunge processing */
	if (!cache->ttl) {
		/* check it is necessary to expunge */
		if (available < suitable) {
			apc_cache_wlocked_real_expunge(cache);
		}
	} else {
		/* check that expunge is necessary */
		if (available < suitable) {
			size_t i;

			/* look for junk */
			for (i = 0; i < cache->nslots; i++) {
				apc_cache_entry_t **entry = &cache->slots[i];
				while (*entry) {
					if (apc_cache_entry_expired(cache, *entry, t)) {
						apc_cache_wlocked_remove_entry(cache, entry);
						continue;
					}

					/* grab next entry */
					entry = &(*entry)->next;
				}
			}

			/* if the cache now has space, then reset last key */
			if (apc_sma_get_avail_size(cache->sma, size)) {
				/* wipe lastkey */
				memset(&cache->header->lastkey, 0, sizeof(apc_cache_slam_key_t));
			} else {
				/* with not enough space left in cache, we are forced to expunge */
				apc_cache_wlocked_real_expunge(cache);
			}
		}
	}

	apc_cache_wunlock(cache);
}
```
([引用元](https://github.com/krakjoe/apcu/blob/master/apc_cache.c#L735))

コードを見ると2パターンに分かれていることがわかります。
```c
	if (!cache->ttl) {
		/* check it is necessary to expunge */
		if (available < suitable) {
			apc_cache_wlocked_real_expunge(cache);
		}
	}
```
まず、グローバルTTLが設定されていない(つまり`0`である)場合です。
メモリ残量が足りなければ`apc_cache_wlocked_real_expunge`という関数を呼び出していますね。
この関数は後程確認しましょう。

```c
	} else {
		/* check that expunge is necessary */
		if (available < suitable) {
			size_t i;

			/* look for junk */
			for (i = 0; i < cache->nslots; i++) {
				apc_cache_entry_t **entry = &cache->slots[i];
				while (*entry) {
					if (apc_cache_entry_expired(cache, *entry, t)) {
						apc_cache_wlocked_remove_entry(cache, entry);
						continue;
					}

					/* grab next entry */
					entry = &(*entry)->next;
				}
			}

			/* if the cache now has space, then reset last key */
			if (apc_sma_get_avail_size(cache->sma, size)) {
				/* wipe lastkey */
				memset(&cache->header->lastkey, 0, sizeof(apc_cache_slam_key_t));
			} else {
				/* with not enough space left in cache, we are forced to expunge */
				apc_cache_wlocked_real_expunge(cache);
			}
		}
	}
```
次はグローバルTTLが設定されている場合です。

```c
			/* look for junk */
			for (i = 0; i < cache->nslots; i++) {
				apc_cache_entry_t **entry = &cache->slots[i];
				while (*entry) {
					if (apc_cache_entry_expired(cache, *entry, t)) {
						apc_cache_wlocked_remove_entry(cache, entry);
						continue;
					}

					/* grab next entry */
					entry = &(*entry)->next;
				}
			}
```
全てのスロットから、期限切れのエントリーを削除していることがわかります。
ここでは、ハードな期限切れでも、ソフトな期限切れでもエントリーを削除しています。

```c
			/* if the cache now has space, then reset last key */
			if (apc_sma_get_avail_size(cache->sma, size)) {
				/* wipe lastkey */
				memset(&cache->header->lastkey, 0, sizeof(apc_cache_slam_key_t));
			} else {
				/* with not enough space left in cache, we are forced to expunge */
				apc_cache_wlocked_real_expunge(cache);
			}
```
しかし、期限切れのエントリーを掃除しても容量が足りなかった場合は、`apc_cache_wlocked_real_expunge`関数を呼び出しているようです。

では`apc_cache_wlocked_real_expunge`関数を確認してみましょう。

```c
static void apc_cache_wlocked_real_expunge(apc_cache_t* cache) {
	size_t i;

	/* increment counter */
	cache->header->nexpunges++;

	/* expunge */
	for (i = 0; i < cache->nslots; i++) {
		apc_cache_entry_t **entry = &cache->slots[i];
		while (*entry) {
			apc_cache_wlocked_remove_entry(cache, entry);
		}
	}

	/* set new time so counters make sense */
	cache->header->stime = apc_time();

	/* reset counters */
	cache->header->ninserts = 0;
	cache->header->nentries = 0;
	cache->header->nhits = 0;
	cache->header->nmisses = 0;

	/* resets lastkey */
	memset(&cache->header->lastkey, 0, sizeof(apc_cache_slam_key_t));
}
```
([引用元](https://github.com/krakjoe/apcu/blob/master/apc_cache.c#L685))

非常にシンプルですね！
全てのエントリーを削除しています。

ここで思い出していただきたいのは、グローバルTTLが設定されていなかった場合に、初手でこの関数が呼び出されていたことです。
つまり...

- **グローバルTTLが設定されていない場合は、TTL関係なく全てのエントリーを削除する**
- **グローバルTTLが設定されている場合は、エントリーTTLとグローバルTTLを元に期限切れのエントリーをまず削除する**
  - **それでもメモリ容量が足りなければ、すべてのエントリーを削除する**

ということになります。
グローバルTTLを設定していない場合、エントリーTTLを元にメモリの掃除を試みてくれないのは、意外だったのではないでしょうか。

## まとめ

纏めてみると以下のようになりました。

**データ挿入時**
- データの上書きを許さない操作の場合、同じkeyにエントリーTTLが切れていないデータが存在するとエラーになる

**データ探索時**
- エントリーTTLを超えているデータは取得できない
- グローバルTTLだけ超えているデータは取得できる

**メモリがあふれた時**
- グローバルTTLが設定されていない場合、全データを削除する
- グローバルTTLが設定されている場合
  - エントリーTTLが切れているか、エントリーTTLが0でグローバルTTLが切れているデータを削除する
  - それでも容量が足りなければ、全データを削除する

## 最後に

調べてみると、APCuのTTLは意外と複雑でした。
特にグローバルTTLについては、どの様に用いられるかがわかったことで、個人的にも勉強になりました。

みなさんも、是非APCuを用いられる場合はグローバルTTLに値を設定するか否かを考えていただき、その際にはこの記事を参考にしていただければ幸いです。

## 参考
- https://www.php.net/manual/ja/book.apcu.php
- https://github.com/krakjoe/apcu