Ranking rapido e affidabile in Datastore

Ranking: un problema semplice, ma molto difficile.

Tomoaki Suzuki (Figura 1), Lead Engineer di App Engine presso Applibot, ha cercato di risolvere il problema molto comune, ma molto difficile, che deve affrontare ogni grande servizio di gioco: il ranking.

Figura 1: Tomoaki Suzuki, App Engine Lead Engineer presso Applibot, Inc.

Applibot è uno dei principali fornitori di applicazioni social in Giappone. L'unicità dell'azienda è la sua vasta conoscenza ed esperienza nella creazione di servizi per social game super scalabili su Google App Engine, l'offerta Platform as a Service (PaaS) di Google. Sfruttando la potenza della piattaforma, Applibot si è rivelata un successo nel cogliere le opportunità di business nel mercato dei social game, non solo in Giappone, ma anche negli Stati Uniti. Applibot può certamente attestare il suo successo. Legend of the Cryptids (Figura 2), uno dei loro titoli di maggior successo, ha raggiunto il primo posto nella categoria di giochi dell'Apple AppStore Nord America nell'ottobre 2012. La serie Legend ha registrato 4,7 milioni di download. Un altro titolo, Gang Road, ha raggiunto la prima posizione nella classifica delle vendite totali dell'AppStore Japan nel dicembre 2012.

Figura 2: Legend of the Criptids, il gioco al primo posto nell'App Store di Apple a ottobre 2012.

Questi titoli sono stati in grado di scalare senza problemi e di gestire il traffico in costante aumento. Applibot non ha avuto difficoltà a creare cluster complessi di server virtuali o database con sharding. Ha sfruttato la potenza di App Engine e ha raggiunto in modo efficiente scalabilità e disponibilità.

Tuttavia, il ranking aggiornato dei giocatori non è facile da risolvere, non per Tomoaki e probabilmente non per nessuno sviluppatore, soprattutto su questa scala. I requisiti sono semplici:

Il tuo gioco ha centinaia di migliaia (o più!) giocatori.
Ogni volta che un giocatore combatte i nemici (o esegue altre attività), il suo punteggio cambia.
Vuoi mostrare il ranking più recente del player su una pagina di un portale web.

Come si calcola un ranking?

Figura 3: ogni giocatore ha un punteggio. Come viene calcolato il loro ranking?

Ottenere un ranking è facile, se non si prevede che sia anche scalabile e veloce. Ad esempio, potresti eseguire la seguente query:

SELECT count(key) FROM Players WHERE Score > YourScore

Questa query conta tutti i giocatori con un punteggio più alto del tuo (Figura 4). Ma vuoi eseguire questa query per ogni richiesta dalla pagina del portale? Quanto tempo impiegherebbe ad avere un milione di giocatori?

Inizialmente Tomoaki ha implementato questo approccio, ma ci sono voluti alcuni secondi per ottenere ogni risposta. Era troppo lento, troppo costoso e aveva un rendimento progressivamente peggiore man mano che la scala aumentava.

Figura 4: il modo più semplice: scansione di tutti i giocatori.

In seguito, Tomoaki ha provato a mantenere il ranking dei dati in Memcache. Questa operazione è stata veloce, ma non affidabile. Le voci memcache potevano essere rimosse in qualsiasi momento e, a volte, il servizio memcache non era disponibile. Con un servizio di ranking che dipendeva esclusivamente dalle coppie chiave-valore in memoria, era difficile mantenere coerenza e disponibilità.

Come soluzione alternativa temporanea, Tomoaki ha deciso di ridurre il livello di servizio. Anziché calcolare la classifica per ogni richiesta, ha impostato un'attività programmata che analizzava e aggiornava la posizione di ogni giocatore una volta all'ora. In questo modo, le richieste provenienti dalla pagina del portale potrebbero ottenere immediatamente il ranking giocatore, ma potrebbe arrivare fino a un'ora prima.

In definitiva, Tomoaki era alla ricerca di un'implementazione di ranking permanente, transazionale, rapida e scalabile che potesse accettare 300 richieste di aggiornamento del punteggio al secondo e ottenere un ranking per ogni giocatore in centinaia di millisecondi. Per trovare una soluzione, Tomoaki si è rivolta a Kaz Sato, un Solutions Architect (SA) e un Technical Account Manager (TAM) nel team della Google Cloud Platform e assegnato ad Applibot con un contratto di assistenza di livello premium.

