はじめに

名著リーダブルコードの"15章「分/時間カウンタ」を設計・実装する"では、直近1分と60分のイベント総数を返すプログラムの作成を通し、書籍を締めくくっています。

この「分/時間カウンタ」のプログラムではリーダブルさに加え、プログラムのメンテナンス性とパフォーマンス改善の要素を意図した3つの実装を用意し、比較しています。

本記事では、Go言語で3つのカウンターを実装し、Goのベンチマークを使い、書籍の記載のようにパフォーマンス改善がされているかを検証します。

また、こちらにて本記事のソースコードを確認できます。

実行環境

macos: 10.13.6 High Sierra
go version: go1.11

プログラム

「分/時間カウンタ」のインターフェース

以下が実装対象の「分/時間カウンタ」のインターフェースです。

minutehourcounterinterface.go

package minutehourcounter

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

	// MinuteCount は直近60秒間の累積カウントを返す。
	MinuteCount() int

	// HourCount は直近3600秒間の累積カウントを返す。
	HourCount() int
}

コメントにあるように、MinuteHourCounterは直近1分間と直近1時間で発生したイベントの累積カウントを記録するものです。イベントを記録するAddメソッドと直近に記録されたカウント数を返すMinuteCountメソッドとHourCoutメソッドがあります。

その1 シンプルカウンター

シンプルカウンターでは、発生するイベントをEvent1構造体としてリストへ逐一追加し、総数取得の際にはリストをFor文で回してカウントします。

minutehourcounter1.go

package minutehourcounter

import "time"

type Event1 struct {
	count int
	time  int64
}

type MinuteHourCounter1 struct {
	events []Event1
}

func NewMinuteHourCounter1() *MinuteHourCounter1 {
	return &MinuteHourCounter1{}
}

func (c *MinuteHourCounter1) Add(count int) {
	c.events = append(c.events, Event1{count, time.Now().Unix()})
}

func (c *MinuteHourCounter1) MinuteCount() int {
	return c.CountSince(time.Now().Unix() - 60)
}

func (c *MinuteHourCounter1) HourCount() int {
	return c.CountSince(time.Now().Unix() - 3600)
}

func (c *MinuteHourCounter1) CountSince(cutoff int64) (count int) {
	for _, event := range c.events {
		if event.time <= cutoff {
			break
		}
		count += event.count
	}
	return count
}

この実装では下記の書籍の引用のように、パフォーマンスの問題があります。

・このクラスはすべてのイベントを保持している。つまり、メモリを無限に使用してしまうのだ！ MinuteHourCounterは、1時間よりも不要なイベントを自動的に削除するべきだ
・MinuteCountとHourCountが遅すぎる。CountSince()メソッドの処理時間はO(n)でありパフォーマンスが悪い。MinuteHourCounterは、Add()の呼び出しに対する値をminute_countとhour_countとで別々に保持するべきだ。

その2 ベルトコンベアー型カウンター

2つ目のベルトコンベアー型カウンターでは、1分版、1時間版でリストをそれぞれ用意し、1分後、1時間後の不要なイベントを削除し、メモリの無限増加を防いでいます。また、Counter構造体にて、minuteCount、hourCountと総数を保持するプロパティを用意しAddメソッド時にカウントすることで、MinuteCountとHourCountが呼ばれるたびにFor文を回すことを回避しています。

minutehourcounter2.go

package minutehourcounter

import "time"

type Event2 struct {
	count int
	time  int64
}

type MinuteHourCounter2 struct {
	minuteEvents []Event2
	hourEvents   []Event2
	minuteCount  int
	hourCount    int
}

func NewMinuteHourCounter2() *MinuteHourCounter2 {
	return &MinuteHourCounter2{}
}

func (c *MinuteHourCounter2) Add(count int) {
	nowSecs := time.Now().Unix()
	c.ShiftOldEvents(nowSecs)

	// 1分間のリストに流し込む
	c.minuteEvents = append(c.minuteEvents, Event2{count, nowSecs})

	c.minuteCount += count
	c.hourCount += count
}

