15章 - TKBTK48/ReadableCode GitHub Wiki

第15章 「分／時間カウンタ」を設計・実装する

15.1 問題点

ウェブサーバの直近の1分間と直近の1時間の転送バイト数を把握したい。

15.2 クラスのインタフェースを定義する

最初のクラスインタフェースのバージョン。

class MinuteHourCounter {
 public:
  // カウントを追加する。
  void Count(int num_bytes);
  // 直近1分間のカウントを返す
  int MinuteCount();
  // 直近1時間のカウントを返す
  int HourCount();
};

名前を改善する

MinuteCount()やHourCount()という名前は合理的である。Getを付けても良いのかもしれないが、Getは軽量アクセサなので、この実装には似合わない。

Count()は何をするのかが分からないので、ほかの名前を考える。

  • Increment() : 値が増加する一方だと思われてしまう。
  • Observe() : 少しあいまい。
  • Record() : 名詞と動詞の問題があるのでダメ。
  • Add() : 「この数値を追加する」と「データのリストに追加する」というどちらの意味もある。

したがって、今回はこのメソッドの名前をAdd(int num_bytes)とする。

コメントを改善する

冗長なコメントを削除し、正確な言葉を使って誤解のない明確なものにする。

// 直近1分間および直近1時間の累積カウントを記録する。
// 例えば、帯域幅の使用状況を確認するのに使える。
class MinuteHourCounter {
 public:
  // 新しいデータ点を追加する (count >= 0).
  // それから1分間は、MinuteCount()の返す値が+countだけ増える。
  // それから1時間は、HourCount()の返す値が+countだけ増える。
  void Add(int num_bytes);
  // 直近60秒間のカウントを返す
  int MinuteCount();
  // 直近3600秒間のカウントを返す
  int HourCount();
};

15.3 試案1: 素朴な解決策

まずは簡単な実装から考えていく。タイムスタンプのついた「イベント」のlistを保持していく。

class MinuteHourCounter {
    struct Event {
        Event (int count, time_t time) : count(count), time(time) {}
        int count;
        time_t time;
    };
    list<Event> events;
  public:
    void Add(int count) {
        events.push_back(Event(count, time()));
    }
    ...
};

必要に応じて直近のイベントをカウントできる。

class MinuteHourCounter {
    ...
    int MinuteCount() {
        int count = 0;
        const time_t now_secs = time();
        for (list<Event>::reverse_iterator i = events.rbegin();
             i != events.rend() && i->time > now_secs - 60; ++i) {
            count += i->count;
        }
        return count;
    }
    int HourCount() {
        int count = 0;
        const time_t now_secs = time();
        for (list<Event>::reverse_iterator i = events.rbegin();
             i != events.rend() && i->time > now_secs - 3600; ++i) {
            count += i->count;
        }
        return count;
    }
};

このコードは理解しやすいか？

  • forループが少しうるさい
  • MinuteCount()とHourCount()がほぼ同じ。

読みやすいバージョン

class MinuteHourCounter {
    ...
    int CountSince(time_t cutoff) {
        int count = 0;
        const time_t now_secs = time();
        for (list<Event>::reverse_iterator rit = events.rbegin();
             rit != events.rend(); ++rit) {
            if (rit->time <= cutoff) {
                break;
            }
            count += rit->count;
        }
        return count;
    }
  public:
    void Add(int count) {
        event.push_back(Event(count, time()));
    }
    int MinuteCount () {
        return CountSince(time()-60));
    }
    int HourCount() {
        return CountSince(time()-3600));
    }
};
  • CounSince()の仮引数の名前をsec_agoという相対値ではなく、cutoffという絶対値に設定している。
  • イテレータの名前をiからritに変えている。
  • forループからrit->time <= cutoffという条件を抽出して、新しくif文を作っている。

パフォーマンスの問題

  • これからも大きくなっていく。このクラスはメモリを無限に使用してしまうため、MinuteHourCounterは、1時間よりも古い不要のイベントを自動的に削除すべきだ。
  • MinuteCount()とHourCount()が遅すぎる。それぞれのメソッドの処理時間はO(n)である。Add()が呼び出された時点で対応する値をminute_countとhour_countとで別々に保持すべきだ。

15.4 試案2: ベルトコンベヤー設計

  • 不要なデータを削除する。
  • 事前にminute_countとhour_countの値を最新のものにしておく。 2段階ベルトコンベヤーの方が効率的なので、こちらを実装してみる。

2段階ベルトコンベヤーの実装

class MinuteHourCounter {
    list<Event> minute_events;
    list<Event> hour_evenst;
    int minute_count;
    int hour_count;
    ...
};

イベントは、minute_eventからhour_eventへ移動する。そのあとで、minute_countとhour_countを更新する。

汚い仕事はShiftOldEvents()に押し付ける。

// 古いイベントを見つけて削除して、hour_countとminute_countを減らす。
void ShiftOldEvent(time_t now_secs) {
    const int minute_ago = now_secs - 60;
    const int hour_ago = now_secs - 3600;
    // 1分以上経過したイベントを'minute_events'から'hour_events'へと移動する。
    // (1時間以上経過した古いイベントは次のループで削除する。)
    while (!minute_events.empty() && minute_events.front().time <= minute_ago) {
        hour_events.push_back(minute_events.front());
        minute_count -= minute_events.front().count;
        minute_events.pop_front();
    }
    // 1時間以上経過した古いイベントを'hour_events'から削除する。
    while (!hour_events.empty() && hour_events.front().time <= hour_ago) {
        hour_count -= hour_events.front().count;
        hour_events.pop_front();
    }
}