Un modo rapido per risolvere i problemi

Molti grandi clienti o partner di Google Cloud Platform, come Applibot, sottoscrivono un contratto di assistenza di livello premium. Con questo contratto di assistenza, oltre all'assistenza 24 ore su 24, 7 giorni su 7 del team di assistenza clienti Cloud e all'assistenza aziendale del team di vendita Cloud, Google assegna un Technical Account Manager (TAM) a ciascun cliente.

Un TAM rappresenta il cliente del team Google Engineering, che si occupa della realizzazione dell'effettiva infrastruttura cloud. I TAM conoscono in dettaglio il sistema e l'architettura del cliente e, dopo aver segnalato un caso critico, utilizzano le proprie conoscenze e la propria rete come rappresentante di Google Engineering nell'azienda per risolvere il problema. I TAM possono riassegnare i problemi ai Solutions Architect del team o agli ingegneri del software nel team della piattaforma Cloud. L'assistenza di livello premium è la corsia preferita per trovare una soluzione con la Google Cloud Platform.

Kaz, il TAM che supporta Applibot, sapeva che il ranking era un problema classico ma difficile da risolvere per qualsiasi servizio distribuito scalabile. Ha iniziato a esaminare le implementazioni note per il ranking su Google Cloud Datastore e altri datastore NoSQL per trovare una soluzione che soddisfasse i requisiti di Applibot.

Ricerca di un algoritmo O(log n)

La soluzione di query semplice richiede l'analisi di tutti i giocatori con un punteggio più alto per conteggiare il ranking di un solo giocatore. La complessità temporale di questo algoritmo è O(n), ovvero il tempo necessario per l'esecuzione della query aumenta proporzionalmente al numero di player. In pratica, ciò significa che l'algoritmo non è scalabile. Invece, abbiamo bisogno di un algoritmo O(log n) o più veloce, in cui il tempo aumenterà logaritmicamente solo con l'aumento del numero di giocatori.

Se hai seguito un corso di informatica, forse ricorderai che gli algoritmi ad albero, come alberi binari, alberi rossi-neri o B-Trees, possono raggiungere la complessità del tempo O(log n) per trovare un elemento. Gli algoritmi ad albero possono essere utilizzati anche per calcolare un valore aggregato di un intervallo di elementi, come conteggio, max/min e media, tenendo i valori aggregati su ciascun nodo del ramo. Utilizzando questa tecnica, è possibile implementare un algoritmo di ranking con prestazioni O(log n).

Kaz ha trovato un'implementazione open source di un algoritmo di ranking ad albero per Datastore, scritto da un ingegnere di Google: la libreria del ranking di Google Code Jam.

Questa libreria basata su Python espone due metodi:

SetScore per impostare il punteggio di un giocatore.
FindRank per conoscere la posizione di un determinato punteggio.

Man mano che le coppie punteggio-giocatore vengono create e aggiornate con il metodo SetScore, la libreria di ranking Code Jam crea un albero N-ary¹. Ad esempio, prendiamo in considerazione un albero terziario che può contare il numero di giocatori con punteggi compresi tra 0 e 80 (Figura 5). La libreria archivia il nodo radice, che contiene tre numeri, come un'unica entità. Ogni numero corrisponde al numero di giocatori con punteggi, rispettivamente, nelle sottosezioni 0-26, 27-53 e 54-80. Il nodo radice ha un nodo secondario per ogni intervallo, contenente a sua volta tre valori per i giocatori che rientrano nei sottointervalli del sottointervallo. La gerarchia ha bisogno di quattro livelli per memorizzare il numero di giocatori per 81 diversi valori di punteggio.

Figura 5: calcolo del ranking di un punteggio in un albero terziario.

Per determinare il grado di un giocatore che ha ottenuto un punteggio pari a 30, la biblioteca deve leggere solo quattro entità (i nodi cerchiati dalla linea tratteggiata nel diagramma) per sommare il numero di giocatori con un punteggio superiore a 30. Con 22 giocatori a "destra" in quattro entità, il ranking giocatore è 23°.

