LorenzとLittle：あなたのテール（末尾）はどれくらいコストがかかるか？

Lorenz and Little: How Much Does Your Tail Cost?

Lorenz and Littleは、2015年のヒップスターバーガー店のような響きだ。

今日は、コスト最適化においてテールレイテンシに私がなぜ多大な注意を払うのか、マークの統計コーナーの時間だ！今日は、コスト最適化におけるテールレイテンシについて話したい。

以前にも、顧客体験におけるテールレイテンシの重要性について書いたことがある（例えば、2026年、2021年、2021年、そして2017年）。今日は、コストとキャパシティの観点からテールレイテンシについて話したい。

多くのシステムオペレーターと同様に、私もパーセンタイルを用いてテールレイテンシを考えている。

ここで一つの疑問だ：私のレイテンシの各パーセンタイルは、平均レイテンシにどれだけ寄与しているのか？直感的には「かなり多く」という答えだが、定量化できるだろうか？できる！私たちが探しているのは、経験的なローレンツ曲線だ。これは、「レイテンシのパーセンタイル $P$（例：p99=100ms）に対して、$P$ より短いリクエストが平均レイテンシにどれだけ寄与するか？」という問いに直接答えてくれる。（これを $L(P)$ と呼ぶとすると、私たちの問いに対する真の答えは $1 - L(P)$ となる）。

レイテンシサンプルからの計算は非常にシンプルだ：L = sum(sorted(x)[:k]) / sum(x)（n 個のレイテンシサンプル x のセットと k=p*n に対して）。分位数（quantiles）のベクトルからは、サンプル間の補間方法や最大値への外挿方法を選択する必要があるため、少し複雑になる。ここではべき乗則（power law）を用いて補間している。これは少し「罪」[1]だが、目的には十分だ。

# Calculate 1 - L(p) for a vector of measured quantiles
# q - an array of quantiles (e.g. [1, 10, 200, 10000, 20000])
# p - an array of percentiles they're measured at (e.g. [0, 0.5, 0.9, 0.99, 0.999])
# OneMinusL - One minus the empirical Lorenz curve for each of the percentiles
def OneMinusL(q, p):
  q, p = np.asarray(q, float), np.asarray(p, float)
  assert q.shape == p.shape and q.size >= 2, "q, p must be same-length, size >= 2"
  assert p[0] == 0 and p[-1] < 1, "p must start at 0 (else mass is dropped) and end below 1"
  assert np.all(np.diff(p) > 0), "p must be strictly increasing"
  assert q[0] > 0 and np.all(np.diff(q) > 0), "q must be positive and strictly increasing"
  w = q*(1-p)
  a = np.log((1-p[1:])/(1-p[:-1]))/np.log(q[:-1]/q[1:])
  assert np.all(np.abs(a-1) > 1e-9), "alpha == 1 in some cell: divide by zero"
  assert a[-1] > 1, f"tail alpha={a[-1]:.3f} <= 1: infinite mean, not estimable"
  c = np.r_[0, np.cumsum(a/(a-1)*(w[:-1]-w[1:]))]
  return 1 - c/(c[-1] + a[-1]/(a[-1]-1)*w[-1])

例えば：

print(OneMinusL([1, 10, 200, 10000, 20000], [0, 0.5, 0.9, 0.99, 0.999]))
[1. 0.99377318 0.93082759 0.51712644 0.10342529]

これは、この分布において、中央値（p50）以上のリクエストが平均レイテンシの約99%を占め、p99以上のリクエストが平均レイテンシの約52%を占めることを示している[2]。

これは面白いが、なぜ気にするのか？なぜなら、リトルの法則は、この値（平均への寄与）がシステム内のコンカレンシーへの寄与でもあると教えてくれるからだ。単純なスレッドシステムでは、$1 - L(p) = k$ ならば、私たちのサービスにおけるビジースレッドの $100k$% は、$p$ パーセンタイル以上のレイテンシを持つリクエストでビジー状態にあることになる[3]。キュー、イベントベースの実装などは、コンカレンシーとコストのマッピングを複雑にするため、自身のシステムの文脈でそれらを考慮する必要がある。

私の経験では、サービスにおいて $1 - L(0.99)$ が $0.5$ や $0.75$ を超えることは珍しくない。これは、テールを最適化することが、コンカレンシーの削減、ひいてはキャパシティ需要、ロック競合、そして高いコンカレンシーに伴うその他の要因の削減に、予想以上に大きく貢献する可能性があることを示している。テールは提供するのが不釣り合いに高コストになりがちであり、したがって最適化を考える上で不釣り合いに重要になる。それらを切り捨てる間違いを犯すべきではない。なぜなら、それらはしばしばコストを駆動する要因だからだ！（そしてもちろん、顧客体験の悪化も）。

値で遊びたい場合は、ここにパーセンタイルを入力して、あなたのカーブを見てみよう。

p0: ms   p50: ms   p90: ms   p99: ms   p99.9: ms

各パーセンタイル以上でのリクエストが平均レイテンシに占める割合：p50 –、p90 –、p99 –、そして p99.9 –。リトルの法則により、これらはシステムコンカレンシーのシェアでもある。

脚注

1. ここには2つの罪がある。一つは補間方法を恣意的に選択していること、もう一つは外挿方法を恣意的に選択していることだ。パーセンタイルの密度が高く、データがパレート分布に近ければ近いほど、それらは重要でなくなる。しかし、正確な経験的回答が欲しい場合は、異なるアプローチ（具体的には、ソートされた生サンプルに基づくアプローチ）を使用する必要がある。アマチュア統計コーナーだと言っただろう。
2. ここでのもう一つの罪は、もちろん、測定されたパーセンタイルが真のパーセンタイルの推定値であり、パーセンタイルが大きくなるにつれて不確実性が増すことだ。重いテールと少ないサンプルがあると、非常に変動しやすい結果が得られる可能性がある。理想的ではないが、結論は変わらない。
3. より正確には、pパーセンタイルを完了することになるリクエスト。監視とメトリクスに基づいて事後的にこれを行っているため、それは問題ではない。ライブ観測でこれをやろうとしている場合、その区別が重要になる可能性がある。これもまた、アマチュア統計コーナーだ。