func (c *MinuteHourCounter2) MinuteCount() int {
	c.ShiftOldEvents(time.Now().Unix())
	return c.minuteCount
}

func (c *MinuteHourCounter2) HourCount() int {
	c.ShiftOldEvents(time.Now().Unix())
	return c.hourCount
}

func (c *MinuteHourCounter2) ShiftOldEvents(nowSecs int64) {
	minuteAgo := nowSecs - 60
	hourAgo := nowSecs - 3600

	// 1分以上経過したイベントを'minuteCount'から'hourCount'へと移動する。
	// (1時間以上経過した古いイベントは次のループで削除する)
	for len(c.minuteEvents) > 0 && c.minuteEvents[0].time <= minuteAgo {
		c.hourEvents = append(c.hourEvents, c.minuteEvents[0])

		c.minuteCount -= c.minuteEvents[0].count
		c.minuteEvents = c.minuteEvents[1:]
	}

	// 1時間以上経過した古いイベントを'hour_events'から削除する
	for len(c.hourEvents) > 0 && c.hourEvents[0].time <= hourAgo {
		c.hourCount -= c.hourEvents[0].count
		c.hourEvents = c.hourEvents[1:]
	}
}

しかし、このベルトコンベアー型カウンターにもまだ以下の欠点があります。

1点目: まず、この設計には柔軟性がない。例えば、直近24時間のカウントを保持したいとする。すると、多くのコードに修正が必要になる。ShiftOldEvents()は、わずかに分と時間のデータのやり取りをしているだけの非常に密度の濃い関数である。
2点目: 次に、メモリの使用量が多い。高トラフィックのサーバが1秒間に100回もAdd()を呼び出したとしよう。直近1時間のデータをすべて保持しているので、約5MBのメモリが必要になる。Add()が呼び出される頻度に関係なく、MinuteHourCounterの使用するメモリは一定であるほうが良い。

その3 バケツ型カウンター

ベルトコンベアー型カウンターをさらに発展させ、s秒数分のイベント数を保管するようなN個のバケツ分のカウントを保持するTrailingBucketCounterインターフェースを実装します。さらにこの実装ではバケツの実態となるキューをより抽象的に扱うConveyorQueueインターフェースの実装を利用します。

minutehourcounter3.go

package minutehourcounter

import "time"

type MinuteHourCounter3 struct {
	minuteCounts TrailingBucketCounter
	hourCounts   TrailingBucketCounter
}

func NewMinuteHourCounter3() *MinuteHourCounter3 {
	m := NewRealTrailingBucketCounter( /*numBuckets*/ 60 /*secsPerBucket*/, 1)
	h := NewRealTrailingBucketCounter( /*numBuckets*/ 60 /*secsPerBucket*/, 60)
	return &MinuteHourCounter3{minuteCounts: m, hourCounts: h}
}

func (c *MinuteHourCounter3) Add(count int) {
	now := time.Now().Unix()
	c.minuteCounts.Add(count, now)
	c.hourCounts.Add(count, now)
}

func (c *MinuteHourCounter3) MinuteCount() int {
	now := time.Now().Unix()
	return c.minuteCounts.TrailingCount(now)
}

func (c *MinuteHourCounter3) HourCount() int {
	now := time.Now().Unix()
	return c.hourCounts.TrailingCount(now)
}

// TrailingBucketCounter は時間バケツN個のカウントを保持する。
type TrailingBucketCounter interface {
	Add(count int, now int64)

	// TrailingCount は最新の合計バケツ分の合計カウントを返す。
	TrailingCount(now int64) int
}

type RealTrailingBucketCounter struct {
	buckets         ConveyorQueue
	secsPerBucket   int64
	lastUpdatedTime int64
}

