La nostra homepage video mostra ora un nuovo set di 24 raccomandazioni ad ogni aggiornamento, grazie al passaggio al weighted reservoir sampling (A-Res). Il cambiamento ha eliminato il problema della "griglia sempre uguale" che affliggeva il nostro precedente feed ordinato per punteggio.
Perché il vecchio approccio rovinava l'esperienza
Ogni due ore recuperiamo i video di tendenza più recenti da otto regioni e salviamo i risultati in una tabella SQLite. La soluzione ingenua consisteva nell'ordinare l'intero set in base a un punteggio di rilevanza e prendere i primi 24. Questo metodo garantisce che appaiano gli elementi con il punteggio più alto, ma garantisce anche che rimangano lì. Un singolo video virale può dominare la posizione 1 per giorni, e gli utenti vedono una griglia identica ogni volta che ricaricano la pagina.
Oltre all'esperienza di navigazione poco dinamica, l'ordinamento dell'intera tabella per ogni richiesta costringe SQLite a caricare una grande struttura temporanea in memoria, il che è uno spreco.
Cosa ci offre il weighted reservoir sampling
Il weighted reservoir sampling risolve due problemi contemporaneamente:
- Freschezza con bias – la probabilità che ogni video venga selezionato è proporzionale al suo peso (ad es. punteggio di rilevanza). Un video con il doppio del peso ha il doppio delle probabilità di apparire, ma nessun elemento ha un posto garantito.
- Efficienza della memoria – l'algoritmo mantiene solo un "reservoir" di dimensione fissa di k elementi (k = 24 per il nostro feed). Elabora lo stream in un unico passaggio, quindi la memoria rimane O(k) indipendentemente dal numero di candidati che arrivano.
L'idea di base è semplice. Mentre scansioniamo le righe in arrivo, assegniamo a ogni elemento una chiave casuale che incorpora il suo peso, quindi manteniamo i k elementi con le chiavi più alte.
L'algoritmo in pratica
Per ogni video:
- Generiamo un numero casuale uniforme u ∈ (0, 1).
- Calcoliamo una chiave k = u^(1/weight).
(Più alto è il peso, maggiore sarà la chiave attesa.) - Inseriamo l'elemento in un min-heap che memorizza le attuali k chiavi più alte.
Se l'heap supera la dimensione k, scartiamo la chiave più piccola.
Quando lo stream termina, l'heap contiene i 24 video che visualizzeremo.
Gestire i limiti dei numeri in virgola mobile
Quando il peso di un video è molto grande, u^(1/weight) collassa in un valore indistinguibile da 1.0 nell'aritmetica a doppia precisione, causando la condivisione della stessa chiave da parte di molti elementi pesanti e la perdita di casualità. La soluzione è lavorare nello spazio logaritmico:
- Calcoliamo
log_key = log(u) / weightinvece dell'espressione con l'esponente.
Poiché i logaritmi trasformano l'elevamento a potenza in moltiplicazione, l'ordine delle chiavi viene preservato evitando il crollo della precisione. Il calcolo non comporta praticamente costi aggiuntivi.
Checklist di implementazione
- Struttura dati: un min-heap (coda di priorità) di dimensione k mantiene le chiavi più grandi in modo efficiente (O(log k) per inserimento).
- Tipo numerico: utilizzare numeri in virgola mobile a 64 bit per u e per le chiavi basate sui logaritmi; forniscono una precisione ampia per gli intervalli di peso tipici.
- Controllo di coerenza statistica: eseguire un rapido test Monte-Carlo su un piccolo set di campioni. Se gli elementi con peso 10 appaiono circa dieci volte più spesso di quelli con peso 1, l'implementazione è corretta.
- Streaming a passaggio singolo: l'algoritmo non ha bisogno di conoscere in anticipo il numero totale di candidati, il che si adatta naturalmente al nostro cursore SQLite che restituisce le righe una alla volta.
In sintesi
Il weighted reservoir sampling consente a un servizio di raccomandazione video di mantenere la propria homepage aggiornata, rispettare i punteggi di rilevanza e rimanere leggero in termini di memoria, il tutto con un singolo passaggio su decine di migliaia di candidati. Spostando il calcolo della chiave nello spazio logaritmico e utilizzando un min-heap, il metodo rimane preciso ed efficiente.