Allo stesso modo, una chiamata a SetScore deve aggiornare solo quattro entità. Anche se hai un numero elevato di punteggi diversi, l'accesso al datastore aumenterà solo nel punto O(log n) e non verrà influenzato dal numero di player. In pratica, la libreria di ranking Code Jam utilizza 100 (anziché 3) come numero predefinito di valori per nodo, quindi è necessario accedere solo a due (o tre, se l'intervallo di punteggi è maggiore di 100.000).

Kaz ha utilizzato il popolare strumento di test di carico Apache JMeter per eseguire un test di carico sulla libreria di ranking di Code Jam e ha confermato che la libreria risponde rapidamente. Sia SetScore che FindRank possono completare i loro job in centinaia di millisecondi utilizzando l'algoritmo ad albero N-ary che funziona alla complessità del tempo O(log n).

Gli aggiornamenti simultanei limitano la scalabilità

Tuttavia, durante i test di carico, Kaz ha rilevato un limite critico nella libreria di ranking di Code Jam. La sua scalabilità in termini di velocità effettiva di aggiornamento era piuttosto bassa. Quando ha aumentato il carico a tre aggiornamenti al secondo, la libreria ha iniziato a restituire errori di nuovo tentativo di transazione. Era ovvio che la libreria non poteva soddisfare il requisito di Applibot di 300 aggiornamenti al secondo. Potrebbe gestire solo l'1% circa di questa velocità effettiva.

Perché? Il motivo è il costo del mantenimento della coerenza della struttura ad albero. In Datastore, è necessario utilizzare un gruppo di entità per garantire un'elevata coerenza quando si aggiornano più entità in una transazione. Vedi "Bilanciare una coerenza elevata ed finale con Google Cloud Datastore". La libreria di ranking Code Jam utilizza un singolo gruppo di entità per contenere l'intero albero al fine di garantire coerenza dei conteggi negli elementi della struttura.

Tuttavia, un gruppo di entità in Datastore ha un limite di prestazioni. Datastore supporta solo una transazione al secondo su un gruppo di entità. Inoltre, se lo stesso gruppo di entità viene modificato in transazioni simultanee, è probabile che la transazione non vada a buon fine e debba essere ritentata. La libreria di ranking Code Jam è a elevata coerenza, transazionale e abbastanza veloce, ma non supporta un volume elevato di aggiornamenti simultanei.

Soluzione per i team Datastore: aggregazione dei job

Kaz ricordò che un tecnico software del team Datastore aveva indicato una tecnica per ottenere una velocità effettiva molto più elevata rispetto a un aggiornamento al secondo su un gruppo di entità. Ciò può essere ottenuto aggregando un batch di aggiornamenti in un'unica transazione, anziché eseguire ogni aggiornamento come una transazione separata. Tuttavia, poiché la transazione include un numero elevato di aggiornamenti, ciascuna transazione richiede più tempo, aumentando la possibilità di conflitti da transazioni simultanee.

In risposta alla richiesta di Kaz, il team di Datastore ha iniziato a discutere del problema e ci ha consigliato di prendere in considerazione l'utilizzo di Job Aggregation, uno dei pattern di progettazione utilizzati con Megastore.

Megastore è il livello di archiviazione sottostante di Datastore e gestisce la coerenza e la transazione dei gruppi di entità. Il limite di un aggiornamento al secondo ha origine da quel livello. Poiché Megastore è ampiamente utilizzato da vari servizi Google, gli ingegneri raccolgono e condividono all'interno dell'azienda best practice e pattern di progettazione per creare un sistema scalabile e coerente con questo datastore NoSQL.

L'idea di base dell'aggregazione dei job è utilizzare un singolo thread per elaborare un batch di aggiornamenti. Poiché c'è un solo thread e una sola transazione aperta nel gruppo di entità, non si verificano errori di transazione dovuti agli aggiornamenti simultanei. Puoi trovare idee simili in altri prodotti di archiviazione come VoltDb e Redis.

