Mục tiêu của bài viết này là xây dựng một bảng xếp hạng đồng thời mạnh mẽ trong Go có thể: Quản lý hàng ngàn bản cập nhật đồng thời từ nhiều goroutines. Dịch vụ các truy vấn Top-N thường xuyên một cách hiệu quả. Duy trì các snapshots có thể dự đoán được của điểm số mặc dù viết đồng thời. Hãy thực tế và sẵn sàng sản xuất, bao gồm hướng dẫn về quy mô, sử dụng bộ nhớ và phần mở rộng. Chúng tôi sẽ cân bằng lý thuyết với thực tiễn thực hiện. bạn sẽ không chỉ nhìn thấy mã mà còn hiểu tại sao mỗi quyết định thiết kế lại quan trọng trong các khối lượng công việc đồng thời. Live leaderboards giới thiệu một số phức tạp: Tần số cao viết: Nhiều người dùng có thể được cập nhật cùng một lúc. khóa trên một bản đồ toàn cầu nhanh chóng trở thành chướng ngại vật. Hiệu quả Top-N truy vấn: sắp xếp toàn bộ tập dữ liệu tại mỗi ghi là không khả thi. Hiệu quả bộ nhớ: Leaderboards có thể chứa hàng trăm ngàn người dùng. Ảnh chụp nhanh nhất quán: Người dùng mong đợi truy vấn Top-N phản ánh trạng thái có ý nghĩa của bảng xếp hạng, ngay cả khi các bản cập nhật đang xảy ra. Sự kết hợp của viết đồng thời và đọc thường xuyên đòi hỏi việc sử dụng cẩn thận các nguyên thủy đồng bộ và cấu trúc dữ liệu của Go. Hiểu được vấn đề Một leaderboard thường hỗ trợ hai hoạt động chính: AddScore(userID string, score int): Lưu trữ điểm số mới cho một người dùng. Để đơn giản, chúng tôi sẽ theo dõi điểm số, không phải người dùng, có nghĩa là nhiều điểm số cao của cùng một người dùng được phép. Top(n int): Nhận được điểm số cao nhất. Ngoài ra còn có những cân nhắc hoạt động: Các bản cập nhật phải mở rộng với sự cạnh tranh. Các truy vấn Top-N phải hiệu quả, lý tưởng nhanh hơn O (tổng số người dùng đăng nhập tổng số người dùng). Khóa nên giảm thiểu tranh chấp, cho phép nhiều nhà văn tiến hành mà không chặn lẫn nhau. Thách thức cạnh tranh Viết tần số cao: Không có cấu trúc dữ liệu phân mảnh hoặc đồng thời nhận thức, mỗi bản cập nhật được serializes thông qua một khóa duy nhất. Hiệu quả Top-N truy vấn: Một cách tiếp cận ngây thơ sẽ là để sắp xếp tất cả người dùng cho mỗi truy vấn. Đối với 100.000 người dùng, điều này có thể mất hàng chục milliseconds mỗi truy vấn - không thể chấp nhận được cho các hệ thống trực tiếp đòi hỏi đáp ứng cấp độ millisecond. Hiệu quả bộ nhớ: Duy trì các cấu trúc phụ trợ như đống hoặc các mảng được sắp xếp cho mỗi người dùng đòi hỏi phải quản lý bộ nhớ cẩn thận. Snapshots nhất quán: Người dùng mong đợi bảng xếp hạng có ý nghĩa.Nếu truy vấn Top-N đọc các giá trị không nhất quán trên nhiều phân đoạn, nó có thể trả về các kết quả dao động hoặc không chính xác. Thiết kế Considerations Trước khi chúng ta bắt đầu mã hóa, chúng ta phải quyết định cách tổ chức cấu trúc dữ liệu để đáp ứng các yêu cầu này. Bản đồ đơn với Global Mutex type Leaderboard struct { mu sync.RWMutex scores map[string]int } : Đơn giản và dễ dàng để lý luận về. Pros Khả năng mở rộng kém trong các bản ghi nặng - tất cả các bản cập nhật được serialize thông qua một mutex. Cons Sử dụng trường hợp: concurrent thấp hoặc tập dữ liệu nhỏ. Sử dụng sync.Map đi đi cung cấp một bản đồ đồng thời với khóa-free đọc: sync.Map var leaderboard sync.Map leaderboard.Store("user123", 100) score, ok := leaderboard.Load("user123") : Pros Đọc không khóa cho phép nhiều goroutines để đọc cùng một lúc. Các chữ viết là nguyên tử và an toàn để sử dụng đồng thời. : Cons Iteration là yếu nhất quán. Viết thường xuyên làm giảm hiệu suất. Không tự nhiên hỗ trợ truy vấn Top-N hiệu quả, làm cho nó không tối ưu cho bảng xếp hạng trực tiếp. Thiết kế Sharded Map Để mở rộng quy mô với nhiều nhà văn, chúng tôi có thể chia bảng xếp hạng thành các mảnh. Mỗi mảnh có bản đồ và mutex riêng của nó. Điều này làm giảm sự tranh chấp khóa và cho phép cập nhật song song. Viết cho các mảnh khác nhau tiến hành độc lập. Đọc có thể xảy ra đồng thời trên các mảnh. Top-N queries merge per-shard kết quả. Thiết kế này đạt được sự đồng nhất cao trong khi giữ cho mã tương đối đơn giản, vì vậy chúng tôi sẽ gắn bó với nó cho việc thực hiện của chúng tôi. Heap-Based Top-N cho mỗi Shard Trong mỗi shard, chúng ta phải theo dõi các điểm số N hàng đầu một cách hiệu quả. Chúng ta có thể sắp xếp toàn bộ shard trên mỗi truy vấn, nhưng điều đó sẽ điên rồ. Hoặc chúng ta có thể theo dõi các điểm số N hàng đầu trong một danh sách được sắp xếp, sau đó một điểm số mới có thể được chèn (hoặc từ chối) trong thời gian O(N). . Lời bài hát: Top-N Min-Heap Một min-heap là một cây nhị phân hoàn chỉnh nơi giá trị của mỗi nút nhỏ hơn hoặc bằng với các giá trị của con của nó: Thuộc tính này làm cho nó hiệu quả để chiết xuất các yếu tố tối thiểu (rễ) và để chèn các yếu tố mới trong khi duy trì cấu trúc đống. Đó là một top-N min-heap bởi vì chúng tôi chỉ giữ các điểm số N hàng đầu trong đống. Khi một điểm số mới đi vào, nếu nó ít hơn gốc của đống, đó là điểm số N hàng đầu nhỏ nhất, chúng tôi từ chối nó. Nếu nó lớn hơn, chúng tôi thay thế gốc với điểm số mới (chúng tôi có thể làm điều này, bởi vì yếu tố gốc sẽ ra khỏi N hàng đầu) và re-heapify (tái cấu trúc đống). Điều này đảm bảo rằng chúng tôi luôn có điểm số N hàng đầu trong đống. Cách tiếp cận này cung cấp sự phức tạp của O(1) từ chối và O(log N) chèn. Biểu đồ này cho thấy những gì xảy ra trên insertion: Mỗi phân đoạn giữ một nhóm top-N cục bộ và Top-N toàn cầu được tính toán bằng cách sáp nhập các nhóm này. phương pháp này tránh sắp xếp toàn bộ tập dữ liệu trên mỗi truy vấn Top-N. Sharded Leaderboard thực hiện Với tất cả các lý thuyết dưới dây đai của chúng tôi, chúng ta hãy đến với nó! Bắn IDE yêu thích của bạn và bắt đầu với việc xác định cấu trúc shard và loại bảng dẫn đầu chính: // 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 thực hiện Tiếp theo, chúng tôi sẽ thực hiện cấu trúc top-N min-heap và các phương pháp để quản lý nó. Điều này bao gồm chèn, từ chối và thu thập các điểm N hàng đầu. Chúng tôi có thể thực hiện đống của riêng chúng tôi để tăng hiệu suất nhỏ, nhưng chỉ với chi phí tăng độ phức tạp - có lẽ trong một bài viết khác. 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) } } Đầu tiên, chúng ta phải thực hiện các , mà định nghĩa , , , và Sau đó, chúng tôi tạo ra một constructor Để bắt đầu, cuối cùng, các phương pháp xử lý việc chèn điểm số mới trong khi duy trì thuộc tính top-N: nếu đống không đầy, chúng tôi chỉ đơn giản là đẩy điểm số mới. nếu nó đầy và điểm số mới lớn hơn tối thiểu (rễ), chúng tôi thay thế gốc và re-heapify (tức là, chúng tôi gọi ) heap.Interface Len Less Swap Push Pop NewTopNMinHeap Add heap.Fix Shard Operations: Score Updates và Reads Mỗi phân đoạn nên phơi bày các phương pháp có thể thêm điểm số mới một cách an toàn và lấy snapshot N hàng đầu hiện tại của nó. đảm bảo rằng các bản cập nhật đồng thời cho shard là an toàn. 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 } khóa shard để viết, sau đó thêm điểm số vào đống bằng cách sử dụng phương pháp của heap mà chúng tôi đã xác định trước đó. AddScore Add khóa phần mảnh để đọc, và trả về một bản sao của phần mảnh mảnh để người gọi không thể vô tình sửa đổi phần mảnh bên trong. Top Sử dụng cho phép nhiều goroutines để đọc top-N cùng một lúc trong khi viết được serialized. RWMutex Bắt đầu với Leaderboard Bây giờ mỗi mảnh đang làm việc của nó, chúng ta có thể bắt đầu bảng xếp hạng với một số mảnh được chỉ định và kích thước top-N toàn cầu: // 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 } Chức năng này tạo ra một Trả về một con trỏ đảm bảo rằng tất cả goroutines hoạt động trên cùng một trường hợp leaderboard được chia sẻ, đó là điều cần thiết cho các bản cập nhật đồng thời. Leaderboard Thêm điểm số Khi chúng tôi thêm điểm số vào bảng xếp hạng, chúng tôi cần xác định bảng xếp hạng nào để cập nhật. Chúng tôi sử dụng hash FNV-1a của playerID để gán một người chơi cho một bảng xếp hạng, đảm bảo sự phân phối gần như đồng đều của người chơi trên các bảng xếp hạng. Điều này rất quan trọng để tránh sự biến dạng phân phối, có thể dẫn đến một số bảng xếp hạng bị quá tải trong khi những người khác đang bị thiếu sử dụng. lưu ý rằng cùng một ID người chơi sẽ luôn luôn lập bản đồ cho cùng một bảng xếp hạng, điều này đối với thiết kế hiện tại của chúng tôi không quan trọng, nhưng có thể quan trọng nếu sau này chúng tôi muốn hỗ trợ các hoạt động cho mỗi người chơi. // 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] } Với Bây giờ chúng ta có thể dễ dàng thực hiện các Phương pháp thêm điểm số vào bảng xếp hạng: 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) } Gọi để tìm đúng shard, sau đó thêm điểm số vào nó thông qua Mỗi mảnh xử lý khóa riêng của nó, vì vậy điều này quy mô với số lượng mảnh. AddScore getShard shard.AddScore Trở lại Top-N toàn cầu Bây giờ chúng ta có thể thêm điểm số, chỉ có một điều còn lại để làm: lấy điểm số top-N toàn cầu trên tất cả các mảnh vụn. Chúng ta có thể làm điều này bằng cách hợp nhất các mảnh vụn hàng đầu từ mỗi mảnh vụn. Vì mảnh vụn hàng đầu của mỗi mảnh vụn đã được sắp xếp (như một mảnh vụn), chúng ta có thể kết hợp chúng một cách hiệu quả bằng cách sử dụng một mảnh vụn tối đa để theo dõi tổng số mảnh vụn. (Đối với một số lượng rất lớn mảnh vụn, một mảnh vụn k-way phức tạp hơn có thể được thực hiện, nhưng đối với số mảnh vụn điển hình, cách tiếp cận này là đủ.) // 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 } Mỗi mảnh trả về một snapshot của top-N của nó, vì vậy chúng tôi không giữ khóa trên nhiều mảnh cùng một lúc. Chúng tôi chèn tất cả các mục top-N của mảnh vào một mảnh nhỏ tạm thời có kích thước n để duy trì top-N toàn cầu hiệu quả. Vì mảnh nhỏ lưu trữ điểm số top-N nhỏ nhất ở gốc, chúng tôi đảo ngược mảnh để trả về điểm số cao nhất đầu tiên. Kiểm tra những gì chúng tôi đã xây dựng Bây giờ chúng ta đã hoàn thành bảng xếp hạng của chúng tôi, chúng ta hãy xem nó hoạt động như thế nào. Đây là một chương trình thử nghiệm đơn giản cho thấy việc thêm điểm số và thu thập top-N cùng một lúc: // 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) } } Chương trình này tạo ra một bảng xếp hạng với 8 phần và một kích thước top-10. Nó sinh ra 50 goroutines, mỗi mô phỏng một cầu thủ cập nhật điểm số của họ 200 lần với các giá trị ngẫu nhiên. Đồng thời, một goroutine khác in các điểm số top-10 hiện tại mỗi 100 milliseconds. Bạn có thể chạy chương trình này với , sản lượng sẽ là một cái gì đó như thế này: 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 Kết luận Trong bài viết này, chúng tôi đã xây dựng một bảng xếp hạng trực tiếp đồng thời hiệu suất cao trong Go từ đầu.Bắt đầu từ vấn đề cốt lõi, chúng tôi đã thảo luận về những thách thức do viết tần số cao, truy vấn top-N hiệu quả và sự nhất quán của snapshot dưới sự đồng bộ. Chúng tôi đã khám phá nhiều lựa chọn thiết kế: Một bản đồ duy nhất với một mutex toàn cầu: đơn giản nhưng khả năng mở rộng kém. sync.Map: thích hợp cho đọc đồng thời, nhưng hạn chế cho các truy vấn top-N. Bảng xếp hạng phân mảnh với mỗi mảnh top-N min-heap: cách tiếp cận được lựa chọn của chúng tôi, cân bằng sự đồng nhất, hiệu quả và đơn giản. Chúng tôi đã thực hiện: Các cấu trúc cấp Shard với khóa đọc-viết. Top-N min-nhóm mỗi mảnh để chèn và loại bỏ nhanh chóng. Các truy vấn top-N toàn cầu kết hợp các đống trên từng mảnh một cách hiệu quả mà không chặn các bản cập nhật đồng thời. Một bản demo / test harness minh họa các bản cập nhật trực tiếp, viết đồng thời và snapshots bảng xếp hạng định kỳ. Chìa khóa takeaways: Sharding làm giảm xung đột khóa. nhiều goroutines có thể cập nhật điểm số cùng một lúc với việc chặn tối thiểu. Min-heaps duy trì top-N hiệu quả. chỉ có điểm phù hợp nhất được lưu trữ, giữ cho các hoạt động O(log N). Việc sáp nhập toàn cầu top-N là thực tế.Bằng cách kết hợp các đống mỗi mảnh, chúng tôi tránh sắp xếp toàn bộ tập dữ liệu và duy trì truy vấn nhanh. An toàn cạnh tranh là đơn giản với khóa mỗi phần. Bạn không cần các thuật toán không khóa phức tạp cho hầu hết các trường hợp sử dụng bảng dẫn đường trực tiếp. Thiết kế này mở rộng quy mô một cách quyến rũ.Tăng số lượng phân mảnh làm giảm sự tranh cãi, và cách tiếp cận dựa trên đống đảm bảo hiệu quả bộ nhớ. Với nền tảng này, bạn có thể mở rộng bảng xếp hạng để hỗ trợ: Dynamic top-N per shard hoặc multi-level leaderboards. Tích hợp với lưu trữ vĩnh viễn hoặc hệ thống phân tán cho các ứng dụng quy mô lớn hơn. Các số liệu bổ sung như timestamps, thứ hạng hoặc thành tựu. Cách tiếp cận thực tế, thực tế này cung cấp cho bạn một ý tưởng về cách xử lý tải công việc đồng thời trong thế giới thực một cách hiệu quả.Bây giờ bạn có các công cụ để triển khai, so sánh và mở rộng các hệ thống đồng thời sẵn sàng sản xuất trong Go. Mã cho bài viết này có sẵn trên GitHub: gkoos/article-leaderboard. Trang chủ / article-leaderboard
