はじめに
株式会社エブリーでDELISH KITCHEN事業のバックエンドエンジニアをしている、GopherのYuki（@YukiBobier）です。現在は主に広告サービスを担当しています。
当社の広告サービスには店頭サイネージというものがあり、サーバーサイドはGoで実装されています。先日、このサービスの空き広告枠検索アルゴリズムを改善しました。その際に、Goのデータ構造と上手に付き合うことでヒープ使用量を改善できることを実感しました。
本記事では、特に効果があった2つの手法を紹介します。
いきさつ
当社の店頭サイネージは、スーパーの店頭でレシピを放映するのみならず、広告を放映することもできます。店頭サイネージには広告を放映できる時間的な枠が定められており、その枠を必要な数だけ占めるかたちで広告を登録します。したがって、広告を登録する際には、希望するサイネージ×日時に十分な空き枠があるかどうかを確認する必要があります。この時に使用されるのが、空き広告枠検索アルゴリズムです。
従来の空き広告枠検索アルゴリズムは、広告配信期間に比例してDBへのI/Oが多発するものでした。他方で、サービスとしては広告配信期間の単位をより細かくしたい要求があり、これを叶えることはI/Oのさらなる増加を意味しました。そこで、広告配信期間とI/Oの頻度が相関しないアルゴリズムに改善することになりました。
アルゴリズム改善の結果、あるベンチマークテストでは、DBへのI/Oは一定して1回に、さらに実行時間は従来の1/10以下にまで改善されました。しかし、DBからごそっと取得したデータをメモリに乗せて集計するため、ヒープ使用量は従来の40倍に増加しました。ヒープ使用量の増加はGCすなわち"stop-the-world"の頻度を高めてしまいます。そこで、さらにこのアルゴリズムのヒープ使用量を改善することになりました。
その際に、Goのデータ構造と上手に付き合うことでヒープ使用量を改善できることを実感しました。次節から、特に効果があった手法を紹介していきます。
#1:mapをmake関数で作成するとき第2引数sizeを渡す
やったこと
改善後のアルゴリズムでは、DBから取得したデータを集計するためのデータ構造として2重のmapを採用していました（map[string]map[string]int8）。これは、サイネージ×日時ごとの広告枠空き状況を保持するのに都合が良かったからです。
map[string]map[string]int8{ "2ab91c5f-ac7f-46c8-8040-28d265c71591": { "2023-10-27 00:00:00": 2, "2023-10-28 00:00:00": 0, "2023-10-29 00:00:00": 2, "2023-10-30 00:00:00": 3, ... .. . }, "e3a3ddd9-96b9-43df-a659-574b2f768ba8": { "2023-10-27 00:00:00": 1, "2023-10-28 00:00:00": 0, "2023-10-29 00:00:00": 2, "2023-10-30 00:00:00": 7, ... .. . }, ... .. . }
mapはmake関数で作成するとき、第2引数sizeを渡すことができます。最終的にmapに保持することになるであろう要素数をsizeに渡すようにしたところ、ヒープ使用量が37%削減されました。
解説
runtimeパッケージによれば、mapは”バケット”の配列を基底とするハッシュテーブルです。バケットとは、キーと値のペアを8個まで保持できる構造です。
mapはより多くの要素を保持するために拡大します。つまり、mapに要素を追加することを引き金として、より大きな基底の作成と全要素のコピーが発生することがあります。不要になった元の基底はGCの対象となります。これはアプリケーションのパフォーマンスにとって小さくないペナルティです。
この点、mapをmake関数で作成するとき第2引数sizeに数値を渡すと、その数の要素を保持するのに十分な大きさの基底を持つmapが作成されます。要するに、少なくとも要素数がsizeに満たないうちは、mapの拡大を抑制できるということです。
そのインパクトを実際にコードで確認してみましょう。まずはsizeを渡さない場合のヒープ使用量を計測します（Go Playground）。
package main import ( "fmt" "runtime" "runtime/debug" ) const count = 1_000_000 func init() { debug.SetGCPercent(-1) // GCが自動で実行されないようにする } func main() { start := allocatedMB() // 開始時のヒープ使用量 m := make(map[int]struct{}) afterMake := allocatedMB() // map作成後のヒープ使用量 for i := 0; i < count; i++ { m[i] = struct{}{} } afterAdd := allocatedMB() // mapに要素を追加した後のヒープ使用量 runtime.GC() // GCを手動で実行する afterGC := allocatedMB() // GCが実行された後のヒープ使用量 runtime.KeepAlive(m) // mapがGCの対象にならないようにする fmt.Printf("作成直後のmapのヒープ使用量: %dMB\n", afterMake-start) fmt.Printf("要素追加後のmapのヒープ使用量: %dMB\n", afterAdd-start) fmt.Printf("GCされたヒープ量: %dMB\n", afterAdd-afterGC) fmt.Printf("最終的なmapのヒープ使用量: %dMB\n", afterGC-start) } func allocatedMB() uint64 { var ms runtime.MemStats runtime.ReadMemStats(&ms) return ms.Alloc / 1024 / 1024 }
次のような結果が得られるはずです。mapが作成直後の0MBから21MBに拡大し、その間に24MBの”ごみ”がヒープに生じたことがわかります。
作成直後のmapのヒープ使用量: 0MB 要素追加後のmapのヒープ使用量: 45MB GCされたヒープ量: 24MB 最終的なmapのヒープ使用量: 21MB
次にsizeを渡す場合です（Go Playground）。
package main import ( "fmt" "runtime" "runtime/debug" ) const count = 1_000_000 func init() { debug.SetGCPercent(-1) // GCが自動で実行されないようにする } func main() { start := allocatedMB() // 開始時のヒープ使用量 m := make(map[int]struct{}, count) afterMake := allocatedMB() // map作成後のヒープ使用量 for i := 0; i < count; i++ { m[i] = struct{}{} } afterAdd := allocatedMB() // mapに要素を追加した後のヒープ使用量 runtime.GC() // GCを手動で実行する afterGC := allocatedMB() // GCが実行された後のヒープ使用量 runtime.KeepAlive(m) // mapがGCの対象にならないようにする fmt.Printf("作成直後のmapのヒープ使用量: %dMB\n", afterMake-start) fmt.Printf("要素追加後のmapのヒープ使用量: %dMB\n", afterAdd-start) fmt.Printf("GCされたヒープ量: %dMB\n", afterAdd-afterGC) fmt.Printf("最終的なmapのヒープ使用量: %dMB\n", afterGC-start) } func allocatedMB() uint64 { var ms runtime.MemStats runtime.ReadMemStats(&ms) return ms.Alloc / 1024 / 1024 }
次のような結果が得られるはずです。mapは作成直後から21MBの十分な容量を持ち、拡大する必要がないのでヒープに”ごみ”は生じませんでした。
作成直後のmapのヒープ使用量: 21MB 要素追加後のmapのヒープ使用量: 21MB GCされたヒープ量: 0MB 最終的なmapのヒープ使用量: 21MB
mapをmake関数で作成するとき第2引数sizeを渡すと、これだけのヒープ使用量の改善につながります。
#2:（可能なら）mapをsliceで代用する
やったこと
サイネージ×日時ごとの広告枠空き状況を保持する2重のmap（map[string]map[string]int8）は、外側のキーがUUIDで、内側のキーが等差な日時でした。ですので内側のmapは、インデックスiに”最初の日時+公差×i”の日時の広告枠空き状況が保持されたsliceで代用できました（[]int8）。
map[string][]int8{ "2ab91c5f-ac7f-46c8-8040-28d265c71591": {2, 0, 2, 3, ...}, "e3a3ddd9-96b9-43df-a659-574b2f768ba8": {1, 0, 2, 7, ...}, ... .. . }
#1に加えてこれをしたところ、ヒープ使用量が90%削減されました。
解説
まずは、mapとsliceのヒープ使用量の違いが顕著であることを計測によって示します（Go Playground）。
package main import ( "fmt" "runtime" "runtime/debug" ) const count = 1_000_000 func init() { debug.SetGCPercent(-1) // GCが自動で実行されないようにする } func main() { start := allocatedMB() // 開始時のヒープ使用量 _ = make(map[string]int8, count) afterMakeMap := allocatedMB() // map作成後のヒープ使用量 _ = make([]int8, 0, count) afterMakeSlice := allocatedMB() // slice作成後のヒープ使用量 fmt.Printf("mapのヒープ使用量: %dMB\n", afterMakeMap-start) fmt.Printf("sliceのヒープ使用量: %dMB\n", afterMakeSlice-afterMakeMap) } func allocatedMB() uint64 { var ms runtime.MemStats runtime.ReadMemStats(&ms) return ms.Alloc / 1024 / 1024 }
次のような結果が得られるはずです。両者のヒープ使用量には顕著な差が見られます。
mapのヒープ使用量: 40MB sliceのヒープ使用量: 1MB
なぜこのような差が見られるのでしょうか？ もう少し深掘りしてみましょう。
次に示すのは、様々な型のsliceとmapのヒープ使用量を計測するコードです（Go Playground）。
package main import ( "fmt" "runtime" "runtime/debug" ) const count = 1_000_000 func init() { debug.SetGCPercent(-1) // GCが自動で実行されないようにする } func main() { start := allocatedMB() // 開始時のヒープ使用量 _ = make([]struct{}, count) afterStructSlice := allocatedMB() // []struct{}作成後のヒープ使用量 _ = make([]int8, count) afterInt8Slice := allocatedMB() // []int8作成後のヒープ使用量 _ = make(map[struct{}]struct{}, count) afterStructStruct := allocatedMB() // map[struct{}]struct{}作成後のヒープ使用量 _ = make(map[string]struct{}, count) afterStringStruct := allocatedMB() // map[string]struct{}作成後のヒープ使用量 _ = make(map[struct{}]int8, count) afterStructInt8 := allocatedMB() // map[struct{}]int8{}作成後のヒープ使用量 _ = make(map[string]int8, count) afterStringInt8 := allocatedMB() // map[string]int8{}作成後のヒープ使用量 fmt.Printf("[]struct{}のヒープ使用量: %dMB\n", afterStructSlice-start) fmt.Printf("[]int8のヒープ使用量: %dMB\n", afterInt8Slice-afterStructSlice) fmt.Printf("map[struct{}]struct{}のヒープ使用量: %dMB\n", afterStructStruct-afterInt8Slice) fmt.Printf("map[string]struct{}のヒープ使用量: %dMB\n", afterStringStruct-afterStructStruct) fmt.Printf("map[struct{}]int8{}のヒープ使用量: %dMB\n", afterStructInt8-afterStringStruct) fmt.Printf("map[string]int8{}のヒープ使用量: %dMB\n", afterStringInt8-afterStructInt8) } func allocatedMB() uint64 { var ms runtime.MemStats runtime.ReadMemStats(&ms) return ms.Alloc / 1024 / 1024 }
次のような結果が得られるはずです。
[]struct{}のヒープ使用量: 0MB
[]int8のヒープ使用量: 1MB
map[struct{}]struct{}のヒープ使用量: 4MB
map[string]struct{}のヒープ使用量: 38MB
map[struct{}]int8{}のヒープ使用量: 6MB
map[string]int8{}のヒープ使用量: 41MB
この結果から次のことがわかります。
mapは要素ごとにオーバーヘッドが存在し、それは空の要素（struct{}）であっても避けられない- ひとつ前のコードで
mapとsliceのヒープ使用量に顕著な差が見られたのは、キーの型がstringだったから
mapをsliceで代用することで、キーがstringのような大きな型であった場合には、ヒープ使用量の顕著な改善につながります。そうでなくても、1要素ごとのオーバーヘッドを回避する効果は少なくとも得られます。
補足
mapをsliceで代用できるかどうかの判断について補足します。
まず大前提として、用途によって判断基準も結論も異なります。総合的にみてmapの方が良いことや、mapでなければならないことは大いにあり得ますし、むしろsliceで代用できることの方が稀かもしれません。その上で、判断の一例を示します。
mapの代表的な特徴は、高速なルックアップです。公式に言明はされていませんが、そのパフォーマンスはO(1)であることが実装から窺い知れます。ですので、同等のパフォーマンスでsliceをルックアップできるかどうかがひとつの判断基準になると思います。本件の場合は下のようにすることで、ある日時に対応するインデックスを”(日時-最初の日時)/公差”で求めることができます。したがってルックアップのパフォーマンスはO(1)なので、mapをsliceで代用できました。
// 等差な日時をキーに持つmap { "2023-10-27 00:00:00": 2, "2023-10-28 00:00:00": 0, "2023-10-29 00:00:00": 2, "2023-10-30 00:00:00": 3, ... .. . } // インデックス`i`が”最初の日時+公差×`i`”の日時に対応するslice {2, 0, 2, 3, ...}
その他のmapの特徴として、キーの重複を許さないことが挙げられます。そのため、他言語における”Set”のようにmapを使用することができます。この場合はsliceで代用することは難しいでしょう（Go Playground）。
package main import "fmt" type node struct { next *node } func main() { node3 := node{} node2 := node{next: &node3} node1 := node{next: &node2} node3.next = &node1 visited := make(map[*node]struct{}) for n := &node1; n.next != nil; n = n.next { if _, ok := visited[n]; ok { fmt.Println("ループしてます！") return } visited[n] = struct{}{} } fmt.Println("ループしてません！") }
こういったmapの特徴を必要としない場合には、sliceで代用できる可能性は高いと思います。
おわりに
もしGoで多量のヒープ使用が観測されるようでしたら、データ構造に着目することが改善の糸口となるかもしれません。
ちなみに、本記事で語った知見は『100 Go Mistakes and How to Avoid Them』から学んだところが大きいです。とても勉強になりますし、最近は邦訳も出たので、ぜひ読んでみてください。
