Ranking rapido e affidabile in Datastore

Ranking: un problema semplice, ma al contempo molto complesso

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

Figura 1: Tomoaki Suzuki, ingegnere capo di App Engine presso Applibot, Inc.

Applibot è uno dei principali fornitori di applicazioni social in Giappone. L'unicità dell'azienda è rappresentata dalla 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 è riuscita a cogliere le opportunità di business nel mercato dei social game, non solo in Giappone, ma anche negli Stati Uniti. Applibot può certamente attestarne il successo. Legend of the Cryptids (Figura 2), uno dei suoi titoli più importanti, ha raggiunto il primo posto nella categoria Giochi dell'App Store di Apple in Nord America a ottobre 2012. La serie The 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, gioco al primo posto nell'Apple App Store a ottobre 2012.

Questi titoli sono stati in grado di scalare senza problemi e di gestire il traffico in costante crescita. Applibot non ha dovuto faticare per creare cluster complessi di server virtuali o database sharded. Ha sfruttato la potenza di App Engine e ha ottenuto scalabilità e disponibilità in modo efficiente.

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

  • Nel tuo gioco ci sono centinaia di migliaia (o più!) giocatori.
  • Ogni volta che un giocatore combatte contro i nemici (o esegue altre attività), il suo punteggio cambia.
  • Vuoi mostrare il ranking più recente del player sulla pagina di un portale web.

Come si calcola il ranking?

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

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

SELECT count(key) FROM Players WHERE Score > YourScore

Questa query conteggia tutti i giocatori che hanno un punteggio più alto del tuo (Figura 4). Vuoi eseguire questa query per ogni richiesta dalla pagina del portale? Quanto tempo occorre quando si ha un milione di giocatori?

Inizialmente Tomoaki ha implementato questo approccio, ma ogni risposta richiedeva alcuni secondi. Era troppo lento, troppo costoso e andava sempre più peggio con l'aumentare della scalabilità.

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

In seguito, Tomoaki ha provato a mantenere i dati del ranking in Memcache. È stato veloce, ma non affidabile. Le voci Memcache possono essere rimosse in qualsiasi momento e, a volte, il servizio Memcache stesso non era disponibile. Con un servizio di ranking che dipendeva esclusivamente da chiavi e valori in memoria, era difficile mantenere la coerenza e la disponibilità.

Come soluzione temporanea, Tomoaki ha deciso di ridurre il livello di servizio. Invece di calcolare il ranking per ogni richiesta, ha configurato un'attività pianificata che scansionava e aggiornava il ranking di ogni giocatore una volta all'ora. In questo modo, le richieste dalla pagina del portale potrebbero ottenere immediatamente il ranking del giocatore, ma potrebbero essere vecchie fino a un'ora.

Infine, Tomoaki cercava un'implementazione del ranking permanente, transazionale, veloce 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 è rivolto a Kaz Sato, Solutions Architect (SA) e Technical Account Manager (TAM) del team della piattaforma Google Cloud, che è stato assegnato ad Applibot in base a 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 da parte del team dell'assistenza clienti Google Cloud e all'assistenza aziendale da parte del team di vendita Cloud, Google assegna a ciascun cliente un Technical Account Manager (TAM).

Un TAM rappresenta il cliente per il team di Google Engineering, che crea l'infrastruttura cloud effettiva. I TAM comprendono in dettaglio il sistema e l'architettura del cliente e, dopo aver segnalato una richiesta critica, utilizzano le loro conoscenze e la loro rete come rappresentanti dell'ingegneria di Google all'interno dell'azienda per risolvere il problema. I TAM possono riassegnazione i problemi ai Solutions Architect del team o ai Software Engineer del team della piattaforma cloud. L'assistenza di livello premium è la strada rapida 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 al fine di trovare una soluzione che soddisfaceva 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 contare il ranking di un giocatore. La complessità temporale di questo algoritmo è O(n); ovvero il tempo necessario per l'esecuzione della query aumenta in modo proporzionale al numero di giocatori. In pratica, ciò significa che l'algoritmo non è scalabile. Abbiamo invece bisogno di un algoritmo O(log n) o più veloce, in cui il tempo aumenterà solo in modo logaritmico man mano che il numero di giocatori aumenta.