これで終わり？

  • この設計には柔軟性が無い。例えば、直近24時間のカウントを保存したいとすると、多くのコードの修正が必要になる。
  • メモリの使用量が多い。こうトラフィックのサーバが1秒間に100回もAdd()を呼び出すと、直近1時間のデータを全て保持しているので、約5MBのメモリが必要となる。 Add()が呼び出される頻度に関係なく、MinuteHourCounterの使用するメモリは一定の方がよい。

15.5 試案3: 時間バケツの設計

60秒で60個のバケツを用意して、直近1分間のイベントは、1秒ごとに60個のバケツに入れる。 直近1時間のイベントは、1分ごとに60個のバケツに入れる。 これにより、メモリ使用量を固定化できて予測可能になるということである。

時間バケツの実装

期間(直近1時間など)のカウントを追跡するクラスを作る。

// 時間バケツN個のカウントを保持するクラス
class TrailingBucketCounter {
  public:
    // 例: TrailingBucketCounter(30, 60) は、直近30分の時間バケツを追跡する。
    TrailingBucketCounter(int num_buckets, int secs_per_bucket);
    void Add(int count, time_t now);
    // 最新のnum_bucketsの時間に含まれる合計カウントを返す。
    int TrailingCount(time_t now);
};

これでMinuteHourCounterは簡単に実装できるようになる。

Class MinuteHourCounter {
  ...
  public:
    MinuteHourCounter():
        minute_counts(/* num_buckets = */ 60, /* secs_per_bucket = */ 1),
        minute_counts(/* num_buckets = */ 60, /* secs_per_bucket = */ 60) {
    }
    void Add (int count) {
        time_t now = time();
        minute_counts.Add(count, now);
        hour_counts.Add(count, now);
    }
    int MinuteCount() {
        time_t now = time();
        return minute_counts.TrailingCount(now);
    }
    int HourCount() {
        time_t now = time();
        return hour_counts.TrailingCount(now);
    }
};

TrailingBucketCounterを実装する

まずは、ConveyorQueueというデータ構造を作る。

// 最大数を持ったキュー。古いデータは端から「落ちる」。
class ConveyorQueue {
    ConveyorQueue(int max_items);
    // キューの最後の値を追加する。
    void AddToBack(int count);
    
    // キューの値を'num_shifted`の分だけシフトする。
    // 新しい項目は0で初期化する。
    // サイコの項目はmax_items以下なら削除する。
    void Shift(int num_shifted);
    
    // 現在のキューに含まれる項目の合計値を返す。
    int TotalSum();
};

クラスを分割することでコードが把握しやすくなる

class TrailingBucketCounter {
  ConveyorQueue buckets;
  const int secs_per_bucket;
  time_t last_update_time; // Update() が最後に呼び出された時刻
  // 通過した時間バケツの数を計算して Shift() する。
  void Update(time_t now) {
    int current_bucket = now / secs_per_bucket;
    int last_update_bucket = last_update_time / secs_per_bucket;
    buckets.Shift(current_bucket - last_update_bucket);
    last_update_time = now;
  }
  public:
    TrailingBucketCounter(int num_buckets, int secs_per_bucket) :
    buckets(num_buckets),
    secs_per_bucket(secs_per_bucket) { }
    void Add(int count, time_t now) {
      Update(now);
      buckets.AddToBack(count);
    }
    int TrailingCount(time_t now) { Update(now);
    return buckets.TotalSum(); }
};

ConveyorQueueの実装

// 最大数を持ったキュー。古いデータは端から「落ちる」。
class ConveyorQueue {
  queue<int> q;
  int max_items;
  int total_sum; // q に含まれるすべての項目の合計
  public:
  ConveyorQueue(int max_items) : max_items(max_items), total_sum(0) { }
  int TotalSum() {
    return total_sum;
  }
  void Shift(int num_shifted) {
    // 項目がシフトされすぎた場合に、キューをクリアする。
    if (num_shifted >= max_items) {
      q = queue<int>(); // clear the queue total_sum = 0;
      return;
    }
    // 必要な分だけ 0 をプッシュする。
    while (num_shifted > 0) {
      q.push(0);
      num_shifted--; }
      // 超過した項目はすべて落とす。 while (q.size() > max_items) { total_sum -= q.front();
      q.pop();
    }
  }
  void AddToBack(int count) {
    if (q.empty()) Shift(1); q.back() += count;
    total_sum += count;
  }
};

疑問：自分なら1パターン目のコードの改良に終始しそう⇒大きな構造の設計変更の発想のヒントは？

特に自分でデータの型を設計するなどはトレーニングが必要？

15.6 3つの解決策を比較する

  • 3つのクラスを使うことになった時間バケツのコードは、ほかの2つのコード行数よりもずっと多いが、パフォーマンスは高いし、設計に柔軟性がある。 これは好ましい変更である。

  • 問題を複数のクラスに分割すると、複数のクラスになったことが原因で複雑になることがある。 今回はクラスが「線形に」つながっていて、ユーザに公開されているクラスは1つだけになっている。 したがって、問題を分割することで、利点だけが得られるようになっている。

15.7 まとめ

MinuteHourCounterになるまでの手順をまとめた。

まずは、素朴な解決策から始めたが、速度とメモリの使用量について問題があった。

次に「ベルトコンベヤー」設計を試したが、この設計は速度とメモリ使用量の問題は解決できたが、高パフォーマンスのアプリケーションには適していなかった。

最終的な設計では、複数の下位問題に分割することで、ボトムアップで3つのクラスを作り、それぞれのクラスで下位問題を解決するようにした。

⚠️ **GitHub.com Fallback** ⚠️