// NewTrailingBucketCounter3(30, 60)は、直近30分の時間バケツを追跡する。
func NewRealTrailingBucketCounter(numBuckets int, secsPerBucket int) *RealTrailingBucketCounter {
	b := NewRealConveyorQueue(numBuckets)
	spb := int64(secsPerBucket)
	now := time.Now().Unix()
	return &RealTrailingBucketCounter{buckets: b, secsPerBucket: spb, lastUpdatedTime: now}
}

func (tbc *RealTrailingBucketCounter) Add(count int, now int64) {
	tbc.update(now)
	tbc.buckets.AddToBack(count)
}

func (tbc *RealTrailingBucketCounter) TrailingCount(now int64) int {
	tbc.update(now)
	return tbc.buckets.TotalSum()
}

func (tbc *RealTrailingBucketCounter) update(now int64) {
	diffTime := now - tbc.lastUpdatedTime
	numShift := diffTime / tbc.secsPerBucket

	tbc.buckets.Shift(int(numShift))
	tbc.lastUpdatedTime = now
}

// ConveyorQueue は上限数を持ったキュー。古いデータは端から落ちる。
type ConveyorQueue interface {
	// AddToBack はキューの最後の値を増加する。
	AddToBack(count int)

	// Shift はキューの値を'numShift'分だけシフトする。
	// 新しい項目は0で初期化する。
	// 最古の項目はmax_items以下なら削除する。
	Shift(numShift int)

	// TotalSum は現在のキューに含まれる項目の合計値を返す。
	TotalSum() int
}

type RealConveyorQueue struct {
	queue    []int
	maxItems int
	totalSum int // My Note: totalSumを持たずTotalSumでは
	// 毎回queueのリストのSumを出すほうがコードはシンプルに
	// なるが、totalSumを持って合計を管理する方がパフォーマンスは良い。
}

func NewRealConveyorQueue(numQueue int) *RealConveyorQueue {
	queue := make([]int, numQueue)
	return &RealConveyorQueue{queue: queue, maxItems: numQueue}
}

func (qc *RealConveyorQueue) AddToBack(count int) {
	if len(qc.queue) < 1 {
		qc.queue = []int{0}
	}
	qc.queue[len(qc.queue)-1] += count
	qc.totalSum += count
}

func (qc *RealConveyorQueue) Shift(numShift int) {
	// numShiftがQueueの上限数より大きいときQueueを初期化する
	if numShift >= qc.maxItems {
		qc.queue = make([]int, len(qc.queue))
		qc.totalSum = 0
		return
	}

	// numShift分Queueの要素を減らした後、maxItems分を0の要素で埋める
	for i := 0; i < numShift; i++ {
		qc.totalSum -= qc.queue[0]
		qc.queue = qc.queue[1:] // Queue.Pop()
	}
	for len(qc.queue) < qc.maxItems {
		qc.queue = append(qc.queue, 0)
	}
}

func (qc RealConveyorQueue) TotalSum() int {
	return qc.totalSum
}

シンプルカウンターとベルトコンベアー型カウンターと比べ、コード量は増えましたが、直近10分間のカウンターなどの対応も、少ない変更で実装可能になります。さらに、精度を犠牲にしながらも(※1)、メモリ使用量をイベント数によらず一定に保つことができています。

※1: HourCountにおいてベルトコンベアー型カウンターでは平均0.5秒間分のイベント数の誤差が存在するのに対し、バケツ型カウンターでは平均30秒間分のイベント数の誤差が存在します。

比較表

以下に書籍記載の各カウンターごとの比較表を示します。

カウンター	コードの行数	HourCount()の計算量	メモリ使用量	HourCount()の誤差
シンプルカウンター	少	O(N)	無限に増える	1/3600
ベルトコンベアー型カウンター	中	O(1)	O(1時間のイベント数) 約5MB	1/3600
バケツ型カウンター	大	O(1)	O(バケツの数) 約500B	1/60

Goでのベンチマーク

ベンチマークコード