Se hai mai frequentato un corso di informatica, potresti ricordare che gli algoritmi ad albero, come gli alberi binari, gli alberi rosso-neri o gli alberi B, possono avere una complessità temporale di 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, ad esempio conteggio, massimo/minimo e media, memorizzando i valori aggregati in ogni 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 basato su albero per Datastore, scritto da un ingegnere di Google: la Google Code Jam Ranking Library.

Questa libreria basata su Python espone due metodi:

  • SetScore per stabilire il punteggio di un giocatore.
  • FindRank per ottenere il ranking di un determinato punteggio.

Quando le coppie giocatore-punteggio vengono create e aggiornate con il metodo SetScore, la libreria di ranking di Code Jam crea un albero N-ario1. Ad esempio, consideriamo un albero terziario che può contare il numero di giocatori con punteggi compresi tra 0 e 80 (Figura 5). La libreria memorizza il nodo principale, che contiene tre numeri, come un'entità. Ogni numero corrisponde al numero di giocatori con punteggi rispettivamente negli intervalli 0-26, 27-53 e 54-80. Il nodo principale ha un nodo secondario per ogni intervallo, contenente a sua volta tre valori per i giocatori negli intervalli dell'intervallo secondario. La gerarchia ha bisogno di quattro livelli per memorizzare il numero di giocatori per 81 diversi valori del punteggio.

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

