Tämän artikkelin tavoitteena on rakentaa vankka samanaikainen johtajuus Go, joka voi: Käsittele tuhansia samanaikaisia päivityksiä useista goroutineista. Tarjoa usein Top-N-kyselyjä tehokkaasti. Pidä ennustettavissa olevia pikakuvia pisteistä huolimatta samanaikaisista kirjoituksista. Ole käytännöllinen ja valmiina tuotantoon, mukaan lukien ohjeet skaalautumisesta, muistin käytöstä ja laajennuksista. Emme vain näe koodia, vaan ymmärrämme myös, miksi jokainen suunnittelupäätös on tärkeä samanaikaisissa työmäärissä. Live leaderboards esittelee useita monimutkaisuuksia: Suuri taajuus kirjoittaa: Useita käyttäjiä voidaan päivittää samanaikaisesti. Globaalin kartan lukot muuttuvat nopeasti pullonkauloiksi. Tehokkaat Top-N-kyselyt: Koko tietokokonaisuuden lajittelu jokaisessa kirjoituksessa ei ole mahdollista. Muistin tehokkuus: Leaderboards voi sisältää satoja tuhansia käyttäjiä. Johdonmukaiset pikakuvakkeet: Käyttäjät odottavat, että Top-N-kysely heijastaa merkityksellistä taulukon tilaa, vaikka päivityksiä tapahtuisi. Samanaikaisen kirjoittamisen ja usein lukemisen yhdistelmä vaatii Go:n synkronointiprimitivien ja datarakenteiden huolellista käyttöä. Ongelman ymmärtäminen Leaderboard tukee yleensä kahta päätoimintaa: AddScore (userID string, score int): Tallentaa uuden pisteen käyttäjälle. Yksinkertaisuuden vuoksi seuraamme pisteitä, emme käyttäjiä, mikä tarkoittaa, että samalle käyttäjälle sallitaan useita korkeita pisteitä. Top(n int): Etsi top N korkeimmat pisteet. Lisäksi on toiminnallisia näkökohtia: Päivitysten on oltava kilpailukykyisiä. Top-N-kyselyjen on oltava tehokkaita, mieluiten nopeampia kuin O (yhteensä käyttäjät kirjaavat yhteensä käyttäjiä). Lukkojen pitäisi minimoida riita, jolloin useat kirjoittajat voivat jatkaa estämättä toisiaan. Kilpailun haasteet Korkean taajuuden kirjoitukset: Ilman hajanaisia tai samanaikaisesti tietoisia tietorakenteita jokainen päivitys sarjataan yhden lukon kautta. Tehokas Top-N-kyselyt: Naivi lähestymistapa olisi lajitella kaikki käyttäjät kuhunkin kyselyyn. 100 000 käyttäjälle tämä voi kestää kymmeniä millisekunteja kyselyä kohden - ei ole hyväksyttävää eläville järjestelmille, jotka vaativat millisekunnin tason reagointia. Muistin tehokkuus: Avustavien rakenteiden, kuten joukkojen tai lajiteltujen joukkojen, ylläpitäminen jokaiselle käyttäjälle vaatii huolellista muistinhallintaa. Johdonmukaiset pikakuvakkeet: Käyttäjät odottavat, että valintaruudulla on järkeä.Jos Top-N-kysely lukee epäjohdonmukaisia arvoja useissa osiossa, se voi palauttaa vaihtelevia tai virheellisiä tuloksia. Suunnittelun näkökohdat Ennen kuin aloitamme koodauksen, meidän on päätettävä, miten järjestämme tietorakenteet näiden vaatimusten täyttämiseksi. Yksi kartta Global Mutexilla type Leaderboard struct { mu sync.RWMutex scores map[string]int } Yksinkertaista ja helppoa perustella. Pros Huono skaalautuvuus raskaissa kirjoituksissa - kaikki päivitykset sarjataan yhden muteksin kautta. Cons Käyttötapa: Alhainen kilpailukyky tai pienet tietokokonaisuudet. käyttämällä sync.Map Käy tarjoaa samanaikaisen kartan lukemattomilla lukemilla: sync.Map var leaderboard sync.Map leaderboard.Store("user123", 100) score, ok := leaderboard.Load("user123") : Pros Lukitusvapaat lukemat mahdollistavat useiden goroutinien lukemisen samanaikaisesti. Kirjoitukset ovat atomisia ja turvallisia samanaikaiseen käyttöön. : Cons Iteraatio on heikosti johdonmukainen. Usein kirjoittaminen vähentää suorituskykyä. Se ei luonnostaan tue tehokkaita Top-N-kyselyjä, mikä tekee siitä suboptimaalisen live-leaderboardeille. Sharded kartan suunnittelu Jos haluat skaalata useiden kirjoittajien kanssa, voimme jakaa leaderboardin osakkeisiin. Jokaisella osakkeella on oma kartta ja mutex. Tämä vähentää lukkojen ristiriitaa ja mahdollistaa rinnakkaiset päivitykset. Kirjoitukset eri kappaleisiin etenevät itsenäisesti. Lukeminen voi tapahtua samanaikaisesti osakkeiden välillä. Top-N kyselyt merge per-shard tulokset. Tämä muotoilu saavuttaa korkean yhtäläisyyden säilyttäen koodin suhteellisen yksinkertaiseksi, joten pidämme sen täytäntöönpanossa. Heap-Based Top-N per Shard Jokaisessa kappaleessa meidän on seurattava tehokkaasti parhaita N-pisteitä. Voimme lajitella koko kappaleen jokaisessa kyselyssä, mutta se olisi hullua. Tai voimme seurata parhaita N-pisteitä järjestyksessä olevassa luettelossa, sitten uusi pisteet voitaisiin lisätä (tai hylätä) O(N) -ajalla. . Lähde: Min-heap Min-joukko on täydellinen binääripuu, jossa kunkin solmun arvo on pienempi tai yhtä suuri kuin sen lasten arvot: Tämä ominaisuus tekee tehokkaaksi poimia vähimmäiselementti (juuri) ja lisätä uusia elementtejä säilyttäen samalla pino rakenne. Se on top-N min-heap, koska pidämme vain top N-pisteet joukossa. Kun uusi pistemäärä tulee sisään, jos se on pienempi kuin joukon juuret, joka on pienin top N-pisteet, hylkäämme sen. Jos se on suurempi, korvaamme juuret uudella pistemäärällä (voimme tehdä tämän, koska root-elementti on ylhäältä N) ja uudelleenheapify (rakenna joukko). Tämä varmistaa, että meillä on aina top N-pisteet joukossa. Tämä lähestymistapa tarjoaa O(1) hylkäämisen ja O(log N) lisäämisen monimutkaisuuden. Tämä kaavio näyttää, mitä insertion yhteydessä tapahtuu: Jokainen kappale pitää paikallisen top-N-kokoonpanon ja globaali Top-N lasketaan yhdistämällä nämä kappaleet. Sharded Leaderboard -toiminta Kaikella teorialla vyömme alla, pääsemme siihen! Laukaise suosikki IDE ja aloita määrittelemällä shard-rakenne ja pääjohtajan tyyppi: // 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 toteutus Seuraavaksi toteutamme top-N min-heapin rakenteen ja menetelmät sen hallitsemiseksi.Tähän sisältyy ylimpien N-pistemäärien lisääminen, hylkääminen ja hakeminen. Voisimme toteuttaa oman joukon pienelle suorituskyvylle, mutta vain lisääntyneen monimutkaisuuden kustannuksella - ehkä toisessa artikkelissa. 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) } } Ensinnäkin meidän on toteutettava Mikä määrittelee ja ja ja ja Sitten luomme rakentajan Ensimmäinen askel.Loppujen lopuksi menetelmä käsittelee uusien pistemäärien lisäämistä säilyttäen ylimmän N-ominaisuuden: jos pino ei ole täynnä, työnnämme yksinkertaisesti uutta pistettä. Jos se on täynnä ja uusi pistemäärä on suurempi kuin vähimmäismäärä (juuri), korvaamme juuret ja yhdistämme uudelleen (eli kutsumme ) on heap.Interface Len Less Swap Push Pop NewTopNMinHeap Add heap.Fix Shard Operations: Score päivitykset ja lukemat Jokaisen kappaleen tulisi paljastaa menetelmät, jotka lisäävät turvallisesti uusia pisteitä ja hankkivat nykyisen top-N-näytteen. varmistaa, että shardin samanaikaiset päivitykset ovat turvallisia. 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 } lukitsee shardin kirjoittamiseen, lisää sitten pisteet joukkoon käyttämällä Meillä on aikaisemmin määritelty metodi. AddScore Add lukitsee kaistan lukemista varten ja palauttaa kopion pinoista niin, että soittajat eivät voi vahingossa muokata sisäistä pinoa. Top käyttämällä mahdollistaa useiden goroutinien lukemisen top-N:stä samanaikaisesti, kun kirjoitukset sarjataan. RWMutex Leaderboardin aloittaminen Nyt kun jokainen murto on tekemässä asiaansa, voimme aloittaa johtajuuden määritetyllä määrällä murto-osia ja maailmanlaajuisella top-N-kokoisella: // 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 } Tämä toiminto luo a Palauttamalla osoitin varmistetaan, että kaikki goroutins toimivat samassa jaetussa leaderboard-instanssissa, mikä on välttämätöntä samanaikaisille päivityksille. Leaderboard Lisää pisteitä Kun lisäämme pistemäärän listalle, meidän on määritettävä, mitkä shardit päivitetään. Käytämme playerID:n FNV-1a-hashia määrittämään pelaajan shardille, mikä takaa pelaajien suunnilleen yhdenmukaisen jakautumisen shardeihin.Tämä on tärkeää, jotta vältetään jakelun vääristyminen, mikä voi johtaa siihen, että jotkut shardit ovat ylikuormitettuja, kun taas toiset ovat alikäyttöisiä. Huomaa, että sama playerID kartoittaa aina samalle shardille, mikä nykyisen suunnittelumme kannalta ei ole ratkaisevan tärkeää, mutta voi olla tärkeää, jos haluamme myöhemmin tukea per-player-toimintoja. // 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] } kanssa Nyt voimme helposti toteuttaa menetelmä pisteiden lisäämiseksi leaderboardiin: 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) } Puheluita löytää oikea shard, lisää sitten pistemäärä sen kautta Jokainen murto käsittelee oman lukituksensa, joten tämä skaalautuu murtojen lukumäärän mukaan. AddScore getShard shard.AddScore Maailmanlaajuinen Top-N Nyt kun voimme lisätä pisteitä, on vain yksi asia jäljellä: hanki maailmanlaajuiset top-N-pisteet kaikissa hiukkasissa. Voimme tehdä tämän yhdistämällä kunkin hiukkasen top-N-hiukkaset. Koska kunkin hiukkasen top-N on jo lajiteltu (min-hiukkasena), voimme tehokkaasti yhdistää ne käyttämällä max-hiukkasia pitämään koko top-N:n jäljessä. (Erittäin suurille hiukkasille voitaisiin toteuttaa monimutkaisempi k-way-yhdistelmä, mutta tyypillisille hiukkasille tämä lähestymistapa riittää.) // 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 } Jokainen fragmentti palauttaa pikakuvakkeen sen top-N:stä, joten emme pidä lukkoja useiden fragmenttien yli samanaikaisesti. Lisäämme kaikki shard-top-N-tiedot tilapäiseen min-kokoon, jonka koko on n, jotta maailmanlaajuinen top-N säilyy tehokkaasti. Koska min-koko tallentaa pienimmän top-N-pisteet juuressa, käännymme segmentin palauttamaan korkeimmat pisteet ensin. Testaa, mitä olemme rakentaneet Nyt kun olemme suorittaneet listamme, katsotaanpa, miten se toimii.Tässä on yksinkertainen testausohjelma, joka osoittaa tulosten lisäämisen ja top-N: n keräämisen samanaikaisesti: // 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) } } Tämä ohjelma luo listan, jossa on 8 osumaa ja 10 parasta kokoa. Se synnyttää 50 goroutineja, joista kukin simuloi pelaajaa, joka päivittää pisteet 200 kertaa satunnaisilla arvoilla. Samalla toinen goroutine tulostaa nykyiset 10 parasta pistettä 100 millisekunnin välein. Voit käyttää tätä ohjelmaa , tulos on jotain tällaista: 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 Johtopäätös Tässä artikkelissa olemme rakentaneet korkean suorituskyvyn samanaikaisen live-leaderboardin Go: ssä alusta alkaen. Alkaen ydinkysymyksestä keskustelemme korkean taajuuden kirjoitusten, tehokkaiden top-N-kyselyjen ja samanaikaisen snapshotin johdonmukaisuuden haasteista. Tutkimme useita muotoiluvaihtoehtoja: Yksi kartta maailmanlaajuisella muteksilla: yksinkertainen, mutta huono skaalautuvuus. sync.Map: sopii samanaikaisiin lukemisiin, mutta rajoitettu top-N-kyselyihin. Sharded leaderboard per-shard top-N min-heap: valitsemamme lähestymistapa, tasapainottamalla samankaltaisuutta, tehokkuutta ja yksinkertaisuutta. Me olemme toteuttaneet: Shard-tason rakenteet, joissa on lukittavat lukot. Top-N min-kokoonpanot kuormaa kohden nopeaa lisäämistä ja hylkäämistä varten. Maailmanlaajuiset top-N-kyselyt, jotka yhdistävät per-shard-joukot tehokkaasti estämättä samanaikaisia päivityksiä. Demo / testiharness, joka kuvaa live-päivityksiä, samanaikaisia kirjoituksia ja säännöllisiä leaderboard-snapshot-kuvia. Tärkeimmät takeaways: Sharding vähentää lukkojen ristiriitaa. Useat goroutins voivat päivittää pisteet samanaikaisesti vähäisen eston kanssa. Min-kokoonpanot ylläpitävät top-N:ää tehokkaasti. Vain kaikkein merkityksellisimmät pisteet tallennetaan pitämällä toiminnot O(log N). Globaali top-N-yhdistyminen on käytännöllistä. Yhdistämällä per-shard-joukot vältämme koko tietokokonaisuuden lajittelua ja ylläpidetään nopeita kyselyitä. Kilpailun turvallisuus on helppoa per-shard-lukkojen kanssa. Sinun ei tarvitse monimutkaisia lukko-vapaita algoritmeja useimmissa live-leaderboard-käyttötapauksissa. Tällainen muotoilu skaalautuu kauniisti.Rajojen määrän lisääminen vähentää ristiriitoja, ja pinoon perustuva lähestymistapa varmistaa muistin tehokkuuden. Tämän säätiön avulla voit laajentaa leaderboardia tukemaan: Dynaaminen top-N per shard tai multi-level leaderboards. Integrointi pysyvään tallennukseen tai hajautettuihin järjestelmiin laajempiin sovelluksiin. Lisämetriikat, kuten aikaleimat, sijoitukset tai saavutukset. Tämä käytännöllinen, käytännönläheinen lähestymistapa antaa sinulle käsityksen siitä, miten voit käsitellä reaaliaikaisia samanaikaisia työmääriä tehokkaasti.Tällä hetkellä sinulla on työkalut tuotantokelpoisten samanaikaisten järjestelmien käyttöönottoon, vertailuun ja laajentamiseen Go:ssa. Tämän artikkelin koodi on saatavilla Githubissa: gkoos/article-leaderboard. gkoos/artikkelin johtajuus