Tuttavia, il pattern di aggregazione dei job presenta uno svantaggio: utilizza un solo thread per aggregare tutti gli aggiornamenti e questo impone un limite alla velocità di invio degli aggiornamenti a Datastore. Di conseguenza, era importante determinare se l'aggregazione dei job potesse soddisfare il requisito di velocità effettiva di Applibot di 300 aggiornamenti al secondo.

Aggregazione job per coda in modalità pull

Sulla base dei consigli del team Datastore, Kaz ha scritto un codice Proof of Concept (PoC) che combina il pattern di aggregazione dei job con la libreria di ranking Code Jam. Il PDC ha i seguenti componenti:

Front-end: accetta le richieste SetScore degli utenti e le aggiunge come attività a una coda in modalità pull.
Coda in modalità pull: riceve e conserva le richieste di aggiornamento di SetScore dal frontend.
Backend: esegue un ciclo infinito con un singolo thread che estrae le richieste di aggiornamento dalla coda e le esegue con la libreria di ranking Code Jam.

Il PDC crea una coda pull, ossia una sorta di coda di attività in App Engine che consente agli sviluppatori di implementare uno o più worker che consumano le attività aggiunte alla coda. L'istanza di backend ha un singolo thread in un ciclo infinito che continua a estrarre il maggior numero possibile di attività (fino a 1000) dalla coda. Il thread passa ogni richiesta di aggiornamento alla libreria di ranking Code Jam, che le esegue come batch in una singola transazione. La transazione potrebbe rimanere aperta per almeno un secondo, ma poiché esiste un singolo thread che guida la libreria e Datastore, non esistono conflitti e nessun problema di modifica in parallelo.

L'istanza di backend è definita come un modulo, una funzionalità di App Engine che consente agli sviluppatori di definire un'istanza di applicazione con varie caratteristiche. In questo PDC, l'istanza di backend viene definita come un'istanza di scalabilità manuale. È in esecuzione una sola istanza di questo tipo alla volta.

Kaz ha testato il carico del PDC utilizzando JMeter. Ha confermato che il PDC era in grado di elaborare 200 richieste SetScore al secondo, con batch da 500 a 600 aggiornamenti per transazione. L'aggregazione dei job funziona.

Sharding della coda per prestazioni stabili

Ma Kaz ha presto riscontrato un altro problema. Mentre continuava a eseguire il test per diversi minuti, ha notato che la velocità effettiva della coda in modalità pull varia di volta in volta (Figura 6). Nello specifico, quando continuava ad aggiungere richieste alla coda con 200 attività al secondo per diversi minuti, la coda smetteva improvvisamente di passare attività al backend e la latenza per ogni attività aumentava drasticamente.

Figura 6: fluttuazione delle prestazioni della coda in modalità pull.

Kaz si è consultato con il team Task Queue per sapere perché stava accadendo. Secondo il team Task Queue, questo è un comportamento noto per l'attuale implementazione delle coda in modalità pull che dipende da Bigtable come livello di persistenza. Se un tablet Bigtable diventa troppo grande, viene suddiviso in più tablet. Durante la suddivisione del tablet, le attività non vengono consegnate, il che crea una fluttuazione delle prestazioni quando la coda riceve attività con una frequenza elevata. Il team addetto alle code di attività sta lavorando per migliorare queste caratteristiche delle prestazioni.

Michael Tang, Solutions Architect, ha consigliato una soluzione alternativa utilizzando lo sharding delle code. Anziché utilizzare una sola coda, ha suggerito di distribuire il carico su più code. Ogni coda può essere archiviata su un server tablet Bigtable diverso per ridurre al minimo l'effetto di una suddivisione del tablet e mantenere un'elevata velocità di elaborazione delle attività. Mentre una coda elabora una suddivisione, le altre code continuano a funzionare e lo sharding riduce il carico su ogni coda, quindi la suddivisione di un tablet avviene meno spesso.

Il loop di istanza di backend avanzato esegue il seguente algoritmo:

Prendi in prestito SetScore attività da 10 code.
Chiama il metodo SetScores con le attività.
Elimina le attività noleggiate dalle code.