Per determinare il ranking di un giocatore con un punteggio di 30, la libreria deve leggere solo quattro entità, ovvero 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 del 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 a Datastore aumenterà solo in O(log n) e non è influenzato dal numero di giocatori. In pratica, la libreria di ranking Code Jam utilizza 100 (invece di 3) come numero predefinito di valori per nodo, quindi è necessario accedere solo a due (o tre, se l'intervallo di punteggio è 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 lavora con complessità temporale O(log n).

Gli aggiornamenti simultanei limitano la scalabilità

Tuttavia, durante il test di carico, Kaz ha individuato un limite critico nella libreria di ranking 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 ripetizione della transazione. Era ovvio che la libreria non poteva soddisfare il requisito di 300 aggiornamenti al secondo di Applibot. Poteva gestire solo circa l'1% di questo throughput.

Perché? Il motivo è il costo per mantenere la coerenza dell'albero. In Datastore, devi utilizzare un gruppo di entità per garantire la coerenza forte quando aggiorni più entità in una transazione. Consulta "Equilibrare la coerenza forte e quella eventuale con Google Cloud Datastore". La libreria di ranking di Code Jam utilizza un singolo gruppo di entità per contenere l'intero albero al fine di garantire la coerenza dei conteggi negli elementi dell'albero.

Tuttavia, un gruppo di entità in Datastore ha una limitazione delle prestazioni. Datastore supporta solo circa una transazione al secondo in un gruppo di entità. Inoltre, se lo stesso gruppo di entità viene modificato in transazioni concorrenti, è probabile che queste non vadano a buon fine e debbano essere ripetute. La libreria di ranking di Code Jam è fortemente coerente, transazionale e abbastanza veloce, ma non supporta un volume elevato di aggiornamenti simultanei.

Soluzione del team di Datastore: aggregazione dei job

Kaz ricordava che un ingegnere informatico del team Datastore aveva menzionato 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 transazione separata. Tuttavia, poiché la transazione include un numero elevato di aggiornamenti, ogni transazione richiede più tempo, aumentando la possibilità di conflitti con le transazioni concorrenti.

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

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

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

Tuttavia, il pattern di aggregazione dei job presenta un svantaggio: utilizza un solo thread per aggregare tutti gli aggiornamenti e questo impone un limite alla velocità con cui può inviare gli aggiornamenti a Datastore. Di conseguenza, è stato importante determinare se l'aggregazione dei job poteva soddisfare il requisito di velocità effettiva di 300 aggiornamenti al secondo di Applibot.

Aggregazione dei job per coda pull

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

  • Frontend: accetta SetScore richieste dagli utenti e le aggiunge come attività a una coda in modalità pull.
  • Coda pull: riceve e trattiene le richieste di aggiornamento di SetScore dal frontend.
  • Backend: esegue un loop 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, ovvero un tipo di coda di attività in App Engine che consente agli sviluppatori di implementare uno o più worker che utilizzano le attività aggiunte alla coda. L'istanza di backend ha un singolo thread in un loop 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 gruppo in un'unica transazione. La transazione potrebbe essere aperta per un secondo o più, ma poiché esiste un singolo thread che gestisce la libreria e Datastore, non esistono conflitti e problemi di modifica simultanei.

L'istanza di backend è definita come 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 è definita come istanza con scalabilità manuale. In un determinato momento è in esecuzione una sola istanza di questo tipo.

Kaz ha eseguito un test di carico del POC utilizzando JMeter. Ha confermato che il PoC è stato in grado di elaborare 200 richieste SetScore al secondo, con batch di 500-600 aggiornamenti per transazione. L'aggregazione delle offerte di lavoro funziona.

Sharding della coda per prestazioni stabili

Ma Kaz scoprì presto un altro problema. Mentre continuava a eseguire il test per diversi minuti, ha notato che il throughput della coda pull variava di volta in volta (Figura 6). In particolare, quando ha continuato ad aggiungere richieste alla coda con 200 attività al secondo per diversi minuti, la coda smette improvvisamente di trasferire le attività al backend e la latenza per ogni attività è aumentata drasticamente.

Figura 6: fluttuazione del rendimento della coda in modalità pull.

Kaz si è consultato con il team della coda di attività per capire il motivo. Secondo il team delle code di attività, si tratta di un comportamento noto per l'attuale implementazione della coda in modalità pull che dipende da Bigtable come livello di persistenza. Quando un tablet Bigtable diventa troppo grande, viene suddiviso in più tablet. Durante la suddivisione del tablet, le attività non vengono consegnate e questo crea la fluttuazione delle prestazioni quando la coda riceve attività ad alta velocità. Il team di Task Queue si sta adoperando per migliorare queste caratteristiche di prestazioni.

Michael Tang, un Solutions Architect, ha consigliato una soluzione alternativa utilizzando lo sharding delle code. Invece di 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 sta elaborando 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 ciclo di istanze di backend migliorato esegue il seguente algoritmo:

  1. Lease di SetScore attività da 10 code.
  2. Chiama il metodo SetScores con le attività.
  3. Elimina le attività noleggiate dalle code.

Nel passaggio 1, ogni coda fornisce fino a 1000 attività, ognuna contenente il nome di un giocatore e un punteggio. Dopo aver aggregato tutte le coppie giocatore-punteggio in un dizionario, il passaggio 2 passa il gruppo 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 le attività in leasing dalle code.

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 come watchdog in modalità di attesa, pronto a prendere il controllo in caso di guasto della prima istanza.

La soluzione proposta: esecuzione a 300 aggiornamenti al secondo sostenuti2

La Figura 7 mostra il risultato del test di carico dell'implementazione finale del PoC 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 un carico standard, ogni aggiornamento viene applicato a Datastore entro pochi secondi dalla ricezione della richiesta.

Figura 7: grafico del rendimento della soluzione.

Questa soluzione soddisfa tutti i requisiti originali di Applibot:

  • Scalabile per gestire decine di migliaia di giocatori.
  • Persistenti e coerenti in quanto tutti gli aggiornamenti vengono eseguiti nelle transazioni di Datastore.
  • Abbastanza veloce da gestire 300 aggiornamenti al secondo.

Con i risultati dei test di carico e il codice PoC, Kaz ha presentato la soluzione a Tomoaki e ad altri ingegneri di Applibot. Tomoaki prevede di incorporare la soluzione nel proprio sistema di produzione, si aspetta 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 dell'albero del ranking con aggregazione dei job

La soluzione proposta presenta diversi vantaggi e un solo svantaggio:

Vantaggi:

  • Veloce: la chiamata FindRank richiede alcune centinaia di millisecondi o meno.
  • Veloce: SetScore invia semplicemente un'attività, che viene elaborata dal backend in pochi secondi.
  • A elevata coerenza e persistente in Datastore.
  • I livelli sono accurati.
  • Scalabile per qualsiasi numero di giocatori.

Svantaggio:

  • La velocità effettiva ha una limitazione (circa 300 aggiornamenti/sec con l'implementazione attuale).

Poiché questa soluzione utilizza il pattern di aggregazione dei job, si basa su un singolo thread per aggregare tutti gli aggiornamenti. Sono necessari ulteriori interventi o complessità per raggiungere un throughput superiore a 300 aggiornamenti/sec con l'attuale potenza della CPU delle istanze App Engine e le prestazioni di Datastore.

Soluzione più scalabile con albero suddiviso

Se hai bisogno di una frequenza di aggiornamento ancora maggiore, potrebbe essere necessario eseguire lo sharding dell'albero dei ranking. Dovresti creare più implementazioni del sistema precedente: un insieme di code che gestiscono ciascuna un modulo di backend che aggiorna la propria struttura ad albero del ranking.

In generale, non è necessario né previsto il coordinamento degli alberi. Nel caso più semplice, ogni aggiornamento di SetScore viene inviato in modo casuale a una coda. Con tre alberi di questo tipo, ciascuno con il proprio gruppo di entità Datastore e il proprio server di backend, il throughput di aggiornamento previsto sarebbe tre volte superiore. Lo svantaggio è che FindRank deve interrogare ogni albero dei ranking per ottenere il ranking di un punteggio, quindi sommare il ranking di ogni albero per trovare il ranking effettivo, operazione che richiede un po' più di tempo. Il tempo di query per FindRank può essere ridotto notevolmente mantenendo le entità in Memcache.

Questo è simile al noto approccio che utilizza i contatori suddivisi in parti: ogni contatore viene incrementato in modo indipendente e la somma totale viene calcolata solo quando è necessaria al cliente.

Ad esempio, con tre alberi, FindRank(865) potrebbe trovare i tre ranking 124, 183 e 156, a indicare che ogni albero contiene il rispettivo numero di punteggi superiori a 865. Il numero totale calcolato di punteggi superiori a 865 è 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 i problemi di ranking di grandi volumi.

Soluzioni più scalabili con approcci approssimativi

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

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

I bucket con query globali sono una soluzione alternativa proposta dal team di Datastore e da Alex Amies, un TAM. Alex ha implementato un PoC basato sull'idea del team di Datastore e ha condotto un'analisi approfondita delle prestazioni. Ha dimostrato che i bucket con query globali sono una soluzione di ranking scalabile con un degrado minimo dell'accuratezza del ranking e potrebbero essere adatti per applicazioni che richiedono un throughput superiore alla libreria di ranking di Code Jam. Consulta l'Appendice per una descrizione dettagliata e i risultati dei test.

Il metodo di conteggio con perdita e lo streaming parsimonioso sono i cosiddetti algoritmi online e algoritmi di streaming in cui è possibile utilizzare uno spazio di archiviazione in memoria molto ridotto per calcolare una stima stocastica dei migliori giocatori da uno stream di coppie giocatore-punteggio. Questi algoritmi sarebbero adatti per applicazioni che richiedono una latenza molto bassa e una larghezza di banda estremamente elevata, come migliaia di aggiornamenti al secondo, con una precisione e una copertura più limitate dei risultati del ranking. Ad esempio, se vuoi avere una dashboard in tempo reale che mostri le 100 parole chiave più cercate in uno stream di social network, questi algoritmi possono aiutarti.

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 collaborato a stretto contatto con il cliente e con i team di ingegneria di Google per affrontare la sfida e fornire una soluzione che potesse ridurre la latenza dell'aggiornamento del ranking da un'ora a pochi secondi. I pattern di progettazione scoperti durante il processo, ovvero l'aggregazione dei job e lo sharding delle code, potrebbero essere applicati anche a problemi comuni in altri design di sistema basati su Datastore che richiedono centinaia di aggiornamenti al secondo con una forte coerenza.

Note

  1. La libreria di ranking di Code Jam accetta un parametro chiamato "fattore di ramificazione" che specifica il numero di punteggi che ogni entità conterrà. Per impostazione predefinita, la libreria utilizza il parametro 100. In questo caso, i punteggi da 0 a 9999 verranno memorizzati su 100 entità come figli del nodo radice. Se devi gestire una gamma più ampia di punteggi, puoi modificare il fattore di ramificazione impostandolo su un valore più alto per ottimizzare il numero di accessi alle entità.
  2. Tutti i dati sulle prestazioni descritti in questo articolo sono valori campionati come 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 questi punti dati da utilizzare per il calcolo dei ranking di determinati giocatori. L'intervallo totale dei punteggi è partizionato in "bucket". Ogni categoria è caratterizzata da un sottointervallo di punteggi e dal numero di giocatori con punteggi compresi in quell'intervallo. Da questi dati, è possibile trovare il ranking di qualsiasi punteggio con un'approssimazione molto accurata. Questi bucket sono simili al nodo di primo livello nell'albero del ranking, ma invece di passare a nodi più dettagliati, questo algoritmo esegue l'interpolazione solo all'interno di un bucket.

Il recupero del ranking da parte degli utenti dal frontend è disaccoppiato dal calcolo del ranking sui bucket nel backend per ridurre al minimo il tempo necessario per trovare un ranking. Quando viene richiesto il ranking di un giocatore, viene trovato il bucket appropriato in base al suo punteggio. Il bucket include un limite di livello 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 modo coerente in meno di 400 millisecondi per un round trip HTTP completo. Il costo del metodo FindRank non dipende dal numero di giocatori della popolazione.

Calcolo del ranking per un determinato punteggio

Figura 8: distribuzione dei punteggi nei bucket.

Per ogni bucket vengono registrati il numero 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 un punteggio di 60, esaminiamo 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 job cron o una coda di attività, i conteggi per ogni bucket vengono calcolati e salvati mediante l'iterazione su tutti i bucket. Questa viene chiamata query globale, perché calcola i parametri necessari per stimare i ranking esaminando i punteggi di tutti i giocatori. Di seguito è riportato il codice Python di esempio per eseguire questa operazione in base ai punteggi nell'intervallo [low_score, high_score] per ogni 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 ogni giocatore con punteggi compresi nell'intervallo coperto dal bucket. Poiché Datastore mantiene un indice ordinato per i punteggi dei giocatori, questo conteggio può essere calcolato in modo efficiente.

Quando abbiamo bisogno di trovare il ranking di un determinato giocatore, possiamo usare il codice 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 livello più alto del bucket e il livello all'interno del bucket specifico che rappresenta il punteggio del giocatore. Dobbiamo sottrarre 1 dal risultato perché il ranking più alto del bucket principale sarà 1 e anche il ranking del giocatore migliore all'interno di un bucket specifico sarà 1.

I bucket vengono archiviati sia in Datastore sia in Memcache. Per calcolare il ranking, leggi i bucket da Memcache (o da Datastore, se in Memcache mancano i dati). Nella nostra implementazione di questo algoritmo, abbiamo utilizzato la libreria client NDB di 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 ranghi prodotti non sono esatti. I ranking all'interno di un bucket vengono approssimati con interpolazione lineare. Per una migliore approssimazione all'interno del bucket, potrebbero essere utilizzati altri metodi di interpolazione più precisi, ad esempio una formula di regressione.

Costo

Il costo per trovare un livello e aggiornare il punteggio di un giocatore è entrambi O(1); indipendente dal numero di giocatori.

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

Il costo del calcolo dei dati dei 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 in modo da utilizzare una query basata solo su chiavi, ma anche in questo caso è necessario recuperare l'elenco di chiavi completo.

Vantaggi

Questo metodo è molto veloce sia per aggiornare il punteggio di un giocatore sia per trovare il ranking di un punteggio. Anche se i risultati si basano su un job in background, se il punteggio di un giocatore cambia, il ranking mostrerà immediatamente una variazione nella direzione appropriata. Questo è dovuto all'interpolazione utilizzata all'interno del bucket.

Dal momento che il calcolo del livello più alto di un bucket viene eseguito in background con un job pianificato, i punteggi del giocatore possono essere aggiornati senza dover mantenere sincronizzati i dati del bucket. Pertanto, la produttività dell'aggiornamento dei punteggi dei giocatori non è limitata da questo approccio.

Svantaggi

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

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

Accuratezza

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

Figura 9: variazione della precisione con il numero di bucket.

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

La precisione diminuisce per i giocatori con valutazioni elevate, soprattutto perché la legge dei grandi numeri non si applica quando si osservano solo i punteggi migliori. In molti casi, potrebbe essere consigliabile utilizzare un algoritmo più preciso per mantenere i ranking di uno o duemila giocatori con i migliori punteggi. Il problema si riduce notevolmente, perché ci sono meno player da monitorare e il tasso aggregato di aggiornamenti è di conseguenza inferiore.

Nel test precedente, l'utilizzo di numeri casuali distribuiti uniformemente, in cui la funzione di distribuzione cumulativa è lineare, favorisce l'utilizzo 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 approssimativamente normale dei punteggi.

Figura 10: Rango 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 calcolando la media di 4 numeri casuali compresi tra 0 e 100, che approssima approssimativamente una distribuzione normale dei punteggi. Il ranking stimato è stato calcolato utilizzando il metodo di query globale con interpolazione lineare su 10 bucket. È possibile notare che anche per set di dati molto piccoli e distribuzioni non uniformi i risultati sono molto buoni.