各カウンターのベンチマークを以下のコードでとります。

benchmark_test.go

package minutehourcounter

import (
	"testing"
)

func BenchmarkMinuteHourCounter1_Add(b *testing.B) {
	counter := NewMinuteHourCounter1()
	loadCounterAdd(b, counter)
}

func BenchmarkMinuteHourCounter2_Add(b *testing.B) {
	counter := NewMinuteHourCounter2()
	loadCounterAdd(b, counter)
}

func BenchmarkMinuteHourCounter3_Add(b *testing.B) {
	counter := NewMinuteHourCounter3()
	loadCounterAdd(b, counter)
}

func loadCounterAdd(b *testing.B, counter MinuteHourCounter) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		counter.Add(1)
	}
}

func BenchmarkMinuteHourCounter1_MinuteCount(b *testing.B) {
	counter := NewMinuteHourCounter1()
	loadCounterMinuteCount(b, counter)
}

func BenchmarkMinuteHourCounter2_MinuteCount(b *testing.B) {
	counter := NewMinuteHourCounter2()
	loadCounterMinuteCount(b, counter)
}

func BenchmarkMinuteHourCounter3_MinuteCount(b *testing.B) {
	counter := NewMinuteHourCounter3()
	loadCounterMinuteCount(b, counter)
}

func loadCounterMinuteCount(b *testing.B, counter MinuteHourCounter) {
	for i := 0; i < 10000; i++ {
		counter.Add(1)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		counter.MinuteCount()
	}
}

func BenchmarkMinuteHourCounter1_HourCount(b *testing.B) {
	counter := NewMinuteHourCounter1()
	loadCounterHourCount(b, counter)
}

func BenchmarkMinuteHourCounter2_HourCount(b *testing.B) {
	counter := NewMinuteHourCounter2()
	loadCounterHourCount(b, counter)
}

func BenchmarkMinuteHourCounter3_HourCount(b *testing.B) {
	counter := NewMinuteHourCounter3()
	loadCounterHourCount(b, counter)
}

func loadCounterHourCount(b *testing.B, counter MinuteHourCounter) {
	for i := 0; i < 10000; i++ {
		counter.Add(1)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		counter.HourCount()
	}
}

結果

$ go test -bench . -benchmem
goos: darwin
goarch: amd64
pkg: github.com/momotaro98/go-minute-hour-counter
BenchmarkMinuteHourCounter1_Add-4           	10000000	       114 ns/op	      82 B/op	       0 allocs/op
BenchmarkMinuteHourCounter2_Add-4           	20000000	       101 ns/op	      80 B/op	       0 allocs/op
BenchmarkMinuteHourCounter3_Add-4           	20000000	       116 ns/op	       0 B/op	       0 allocs/op
BenchmarkMinuteHourCounter1_MinuteCount-4   	  300000	      5387 ns/op	       0 B/op	       0 allocs/op
BenchmarkMinuteHourCounter2_MinuteCount-4   	20000000	        83.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkMinuteHourCounter3_MinuteCount-4   	20000000	       103 ns/op	       0 B/op	       0 allocs/op
BenchmarkMinuteHourCounter1_HourCount-4     	  300000	      5395 ns/op	       0 B/op	       0 allocs/op
BenchmarkMinuteHourCounter2_HourCount-4     	20000000	        81.6 ns/op	       0 B/op	       0 allocs/op
BenchmarkMinuteHourCounter3_HourCount-4     	20000000	        98.4 ns/op	       0 B/op	       0 allocs/op
PASS

Addメソッドについて、メモリ使用量がイベント数に依存するシンプルカウンター、ベルトコンベアー型カウンターが約80 B/opであるのに対し、メモリ使用量がイベントに依らないバケツ型カウンターでは0 B/op(実質無し)であることが確認できます。

また、シンプルカウンターのMinuteCountメソッドとHourCountメソッドについて、イベント数分のループをするためやはり遅いことがわかります。

参考

リーダブルコード