Nel passaggio 1, ogni coda fornisce fino a 1000 attività, ciascuna delle quali contiene un nome giocatore e un punteggio. Dopo aver aggregato tutte le coppie di punteggio del player in un dizionario, il passaggio 2 passa il batch di aggiornamenti al metodo SetScores della libreria di ranking Code Jam, che apre una transazione per archiviarli in Datastore. Se non si è verificato alcun errore durante l'esecuzione del metodo, il passaggio 3 elimina dalle code le attività noleggiate.

Se si verifica un errore o un arresto imprevisto del loop o dell'istanza di backend, le attività di aggiornamento rimangono nelle code di attività, in modo da poter essere elaborate al riavvio dell'istanza. In un sistema di produzione, potresti avere un altro backend che agisce da watchdog in modalità standby, pronto a prendere il controllo in caso di errore della prima istanza.

La soluzione proposta: funziona a 300 aggiornamenti al secondo sostenuti²

La Figura 7 mostra il risultato del test di carico dell'implementazione finale del PDC con lo sharding della coda. Riduce al minimo le fluttuazioni del rendimento nelle code e può supportare 300 aggiornamenti al secondo per diverse ore. Con il normale caricamento, ogni aggiornamento viene applicato a Datastore entro pochi secondi dalla ricezione della richiesta.

Figura 7: grafico delle prestazioni della soluzione.

Questa soluzione soddisfa tutti i requisiti originali di Applibot:

Scalabile per gestire decine di migliaia di giocatori.
Persistente e coerente, poiché tutti gli aggiornamenti vengono eseguiti nelle transazioni Datastore.
Talmente veloce da gestire 300 aggiornamenti al secondo.

Con i risultati dei test di carico e il codice PDC, Kaz ha presentato la soluzione a Tomoaki e altri ingegneri Applibot. Tomoaki prevede di incorporare la soluzione nel proprio sistema di produzione, prevede di ridurre la latenza dell'aggiornamento delle informazioni sul ranking da un'ora a pochi secondi e spera di migliorare notevolmente l'esperienza utente.

Riepilogo della struttura del ranking con aggregazione dei job

La soluzione proposta presenta diversi vantaggi e uno svantaggio:

Vantaggi:

Veloce: la chiamata FindRank richiede alcune centinaia di millisecondi o meno.
Veloce: SetScore invia un'attività, che viene elaborata dal backend in pochi secondi.
Fortemente coerente e persistente in Datastore.
Le posizioni sono precise.
Scalabile per qualsiasi numero di giocatori.

Svantaggio:

