L'objectif de cet article est de construire un tableau de bord concurrentiel robuste dans Go qui peut: Gérer des milliers de mises à jour simultanées à partir de plusieurs goroutines. Servir fréquemment les requêtes Top-N efficacement. Maintenir des snapshots prévisibles des scores malgré les écrits concurrents. Soyez pratique et prête à la production, y compris des instructions sur l'évolutivité, l'utilisation de la mémoire et les extensions. Nous équilibrerons la théorie avec la mise en œuvre pratique. Vous verrez non seulement le code, mais vous comprendrez également pourquoi chaque décision de conception compte dans des charges de travail simultanées. Les leaderboards en direct introduisent plusieurs complexités : Écriture à haute fréquence: De nombreux utilisateurs peuvent être mis à jour simultanément. Les verrous sur une carte mondiale deviennent rapidement des barrières. Les requêtes Top-N efficaces : il n’est pas possible de trier l’ensemble de données à chaque écriture. Efficacité de la mémoire : Leaderboards peuvent contenir des centaines de milliers d’utilisateurs. Instantanés cohérents : les utilisateurs s’attendent à ce que la requête Top-N reflète un état significatif du tableau de bord, même lorsque des mises à jour se produisent. La combinaison d'écriture concomitante et de lecture fréquente nécessite l'utilisation minutieuse des primitifs de synchronisation et des structures de données de Go. Comprendre le problème Un leaderboard prend généralement en charge deux opérations principales : AddScore(userID string, score int): stocke un nouveau score pour un utilisateur. Pour simplifier, nous allons suivre les scores, pas les utilisateurs, ce qui signifie que plusieurs scores élevés par le même utilisateur sont autorisés. Top(n int): Récupère le top N des scores les plus élevés. En outre, il y a des considérations opérationnelles: Les mises à jour doivent évoluer avec la concurrence. Les requêtes Top-N doivent être efficaces, idéalement plus rapides que O (total d’utilisateurs enregistrant le total d’utilisateurs). Les verrous devraient minimiser les contentieux, permettant à plusieurs écrivains de procéder sans se bloquer mutuellement. Les défis de la concurrence Écrits à haute fréquence : sans structures de données fragmentées ou conscientes de la concurrence, chaque mise à jour est sérialisée à travers une seule serrure. Une approche naïve serait de trier tous les utilisateurs pour chaque requête. Pour 100 000 utilisateurs, cela peut prendre des dizaines de millisecondes par requête - inacceptable pour les systèmes en direct qui nécessitent une réactivité au niveau des millisecondes. Efficacité de la mémoire : le maintien de structures auxiliaires telles que des ensembles ou des ensembles triés pour chaque utilisateur nécessite une gestion minutieuse de la mémoire. Snapshots cohérents : les utilisateurs s’attendent à ce que le tableau de bord donne du sens. Si une requête Top-N lit des valeurs incohérentes sur plusieurs tranches, elle peut renvoyer des résultats fluctuants ou incorrects. Considérations de conception Avant de commencer à coder, nous devons décider comment organiser les structures de données pour répondre à ces exigences. Carte unique avec Global Mutex type Leaderboard struct { mu sync.RWMutex scores map[string]int } : Simple et facile à raisonner. Pros Mauvaise évolutivité dans les écrans lourds - toutes les mises à jour sont sérialisées à travers un seul mutex. Cons Cas d'utilisation : faible concurrence ou petits ensembles de données. Utiliser sync.Map Go’s est fournit une carte concurrentielle avec des lectures sans verrouillage: sync.Map var leaderboard sync.Map leaderboard.Store("user123", 100) score, ok := leaderboard.Load("user123") : Pros Les lectures sans verrouillage permettent de lire plusieurs goroutines en même temps. Les lettres sont atomiques et sûres pour une utilisation concomitante. : Cons L’iteration est faiblement cohérente. L'écriture fréquente réduit la performance. Ne prend pas en charge des requêtes Top-N efficaces, ce qui le rend suboptimal pour les tableaux de bord en direct. Design de cartes Sharded Pour l'échelle avec plusieurs écrivains, nous pouvons diviser le tableau de bord en morceaux. Chaque morceau a sa propre carte et mutex. Cela réduit la contention de verrouillage et permet des mises à jour parallèles. L'écriture à différentes tranches se déroule de manière indépendante. Les lectures peuvent se produire simultanément entre les tranchées. Les requêtes Top-N combinent les résultats par shard. Cette conception obtient une concurrence élevée tout en gardant le code relativement simple, de sorte que nous nous attacherons à elle pour notre mise en œuvre. Heap-Based Top-N par Shard Dans chaque fragment, nous devons suivre efficacement les meilleurs scores N. Nous pourrions trier l'ensemble du fragment sur chaque requête, mais cela serait fou. Ou nous pourrions suivre les meilleurs scores N dans une liste ordonnée, puis un nouveau score pourrait être inséré (ou rejeté) dans le temps O(N). . Top-N de min-heap Un min-heap est un arbre binaire complet où la valeur de chaque nœud est inférieure ou égale aux valeurs de ses enfants : Cette propriété rend efficace l'extraction de l'élément minimum (la racine) et l'insertion de nouveaux éléments tout en maintenant la structure de la pile. C'est un top-N min-heap parce que nous ne gardons que les meilleurs N scores dans le heap. Lorsqu'un nouveau score est entré, s'il est inférieur à la racine du heap, qui est le plus petit des meilleurs N scores, nous le rejetons. Si il est plus grand, nous remplaçons la racine par le nouveau score (nous pouvons le faire, parce que l'élément racine sera hors du haut N) et re-heapify (réorganisez le heap). Cela assure que nous avons toujours les meilleurs N scores dans le heap. Cette approche fournit O(1) rejet et O(log N) insertion complexité. Ce diagramme montre ce qui se passe lors de l'insertion: Chaque fragment conserve un ensemble top-N local et le Top-N global est calculé en fusionnant ces ensembles.Cette approche évite de trier l'ensemble de données sur chaque requête Top-N. Mise en œuvre du leadboard Avec toute la théorie sous notre ceinture, allons y arriver !Feuillez votre IDE préféré et commencez par définir la structure du shard et le type principal de tableau de bord: // 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 } Mise en œuvre Heap Ensuite, nous mettrons en œuvre la structure et les méthodes du top-N min-heap pour le gérer. Cela inclut l'insertion, le rejet et la récupération des meilleurs N scores. Nous pourrions mettre en œuvre notre propre pile pour un petit gain de performance, mais seulement au prix d'une complexité accrue - peut-être dans un autre article. 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) } } Tout d’abord, il faut mettre en œuvre le Ce qui définit , à , à , à et Nous avons créé un constructeur Pour commencer, il s’agit de la mise en scène. Enfin, le méthode traite de l'insertion de nouveaux scores tout en conservant la propriété top-N: si la pile n'est pas pleine, nous poussons simplement la nouvelle note. si elle est pleine et la nouvelle note est supérieure au minimum (la racine), nous remplaçons la racine et re-heapify (c'est-à-dire, nous appelons ) de heap.Interface Len Less Swap Push Pop NewTopNMinHeap Add heap.Fix Opérations de Shard: Mises à jour de score et lectures Chaque fragment doit exposer des méthodes qui ajoutent en toute sécurité de nouveaux scores et récupèrent son snapshot actuel de haut niveau. assure que les mises à jour simultanées du shard sont sécurisées. 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 } verrouille le shard pour l'écriture, puis ajoute le score à la pile en utilisant le méthode de la pâte que nous avons définie plus tôt. AddScore Add verrouille le fragment pour la lecture et renvoie une copie de la tranche de la pile afin que les appelants ne puissent pas modifier accidentellement la pile interne. Top Utiliser permet à plusieurs goroutines de lire le top-N en même temps que les écrits sont sérialisés. RWMutex Initialiser le leaderboard Maintenant que chaque tranche fait son travail, nous pouvons initialiser le tableau de bord avec un nombre spécifié de tranches et la taille globale du top-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 } Cette fonction crée un Retourner un pointeur assure que toutes les goroutines fonctionnent sur la même instance de tableau de bord partagé, ce qui est essentiel pour les mises à jour simultanées. Leaderboard Ajouter des scores Lorsque nous ajoutons un score au tableau de bord, nous devons déterminer le shard à mettre à jour. Nous utilisons le hash FNV-1a de playerID pour attribuer un joueur à un shard, ce qui assure une répartition approximativement uniforme des joueurs sur les shards. Ceci est important pour éviter les écarts de distribution, ce qui pourrait conduire à ce que certains shards soient surchargés tandis que d'autres sont sous-utilisés. Notez que le même playerID va toujours cartographier le même shard, ce qui pour notre conception actuelle n'est pas crucial, mais pourrait être important si nous voulons plus tard soutenir les opérations par joueur. // 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] } avec Nous pouvons facilement mettre en œuvre le La méthode pour ajouter des scores au leaderboard : 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) } appels pour trouver le bon shard, puis ajoutez le score à Chaque morceau gère son propre verrouillage, donc ce scale avec le nombre de morceaux. AddScore getShard shard.AddScore Récupération du Top-N Maintenant que nous pouvons ajouter des scores, il ne reste plus qu’une chose à faire : récupérer les scores mondiaux top-N sur tous les shards. Nous pouvons le faire en fusionnant les pics top-N de chaque shard. Puisque le top-N de chaque shard est déjà trié (en tant que min-heap), nous pouvons les combiner efficacement en utilisant un max-heap pour suivre le top-N global. (Pour un nombre très important de shards, une fusion plus complexe de k-way pourrait être mise en œuvre, mais pour les comptes de shard typiques, cette approche est suffisante.) // 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 } Chaque fragment renvoie une capture d'écran de son top-N, de sorte que nous ne tenons pas les verrous sur plusieurs fragments en même temps. Nous insérons toutes les entrées de shard top-N dans un min-heap temporaire de taille n pour maintenir le top-N global efficacement. Puisque le min-heap stocke le plus petit score de top-N à la racine, nous inversons la tranche pour retourner les meilleurs scores en premier. Tester ce que nous avons construit Maintenant que nous avons terminé notre tableau de bord, voyons comment cela fonctionne. Voici un programme de test simple qui démontre l'ajout de scores et la récupération du top-N simultanément: // 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) } } Ce programme crée un tableau de bord avec 8 morceaux et une taille top-10. Il engendre 50 goroutines, chacune simulant un joueur qui met à jour son score 200 fois avec des valeurs aléatoires. Vous pouvez utiliser ce programme avec La sortie sera quelque chose comme ça : 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 Conclusion Dans cet article, nous avons construit un tableau de bord concurrent en direct hautes performances dans Go depuis le bas. À partir du problème de base, nous avons discuté des défis posés par les écriture à haute fréquence, les requêtes hautes-N efficaces et la cohérence des snapshots sous concurrence. Nous avons exploré plusieurs options de conception : Une carte unique avec un mutex mondial : simple mais faible évolutivité. sync.Map : adapté aux lectures simultanées, mais limité aux requêtes de haut niveau. Tableau de bord scindé avec des pics de mins de haut N par pile: notre approche choisie, équilibrant la concurrence, l'efficacité et la simplicité. Nous avons mis en œuvre : Structures de niveau Shard avec serrures de lecture-écriture. Top-N min-heaps par morceau pour une insertion et un rejet rapides. Les requêtes globales top-N qui fusionnent efficacement les pics par pile sans bloquer les mises à jour simultanées. Un câble de démonstration / test illustrant les mises à jour en direct, les écrits simultanés et les snapshots du tableau de bord périodiques. Principaux takeaways : Sharding réduit le contentieux de verrouillage. Plusieurs goroutines peuvent mettre à jour les scores simultanément avec un blocage minimal. Les min-heaps maintiennent le top-N efficacement. Seuls les scores les plus pertinents sont stockés, gardant les opérations O(log N). En combinant des pics par pile, nous évitons de trier l'ensemble des données et de maintenir des requêtes rapides. La sécurité de la concurrence est simple avec les verrous par pièce. Vous n'avez pas besoin d'algorithmes complexes sans verrouillage pour la plupart des cas d'utilisation du tableau de bord en direct. L'augmentation du nombre de morceaux réduit la contention, et l'approche basée sur des pions assure l'efficacité de la mémoire. Avec cette fondation, vous pouvez étendre le tableau de bord pour soutenir: Top-N dynamique par shard ou leaderboards multi-niveaux. Intégration avec le stockage persistant ou les systèmes distribués pour des applications à plus grande échelle. Des mesures supplémentaires telles que les timestamps, les rangs ou les réalisations. Cette approche pratique et pratique vous donne une idée de la façon de gérer efficacement les charges de travail concurrentes du monde réel. Vous disposez désormais des outils pour implémenter, comparer et étendre les systèmes concurrents prêts à la production dans Go. Le code de cet article est disponible sur GitHub : gkoos/article-leaderboard. gkoos / tableau de bord de l'article
