この記事の目的は、Goで強力な並列リーダーボードを構築することです。 複数の goroutines から何千もの同時更新を処理します。 頻繁なトップ・N クエリを効率的に処理します。 共通の書き込みにもかかわらず予測可能なスナップショットを保持します。 スケーリング、メモリ使用、および拡張のためのガイドラインを含む、実用的で生産準備ができています。 私たちは、実践的な実装と理論のバランスをとります. あなたはコードを見るだけでなく、なぜそれぞれの設計決定が同時にワークロード下で重要であるかを理解します。 ライブリーダーボードは、いくつかの複雑性を導入します: High-frequency writes: 多くのユーザーが同時に更新される可能性があります. Locks on a global map quickly become bottlenecks. グローバルマップ上のロックはすぐにボトルネックになります。 効率的なトップ-N クエリ: すべての書き込み時にデータセット全体を分類することは不可能です。 メモリ効率: Leaderboards には数十万のユーザーが含まれる可能性があります。 一貫したスナップショット:ユーザーは、アップデートが発生している間でも、トップ-N クエリがリーダーボードの有意義な状態を反映することを期待します。 共通の書き込みと頻繁な読み込みの組み合わせは、Goの同期原理とデータ構造の慎重な使用を必要とします。 問題を理解する リーダーボードは通常、2つの主要な操作をサポートします。 AddScore(userID string, score int):ユーザーのための新しいスコアを格納します. 単純性のために、ユーザーではなくスコアを追跡します。 トップ(n int):トップN最高のスコアを取得します。 さらに、運用上の考慮点があります: アップデートは競合とともにスケールする必要があります。 トップ-N クエリは効率的で、理想的には O(ユーザログの合計ユーザ)よりも速い必要があります。 ロックは議論を最小限に抑え、複数の作家が互いにブロックすることなく進めることを可能にする。 競争の課題 High-Frequency Writes: Sharding or concurrency-aware data structures なしで、それぞれの更新は単一のロックを通じてシリアル化されます。 効率的なトップ-N クエリ: 1 つのクエリのすべてのユーザーを分類するのが天真なアプローチです. For 100,000 users, this can take tens of milliseconds per query - unacceptable for live systems that require millisecond-level responsiveness. メモリ効率: すべてのユーザのためのヘップや分類されたアレイなどの補助構造を維持するには、注意深いメモリ管理が必要です. Each additional shard or heap increases memory use linearly. 一貫したスナップショット:ユーザーは、トップN クエリが複数のスライドで不一致の値を読み取る場合、変動または間違った結果を返す可能性があります。 デザイン考慮事項 コードを始める前に、これらの要件を満たすためにデータ構造をどのように組織するかを決めなければなりません。 Single Map with Global Mutex(グローバル・ムテックス) type Leaderboard struct { mu sync.RWMutex scores map[string]int } : 単純で論理しやすい。 Pros : 重い書き込みの下でスケーラビリティが悪い - すべてのアップデートは1つのムテックスを通じてシリアル化されます。 Cons 使用例:低コンペレントまたは小規模なデータセット 利用 sync.Map GOの Lock-Free Reads を含む共通のマップを提供する: sync.Map var leaderboard sync.Map leaderboard.Store("user123", 100) score, ok := leaderboard.Load("user123") : Pros ロックフリーの読み込みにより、多くのゴロチンを同時に読み取ることができます。 文字は原子力であり、同時に使用するために安全です。 : Cons イテリアは一貫性が弱い。 頻繁に書くことは、パフォーマンスを低下させます。 効率的なトップ-N クエリを本質的にサポートしていないため、ライブ リーダーボードに最適ではない。 Sharded Map デザイン 複数の書き手でスケールするには、リーダーボードをシェアに分割することができます. 各シェアには独自のマップとムテックスがあります. This reduces lock contention and enables parallel updates. さまざまなカットに書くことは独立して進行します。 Reads は、shards で同時に発生する場合があります。 Top-N queries merge per-shard results. トップN queries merge per-shard results. このデザインは、コードを比較的単純に保つ一方で、高い共通性を達成するので、私たちは実装のためにそれに固執します。 Heap-Based Top-N per Shard それぞれのシールドで、我々は効率的にトップNスコアを追跡しなければなりません。我々はすべてのクエリで全体のシールドを分類することができますが、それは狂気になります。あるいは、我々は順番のリストでトップNスコアを追跡することができます、それから新しいスコアがO(N)時間に挿入されます(または拒否されます)。 . トップ > min-heap A min-heap is a complete binary tree where the value of each node is less than or equal to the values of its children. ミンホープは、それぞれのノードの値がその子どもの値より小さいまたは等しい完全なバイナリツリーです。 この属性により、最小の要素(ルート)を抽出し、集積構造を維持しながら新しい要素を挿入することが効率的になります。 それはトップNのマイナスホップであるため、我々はトップNのスコアだけをホップに保つ。新しいスコアが入るとき、それがトップNのスコアよりも小さい場合は、我々はそれを拒否します。もしそれが大きい場合は、我々は新しいスコアでルートを置き換える(我々はこれを行うことができます、なぜなら、ルート要素はトップNから出るでしょう)と再ヘアピファイ(ホップを再構築します)。これにより我々は常にトップNスコアを持っていることを保証します。 この図は、挿入時に起こることを示しています: 各シェアはローカルなトップ-N ホップを保持し、グローバルなトップ-N はこれらのホップを合併することによって計算されます。 Sharded Leaderboard Implementationについて 私たちのベルトの下にすべての理論を持って、それに到達しましょう! あなたの好きなIDEを点火し、シャード構造と主なリーダーボードタイプを定義することから始めましょう: // leaderboard/leaderboard.go package leaderboard import "sync" // Shard represents a portion of the leaderboard // It maintains a top-N min-heap of high scores type shard struct { mu sync.RWMutex topN *TopNMinHeap } type Leaderboard struct { shards []*shard n int // global top-N size } HEAP実施 次に、我々はそれを管理するためのトップ N ミン ステップの構造と方法を実装する。これには、トップ N スコアの挿入、拒否、および回収が含まれます。 私たちは、小さなパフォーマンスの向上のために独自の積み重ねを実装することができますが、複雑性の増加の代償でしかありません - もしかしたら別の記事で。 container/heap // leaderboard/topnminheap.go package leaderboard import ( "container/heap" ) // ScoreEntry represents a score and its associated player. type ScoreEntry struct { PlayerID string Score int } // TopNMinHeap is a min-heap that stores the top-N high scores with player IDs. type TopNMinHeap struct { scores []ScoreEntry maxN int } // Len implements heap.Interface func (h TopNMinHeap) Len() int { return len(h.scores) } // Less implements heap.Interface (min-heap) func (h TopNMinHeap) Less(i, j int) bool { return h.scores[i].Score < h.scores[j].Score } // Swap implements heap.Interface func (h TopNMinHeap) Swap(i, j int) { h.scores[i], h.scores[j] = h.scores[j], h.scores[i] } // Push implements heap.Interface func (h *TopNMinHeap) Push(x any) { h.scores = append(h.scores, x.(ScoreEntry)) } // Pop implements heap.Interface func (h *TopNMinHeap) Pop() any { old := h.scores n := len(old) x := old[n-1] h.scores = old[:n-1] return x } // NewTopNMinHeap creates a TopNMinHeap with a specified maximum size. func NewTopNMinHeap(maxN int) *TopNMinHeap { return &TopNMinHeap{ scores: make([]ScoreEntry, 0, maxN), maxN: maxN, } } // Add inserts a new score into the heap, maintaining the top-N property. func (h *TopNMinHeap) Add(playerID string, score int) { entry := ScoreEntry{PlayerID: playerID, Score: score} if h.Len() < h.maxN { heap.Push(h, entry) } else if score > h.scores[0].Score { h.scores[0] = entry heap.Fix(h, 0) } } まず、我々は、その実施を 定義するもの で、 で、 で、 そして、 その後、我々は建設者を作る。 初期化を図るには、最後に、 方法は、トップNの属性を維持しながら新しいスコアを挿入することに取り組んでいます: 積み重ねが満たされていない場合、我々は単に新しいスコアを押します。 ( ) heap.Interface Len Less Swap Push Pop NewTopNMinHeap Add heap.Fix Shard Operations: Score Updates and Reads(シェード・オペレーション:スコア・アップデートとリース) 各シェードは、安全に新しいスコアを追加し、現在のトップNスナップショットを取得する方法を露出する必要があります。 shard への同時更新が安全であることを保証します。 mu // leaderboard/leaderboard.go ... // AddScore adds a new score to the shard's top-N heap. func (s *shard) AddScore(playerID string, score int) { s.mu.Lock() defer s.mu.Unlock() s.topN.Add(playerID, score) } // Top returns a snapshot of the top-N scores for this shard. func (s *shard) Top() []ScoreEntry { s.mu.RLock() defer s.mu.RUnlock() // Return a copy to avoid exposing internal slice top := make([]ScoreEntry, len(s.topN.scores)) copy(top, s.topN.scores) return top } shard を書き込むためにロックし、その後、スコアを使用して heap に追加します。 先ほど定義したハーフの方法。 AddScore Add 読み込みのためのシェードをロックし、呼び出し者が内部のシェープを偶然に変更できないように、ヒップシリーズのコピーを返します。 Top 利用 複数のgoroutinesがトップNを同時に読み取ることを可能にし、書き込みが序列化される。 RWMutex リーダーボードの初期化 それぞれのシェアが自分のことをしているので、指定されたシェア数とグローバルトップNサイズでリーダーボードを初期化することができます。 // leaderboard/leaderboard.go // NewLeaderboard creates a sharded leaderboard with `numShards` shards and global top-N size `n`. func NewLeaderboard(numShards, n int) *Leaderboard { lb := &Leaderboard{ shards: make([]*shard, numShards), n: n, } for i := 0; i < numShards; i++ { lb.shards[i] = &shard{ topN: NewTopNMinHeap(n), } } return lb } この機能はA 指定されたシェア数で、それぞれが独自のトップ-N ミン セットで初期化され、ポインターを返すと、すべての goroutines が同じ共有リーダーボードインスタンスで動作することを保証します。 Leaderboard 追加スコア プレーヤーIDのFNV-1aハッシュを使用してプレーヤーをシールドに割り当てると、これはシールドの間でプレイヤーのほぼ均一な分布を確保するためです。これは、一部のシールドが過剰に使用され、他の部分が過剰に使用される可能性がある分布の歪みを避けるために重要です。同じプレーヤーIDが常に同じシールドにマッピングすることに注意してください。 // leaderboard/leaderboard.go import "hash/fnv" ... // getShard returns the shard for a given playerID. func (lb *Leaderboard) getShard(playerID string) *shard { h := fnv.New32a() h.Write([]byte(playerID)) idx := int(h.Sum32()) % len(lb.shards) return lb.shards[idx] } 同 今では簡単に実施できるのが、 リーダーボードにスコアを追加する方法: getShard AddScore // leaderboard/leaderboard.go // AddScore adds a new score to the appropriate shard. func (lb *Leaderboard) AddScore(playerID string, score int) { s := lb.getShard(playerID) s.AddScore(playerID, score) } 電話 正しいシェードを見つけるには、それからスコアをそれに追加します。 各シェードは独自のロックを処理するので、これはシェードの数でスケールします。 AddScore getShard shard.AddScore グローバルトップ-N すでに得点を追加できるので、残すべきことは、すべてのシェアのグローバルトップNスコアを取得することです。我々は、各シェアのトップNスコアを合併することによってこれを行うことができます。各シェアのトップNがすでに分類されているので(ミンシェアとして)、我々は、全体トップNを追跡するためにマックスシェアを使用してそれらを効率的に組み合わせることができます。 // leaderboard/leaderboard.go // Top returns the global top-N across all shards. func (lb *Leaderboard) Top() []ScoreEntry { // Temporary heap to compute global top-N globalHeap := NewTopNMinHeap(lb.n) for _, s := range lb.shards { shardTop := s.Top() // thread-safe snapshot for _, entry := range shardTop { globalHeap.Add(entry.PlayerID, entry.Score) } } // Copy to slice top := make([]ScoreEntry, len(globalHeap.scores)) copy(top, globalHeap.scores) // Sort descending (highest score first) for i, j := 0, len(top)-1; i < j; i, j = i+1, j-1 { top[i], top[j] = top[j], top[i] } return top } 各シェードは、トップNのスナップショットを返しますので、複数のシェードを同時にロックしないでください。我々は、グローバルトップNを効率的に維持するために、すべてのシェードトップNのエントリを、サイズnの一時的なミンシェープに挿入します。 わたしたちが作ったものをテスト リードボードを完了した今、これがどのように機能するかを見てみましょう. ここでは、スコアを追加し、トップNを同時に取得することを示す簡単なテストプログラムです: // main.go package main import ( "fmt" "math/rand" "sync" "time" "./leaderboard" ) func main() { const ( numShards = 8 topN = 10 numPlayers = 50 numUpdates = 200 updateDelay = 10 * time.Millisecond ) lb := leaderboard.NewLeaderboard(numShards, topN) var wg sync.WaitGroup // Spawn concurrent score updates for i := 0; i < numPlayers; i++ { wg.Add(1) playerID := fmt.Sprintf("player%02d", i) go func(pid string) { defer wg.Done() for j := 0; j < numUpdates; j++ { score := rand.Intn(50000) lb.AddScore(pid, score) time.Sleep(updateDelay) } }(playerID) } // Spawn a goroutine to print live top-N periodically done := make(chan struct{}) go func() { ticker := time.NewTicker(100 * time.Millisecond) defer ticker.Stop() for { select { case <-ticker.C: top := lb.Top() fmt.Println("Top Scores:") for i, entry := range top { fmt.Printf("%2d: %s = %d\n", i+1, entry.PlayerID, entry.Score) } fmt.Println("-----") case <-done: return } } }() // Wait for all updates to finish wg.Wait() close(done) // Print final top-N fmt.Println("Final Top Scores:") top := lb.Top() for i, entry := range top { fmt.Printf("%2d: %s = %d\n", i+1, entry.PlayerID, entry.Score) } } このプログラムは、8つのシェアとトップ10のサイズを持つリーダーボードを作成します。 それは50のゴロチンを産み、それぞれがランダム値で200回のスコアを更新するプレイヤーをシミュレートします。同時に、別のゴロチンは、現在のトップ10のスコアを100ミリ秒ごとに印刷します。 あなたはこのプログラムを実行することができます。 出力はこんなものになります: go run main.go Top Scores: 1: player05 = 49830 2: player07 = 49873 3: player46 = 49966 4: player24 = 49800 5: player25 = 49961 6: player10 = 49802 7: player30 = 49812 8: player02 = 49726 9: player19 = 49750 10: player46 = 49718 ----- ... ----- Final Top Scores: 1: player10 = 49971 2: player45 = 49977 3: player00 = 49992 4: player40 = 49979 5: player29 = 49990 6: player19 = 49967 7: player46 = 49966 8: player18 = 49974 9: player25 = 49961 10: player39 = 49960 結論 この記事では、コアの問題から始め、高周波の書き込み、効率的なトップNクエリ、およびスナップショットの一致性による課題について議論しました。 さまざまなデザインオプションを検討しました: グローバルムテックスを持つ単一の地図:シンプルだが、スケーラビリティが低い。 sync.Map: 同時に読み取るのに適していますが、トップN クエリに限定されます。 Sharded leaderboard with per-shard top-N min-heaps: our chosen approach, balancing concurrence, efficiency, and simplicity. シェアードのリーダーボード:私たちの選択したアプローチ、バランスを取る共通性、効率性、シンプルさ。 実施しました: Shard-level structures with read-writing locks シェアードレベルの構造 Top-N min-heaps per shard for fast insertion and rejection. スピードアップと拒絶のためのスピードアップ。 Global top-N queries that merge per-shard heads efficiently without blocking concurrent updates. グローバルトップNクエリは、同時更新をブロックすることなく、シェールドホップを効率的に統合します。 A demo/test harness illustrating live updates, concurrent writes, and periodic leaderboard snapshots. ライブアップデート、並行書き込み、および定期的なリーダーボードのスナップショットを示す。 Key takeaways : Sharding はロック コンテストを減らします. Multiple goroutines can update scores simultaneously with minimal blocking. Sharding は、ロック コンテストを減らします。 Min-heaps は、トップ-N を効率的に維持します. Only the most relevant scores are stored, keeping operations O(log N). グローバルトップNの合併は実用的です. per-shard ホップを組み合わせることにより、データセット全体の分類を回避し、迅速なクエリを維持します。 競争セキュリティは、per-shard ロックでシンプルで、ほとんどのライブ リーダーボードの使用ケースに複雑なロックフリーアルゴリズムは必要ありません。 このデザインは優雅にスケールします. シェアの数を増やすことで議論が低下し、バックベースのアプローチはメモリ効率を確保します。 この財団を使用すると、リーダーボードをサポートするように拡張できます: シールドまたはマルチレベルのリーダーボードごとにダイナミックトップN。 より大規模なアプリケーションのための永続的なストレージまたは分散システムとの統合。 タイムスタンプ、ランク、または業績などの追加メトリクス。 この実践的で実践的なアプローチは、実世界の同期ワークロードを効率的に処理する方法についてのアイデアを提供します. You now have the tools to implement, benchmark, and extend production-ready concurrent systems in Go. この記事のコードは GitHub で入手できます: gkoos/article-leaderboard. gkoos / 記事リーダーボード
