「リーダブルコード」を読む (第15章「「分/時間カウンタ」を設計・実装する」)

「リーダブルコード」読書会。名著と呼ばれており、私も一度さっくりと読んだ。 ただし忘れていることもあるし、体系的に学びたいので読み直す。

例によってJupyter Notebookに書いてまとめをブログに張っていくことにする。

今回は最後の章「第15章「分・時間カウンタ」を設計・実装する」までをまとめた。 とりあえず、本書はここまで。

まとめるといっても、本書は言いたいことを非常に簡潔に要約しており、ほぼほぼそれを写経したようなものになっているが、まあ自分で手を動かさないと分からないということで。。。

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

---

第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: ベルトコンベヤー設計

1. 不要なデータを削除する。
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();
};

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

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

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

15.7 まとめ

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

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

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

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