La velocità effettiva è limitata (circa 300 aggiornamenti al secondo con l'implementazione corrente).

Poiché questa soluzione utilizza il pattern di aggregazione dei job, si basa su un singolo thread per aggregare tutti gli aggiornamenti. Sono necessarie attività o complessità aggiuntive per ottenere una velocità effettiva superiore a 300 aggiornamenti al secondo con la potenza attuale della CPU delle istanze di App Engine e le prestazioni di Datastore.

Soluzione più scalabile con l'albero con sharding

Se hai bisogno di una frequenza di aggiornamento ancora maggiore, potrebbe essere necessario suddividere in più parti la struttura del ranking. Dovresti creare più implementazioni del sistema sopra menzionato, ovvero un insieme di code, ciascuna che alimenta un modulo di backend che aggiorna il proprio albero di ranking.

In genere non è richiesto né previsto il coordinamento degli alberi. Nel caso più semplice, ogni aggiornamento di SetScore viene inviato in modo casuale a una coda. Con tre di questi alberi, ciascuno con il proprio gruppo di entità Datastore e server di backend, la velocità effettiva di aggiornamento prevista sarebbe tre volte superiore. Il compromesso è che FindRank deve eseguire query su ogni albero del ranking per ottenere il ranking di un punteggio, quindi sommare il ranking di ogni albero per trovare quello effettivo, operazione che richiede più tempo. Il tempo di query per FindRank può essere ridotto notevolmente mantenendo le entità in Memcache.

Questo approccio è simile al noto approccio di utilizzo dei contatori con sharding: ogni contatore viene incrementato in modo indipendente e la somma totale viene calcolata solo quando necessario dal client.

Ad esempio, con tre alberi, FindRank(865) potrebbe trovare i tre ranghi 124, 183 e 156, indicando che ogni albero contiene il rispettivo numero di punteggi superiore a 865. Il numero totale calcolato di punteggi superiori a 865 sarà quindi 124 + 183 + 156 = 463.

Questo approccio non funziona per tutti i tipi di algoritmi distribuiti, ma poiché il ranking è fondamentalmente un problema di conteggio commutativo, dovrebbe funzionare per problemi di ranking di grandi volumi.

Soluzioni più scalabili con approcci approssimativi

Se la tua applicazione richiede la scalabilità più che l'accuratezza dei ranghi e può tollerare un certo livello di inesattezza o approssimazione, potresti scegliere approcci stocastici come:

Bucket con query globale
Metodo di conteggio senza perdita
Streaming frugale

Questi approcci approssimativi sono tutte varianti di un'unica idea: come si comprime lo spazio di archiviazione per le informazioni di ranking consentendo un certo degrado dell'accuratezza del ranking?

Bucket con query globale è una soluzione alternativa proposta dal team Datastore e da Alex Amies, un TAM. Alex ha implementato un PDC sulla base dell'idea del team Datastore e ha condotto un'analisi approfondita delle prestazioni. Ha dimostrato che Bucket con query globale è una soluzione di ranking scalabile con un peggioramento minimo dell'accuratezza del ranking e potrebbe essere adatta per le applicazioni che richiedono una velocità effettiva superiore rispetto alla libreria di ranking Code Jam. Consulta l'Appendice per una descrizione dettagliata e i risultati del test.

Lossy Counting Method e Frugal Streaming sono i cosiddetti algoritmi online e algoritmi di streaming in cui potresti utilizzare uno spazio di archiviazione in memoria molto ridotto per calcolare una stima stocastica dei migliori ranking a partire da un flusso di coppie giocatore-punteggio. Questi algoritmi sarebbero adatti per applicazioni che richiedono una latenza molto bassa e una larghezza di banda super elevata, ad esempio migliaia di aggiornamenti al secondo, con una precisione e una copertura del ranking più limitate. Ad esempio, se desideri avere una dashboard in tempo reale che mostri le prime 100 parole chiave digitate nello stream di un social network, questi algoritmi aiuterebbero.

Conclusione

Il ranking è un problema classico ma difficile da risolvere se richiedi che l'algoritmo sia scalabile, coerente e veloce. In questo articolo, abbiamo descritto in che modo i TAM di Google hanno lavorato a stretto contatto con il cliente e con i team tecnici di Google per affrontare la sfida e fornire una soluzione in grado di ridurre la latenza di aggiornamento del ranking da un'ora a pochi secondi. I pattern di progettazione rilevati nel processo, aggregazione dei job e sharding delle code, potrebbero essere applicati anche a problemi comuni in altre progettazioni di sistema basate su Datastore che richiedono centinaia di aggiornamenti al secondo con elevata coerenza.

Note

La libreria di ranking di Code Jam utilizza un parametro chiamato "fattore di branching" che specifica il numero di punteggi che avrà ogni entità. Per impostazione predefinita, la libreria utilizza 100 come parametro. In questo caso, i punteggi che vanno da 0 a 9999 saranno archiviati su 100 entità come figli del nodo radice. Se hai bisogno di gestire una gamma più ampia di punteggi, puoi modificare il fattore di diramazione in un valore più alto per ottimizzare il numero di accessi alle entità.
Eventuali cifre relative alle prestazioni descritte in questo articolo sono valori campionati a scopo di riferimento e non garantiscono prestazioni assolute di App Engine, Datastore o altri servizi.

Appendice: bucket con soluzione di query globale

Come accennato nella sezione Come ottenere un ranking, è costoso eseguire query sul database per ogni richiesta di ranking. Questo approccio alternativo ottiene periodicamente il conteggio di tutti i punteggi, calcola il ranking dei punteggi selezionati e fornisce i punti dati da utilizzare nel calcolo dei ranking per determinati giocatori. L'intervallo totale dei punteggi è partizionato in "bucket". Ogni bucket è caratterizzato da un sottointervallo di punteggi e dal numero di giocatori con punteggi in tale intervallo. Da questi dati, la posizione di qualsiasi punteggio può essere calcolata con approssimazione. Questi bucket sono simili al nodo di primo livello nell'albero di ranking, ma invece di passare a nodi più dettagliati, questo algoritmo si interpola all'interno di un bucket.

Il recupero del ranking da parte degli utenti dal frontend viene disaccoppiato dal calcolo del ranking sui bucket nel backend per ridurre al minimo il tempo per trovare un ranking. Quando viene richiesto il ranking di un giocatore, viene trovato il bucket appropriato in base al punteggio del giocatore. Il bucket include un limite di ranking superiore e il numero di giocatori all'interno del bucket. L'interpolazione lineare all'interno dei bucket viene utilizzata per stimare il ranking dei giocatori all'interno dei bucket. Nei nostri test, siamo riusciti a ottenere il ranking di un giocatore in meno di 400 millisecondi per un round trip HTTP completo. Il costo del metodo FindRank non dipende dal numero di giocatori nella popolazione.

Calcolo del ranking per un determinato punteggio

Figura 8: distribuzione dei punteggi nei bucket.

Per ogni bucket vengono registrati il conteggio e il ranking più alto (ovvero il ranking più alto possibile in questo bucket). Per i punteggi compresi tra i limiti di punteggio basso e alto in un bucket, utilizziamo l'interpolazione lineare per stimare il ranking. Ad esempio, se il giocatore ha ottenuto un punteggio di 60, consideriamo il bucket [50, 74], utilizzando il conteggio (numero di giocatori/punteggi nel bucket) (42) e il ranking più alto (5) per calcolare il ranking del giocatore con questa formula:

    rank = 5  + (74 - 60)*42/(74 - 50) =  30

Calcolo del conteggio e dell'intervallo per ogni bucket

In background, utilizzando un cron job o una coda di attività, i conteggi per ciascun bucket vengono calcolati e salvati eseguendo l'iterazione su tutti i bucket. È definita query globale perché calcola i parametri necessari per stimare i ranking esaminando i punteggi di tutti i giocatori. Di seguito è riportato un codice Python di esempio per eseguire questa operazione in base ai punteggi nell'intervallo [low_score, high_score] per ciascun bucket.

next_upper_rank = 1
for b in buckets:
  count = GetCountInRange(b.low_score, b.high_score)
  b.count = count
  b.upper_rank = next_upper_rank
  b.put()
  next_upper_rank += count

Il metodo GetCountInRange() conteggia ciascun giocatore con i punteggi compresi nell'intervallo coperto dal bucket. Poiché Datastore mantiene un indice ordinato sui punteggi dei player, questo conteggio può essere calcolato in modo efficiente.

Quando dobbiamo trovare la classifica di un determinato giocatore, possiamo utilizzare il codice come mostrato di seguito.

b = GetBucketByScore(score)
rank = RankInBucket(b, score)
return rank + b.upper_rank - 1

Il metodo GetBucketByScore(score) recupera il bucket che contiene il punteggio specificato. Il metodo RankInBucket() esegue una stima del ranking all'interno del bucket. Il ranking del giocatore è la somma del grado più alto del bucket e il ranking all'interno del bucket specifico, che rappresenta il punteggio del giocatore. Dobbiamo sottrarre 1 dal risultato perché il ranking più alto del bucket in alto sarà 1, così come il ranking del miglior giocatore all'interno di un bucket specifico sarà 1.

I bucket vengono archiviati sia su Datastore che su Memcache. Per calcolare il ranking, leggi i bucket da Memcache (o da Datastore, se i dati mancano). Nella nostra implementazione di questo algoritmo, abbiamo utilizzato la libreria client NDB Python che utilizza memcache per memorizzare nella cache i dati archiviati in Datastore.

Poiché i bucket (o altri metodi) vengono utilizzati per rappresentare i dati in modo compatto, i ranking prodotti non sono esatti. Le posizioni all'interno di un bucket sono approssimate con l'interpolazione lineare. Altri metodi di interpolazione più precisi potrebbero essere utilizzati per una migliore approssimazione all'interno del bucket, come una formula di regressione.

Costo

Il costo per trovare un ranking e aggiornare il punteggio di un giocatore sono entrambi O(1), ovvero, indipendentemente dal numero di giocatori.

Il costo del job di query globale è pari a O(Players) * frequenza di aggiornamento della cache.

Il costo del calcolo dei dati del bucket nel job di backend è correlato anche al numero di bucket, poiché viene eseguita una query di conteggio per ciascun bucket. La query count è ottimizzata per l'utilizzo di una query basata solo su chiavi, ma anche così, è necessario recuperare l'elenco completo delle chiavi.

Vantaggi

Si tratta di un metodo molto veloce sia per l'aggiornamento del punteggio di un giocatore che per la ricerca della posizione in classifica di un punteggio. Anche se i risultati sono basati su un lavoro in background, se il punteggio di un giocatore cambia, il ranking mostrerà immediatamente un cambiamento nella direzione appropriata. Ciò è dovuto all'interpolazione utilizzata all'interno del bucket.

Poiché il calcolo del ranking più alto di un bucket viene eseguito in background con un job programmato, i punteggi del giocatore possono essere aggiornati senza dover mantenere sincronizzati i dati del bucket. Quindi, la velocità effettiva di aggiornamento dei punteggi dei giocatori non è limitata da questo approccio.

Svantaggi

È necessario considerare il tempo necessario per conteggiare i punteggi di tutti i giocatori, calcolare i ranking globali e aggiornare i bucket. Nei nostri test su una popolazione di dieci milioni di giocatori, il tempo impiegato per il nostro sistema di test su App Engine è stato di 8 minuti e 34 secondi. È più veloce rispetto alle ore necessarie per calcolare la posizione di ciascun giocatore, ma il compromesso è l'approssimazione dei punteggi all'interno di ogni categoria. Al contrario, l'algoritmo ad albero calcola gli "intervalli di bucket" (il nodo superiore dell'albero) in modo incrementale a intervalli di pochi secondi, ma presenta una maggiore complessità di implementazione e una velocità effettiva limitata.

In tutti i casi, il tempo per FindRank dipende anche dal recupero rapido dei dati (nodi bucket o ad albero) da Memcache. Se i dati vengono rimossi da memcache, questi devono essere recuperati di nuovo da Datastore e memorizzati di nuovo nella cache per le successive richieste FindRank.

Accuratezza

La precisione del metodo dei bucket dipende da quanti bucket ci sono, dal ranking del giocatore e dalla distribuzione dei punteggi. La Figura 9 mostra i risultati del nostro studio sull'accuratezza delle stime di ranking con numeri diversi di bucket.

I test sono stati effettuati su una popolazione di 10.000 giocatori con punteggi distribuiti uniformemente nell'intervallo [0-9999]. L'errore relativo è di circa l'1% anche per solo 5 bucket.

L'accuratezza diminuisce per i giocatori con un ranking elevato, soprattutto perché la legge dei grandi numeri non si applica quando si analizzano solo i punteggi più alti. In molti casi, potrebbe essere consigliabile utilizzare un algoritmo più preciso per mantenere la posizione di uno o duemila giocatori con i punteggi più alti. Il problema si riduce notevolmente, poiché ci sono meno giocatori da monitorare e il tasso aggregato di aggiornamenti è di conseguenza inferiore.

Nel test precedente, l'uso di numeri casuali distribuiti uniformemente, in cui la funzione di distribuzione cumulativa è lineare, favorisce l'uso dell'interpolazione lineare all'interno del bucket, ma l'interpolazione all'interno dei bucket funziona bene per qualsiasi distribuzione densa di punteggi. La Figura 10 mostra il ranking stimato ed effettivo per una distribuzione dei punteggi approssimativamente normale.

Figura 10: ranking stimato con distribuzione normale

In questo esperimento, è stata utilizzata una popolazione di 100 giocatori per testare l'accuratezza con un piccolo set di dati. Ogni punteggio è stato generato prendendo la media di 4 numeri casuali tra 0 e 100, che indica approssimativamente una normale distribuzione di punteggi. Il ranking stimato è stato calcolato utilizzando il metodo di query globale con interpolazione lineare su 10 bucket. Si può vedere che anche per set di dati molto piccoli e distribuzioni non uniformi i risultati sono molto buoni.