Un dato che vale dieci minuti

Due app in una

Un’app per trovare parcheggio in zona. Sul telefono in realtà ci sono due app in una. La prima lavora in sottofondo e non ha interfaccia: ascolta i sensori, l’accelerometro, la connessione Bluetooth con l’auto che cade, il passaggio da fermo a passo, e quando conclude che la persona ha appena lasciato un parcheggio manda la posizione GPS di quel posto che si sta liberando. La seconda è quella che si apre con il dito: una mappa con le segnalazioni intorno, ognuna con il tempo passato da quando è arrivata. Chi segnala non fa nulla, chi cerca guarda la mappa. Il lavoro sui sensori sta tutto nel telefono e non è l’argomento di questo post. L’argomento è l’API in mezzo, quella che riceve le segnalazioni e risponde alle mappe.

Il disegno che chiunque farebbe in cinque minuti è una tabella: una riga per segnalazione con coordinate e orario, un indice geografico, una query che prende le righe dentro il rettangolo della mappa e più recenti di dieci minuti, un lavoro periodico che cancella le vecchie. Funziona, e in una città funziona anche bene. Il problema nasce quando le segnalazioni diventano milioni l’ora: ogni riga va scritta, indicizzata, letta pochissime volte e poi cancellata entro dieci minuti, e un database relazionale paga ognuno di questi passaggi, la cancellazione in particolare, perché le righe morte restano sul disco finché qualcuno non ripulisce. Si arriva a un database grande e indaffarato per conservare qualcosa che, per definizione, non va conservato.

Niente da conservare

La proprietà che ha deciso tutto è la durata del dato. Una segnalazione nasce, vale dieci minuti, muore. Non ha valore storico, non si corregge, non si aggiorna, non va mai riletta dopo la scadenza. Se il sistema perdesse per intero tutte le segnalazioni in memoria, nel giro di dieci minuti sarebbe come se non fosse successo nulla: i parcheggi si liberano di continuo e la mappa si riempie da sola. Non ha senso fare il backup di un dato che fra dieci minuti non serve più a nessuno, e non ha senso neanche scriverlo su disco.

Da qui la scelta dell’archivio: Redis, in memoria, senza persistenza, con la scadenza automatica delle chiavi che fa il lavoro di pulizia al posto di qualsiasi processo. Non si cancella nulla, si lascia che il dato scada. E accanto un database SQL per la sola cosa che invece ha valore nel tempo, cioè le statistiche di zona: quante segnalazioni arrivano in quel rettangolo in quell’ora, giorno dopo giorno. Posizioni esatte lì non ne entrano mai.

Restava da decidere come organizzare le chiavi, ed è il cuore di tutto.

La chiave tempo-zona

Ho diviso il mondo in rettangoli di un centinaio di metri di lato, più o meno quello che si vede sullo schermo di un telefono a una scala utile per cercare parcheggio. Un rettangolo si identifica con il suo vertice in alto a sinistra, cioè con una coppia di coordinate arrotondate alla terza cifra decimale: un millesimo di grado di latitudine sono circa centoundici metri. A quella coppia ho aggiunto il minuto corrente, e questa è la chiave, che ho chiamato tempo-zona: dove e quando, in una stringa.

Il valore associato alla chiave è una lista: le posizioni esatte dei parcheggi segnalati in quel rettangolo durante quel minuto. Quando arriva una segnalazione, l’API calcola la chiave dalle coordinate del telefono e dal minuto in corso, e aggiunge la posizione in coda alla lista. Se la chiave non esiste Redis la crea, e in quel momento le viene messa una scadenza di dieci minuti dal minuto a cui appartiene. Niente letture prima di scrivere, niente controlli di esistenza: un’operazione sola.

const (
    grid = 0.001             // a thousandth of a degree: ~111 m of latitude
    ttl  = 10 * time.Minute  // a report is worth ten minutes, then it is gone
)

// zoneKey builds the time-zone key for a point: the north-west corner
// of the cell that contains it, plus the minute (server time, never
// the phone's clock). Integers only: no prefix, no dots, every byte
// is paid once per key, and the keys are millions.
func zoneKey(lat, lon float64, t time.Time) string {
    north := int(math.Ceil(lat / grid)) // thousandths of a degree
    west := int(math.Floor(lon / grid))
    return fmt.Sprintf("%06d:%05d:%d", north, west, t.Unix()/60)
}

// expiresAt is the same for every report in the same minute, so
// setting it again on a later write never extends the key's life.
func expiresAt(t time.Time) time.Time {
    return time.Unix((t.Unix()/60)*60, 0).Add(ttl)
}

Per un’auto che si libera in centro a Milano alle 14:37 la chiave è 045466:09186:29878397: latitudine e longitudine del vertice in millesimi di grado, poi il minuto contato da Unix epoch, e la lista contiene stringhe come 45.46512,9.18603. Nella chiave non c’è un byte di troppo, niente prefisso e niente punti decimali, perché le chiavi sono milioni e ogni carattere si paga su ognuna; i due punti sono rimasti solo per leggerla a occhio. Il minuto lo decide il server quando riceve la segnalazione, non il telefono: gli orologi dei telefoni sono quasi sempre giusti, ma “quasi sempre” su milioni di dispositivi è un numero grande, e una segnalazione datata nel futuro non scadrebbe mai.

func (s *Server) report(w http.ResponseWriter, r *http.Request) {
    var rep struct{ Lat, Lon float64 }
    if err := json.NewDecoder(r.Body).Decode(&rep); err != nil {
        http.Error(w, "bad report", http.StatusBadRequest)
        return
    }
    now := time.Now().UTC()
    key := zoneKey(rep.Lat, rep.Lon, now)
    pos := fmt.Sprintf("%.5f,%.5f", rep.Lat, rep.Lon)

    pipe := s.redis.Pipeline()
    pipe.RPush(r.Context(), key, pos)
    pipe.ExpireAt(r.Context(), key, expiresAt(now))
    if _, err := pipe.Exec(r.Context()); err != nil {
        http.Error(w, "try again", http.StatusServiceUnavailable)
        return
    }
    w.WriteHeader(http.StatusAccepted)
}

Dieci chiavi per una mappa

Chi apre la mappa non manda il centro dello schermo: manda il vertice della cella che ha a schermo, già arrotondato ai millesimi di grado. È lo stesso calcolo della chiave, ma lo fa il telefono una volta, non l’API un milione di volte al minuto. L’API aggiunge il minuto e chiede a Redis dieci chiavi in una volta: quella del minuto corrente e le nove dei minuti precedenti. Dieci letture di liste in una sola andata e ritorno, su dati che stanno in memoria: la risposta è pronta in pochi millisecondi anche con il mondo intero dentro Redis, perché il costo non dipende da quante segnalazioni ci sono in totale, ma solo da quante ce ne sono in quel rettangolo negli ultimi dieci minuti.

// The phone sends the cell it is looking at, e.g. "045466:09186":
// the north-west corner in thousandths of a degree, computed once on
// the device. The API only appends the minute.
var cellRe = regexp.MustCompile(`^-?\d{5,6}:-?\d{5,6}$`)

func (s *Server) spots(w http.ResponseWriter, r *http.Request) {
    cell := r.URL.Query().Get("cell")
    if !cellRe.MatchString(cell) {
        http.Error(w, "bad cell", http.StatusBadRequest)
        return
    }
    minute := time.Now().Unix() / 60
    pipe := s.redis.Pipeline()
    reads := make([]*redis.StringSliceCmd, 10)
    for age := range reads {
        key := cell + ":" + strconv.FormatInt(minute-int64(age), 10)
        reads[age] = pipe.LRange(r.Context(), key, 0, -1)
    }
    if _, err := pipe.Exec(r.Context()); err != nil {
        http.Error(w, "try again", http.StatusServiceUnavailable)
        return
    }
    type bucket struct {
        Age   int      `json:"age"`   // minutes since the report
        Spots []string `json:"spots"` // "lat,lon"
    }
    out := make([]bucket, 0, 10)
    for age, cmd := range reads {
        if spots := cmd.Val(); len(spots) > 0 {
            out = append(out, bucket{Age: age, Spots: spots})
        }
    }
    json.NewEncoder(w).Encode(out)
}

La risposta è già divisa per minuto, perché il minuto sta nella chiave e non c’è nulla da ordinare o raggruppare:

[
  {"age": 0, "spots": ["45.46512,9.18603"]},
  {"age": 2, "spots": ["45.46588,9.18640", "45.46501,9.18720"]},
  {"age": 7, "spots": ["45.46550,9.18577"]}
]

Con questo il telefono disegna i classici segnaposto a goccia, con il colore che va dal verde di una segnalazione appena arrivata al grigio di una vecchia di nove minuti, e un contatore che parte dall’età ricevuta e si azzera a dieci. Non c’è bisogno di chiedere al server quando una segnalazione scade: lo sa già dal minuto della chiave, e dall’altra parte Redis la farà sparire esattamente nello stesso istante.

Se la persona si muove, la mappa non resta dentro un rettangolo. Il telefono allora manda anche i vertici dei rettangoli intorno, i tre per tre centrati su quello dello schermo, e l’API legge novanta chiavi invece di dieci, sempre in una sola andata e ritorno, sempre in millisecondi. E un parcheggio segnalato a un metro dal bordo di una cella non si perde mai per questo motivo, perché chi cerca riceve comunque le celle confinanti.

La Terra è tonda

L’unica accortezza di tutto il disegno. Un millesimo di grado di latitudine vale centoundici metri ovunque, ma un millesimo di grado di longitudine si restringe andando verso i poli: centoundici metri all’equatore, ottantatré a Roma, cinquantasette a Stoccolma. I miei “rettangoli” sono rettangoli solo all’equatore; più a nord diventano spicchi sempre più stretti. Non ho corretto la cosa, per due motivi. Le città con un problema di parcheggio stanno quasi tutte fra il sessantesimo parallelo nord e il quarantesimo sud, dove una cella è larga fra la metà e il doppio della sua altezza: una zona ancora sensata per uno schermo di telefono. E chi cerca riceve comunque le celle confinanti, quindi una cella stretta cambia la forma dell’area coperta, non la copertura. Verso i poli le celle diventano fettucce, e lì di parcheggio ne trovate quanto volete.

Quello che resta

Le statistiche di zona sono l’unico dato che sopravvive ai dieci minuti. Ogni segnalazione, dopo essere entrata nella lista, viene contata in una tabella zone_stats con il vertice della cella, l’ora e il numero di segnalazioni: un contatore, non una posizione. Il conteggio lo fa un worker che legge le segnalazioni da uno stream di Redis, le aggrega per cella e ora in memoria e scrive una riga per cella ogni minuto, quindi il database SQL riceve scritture che si contano a centinaia al minuto nel peggiore dei casi, non a milioni. Da lì vengono le mappe di calore di dove si libera più spesso un posto e a che ora, che è la parte del prodotto che vale nel tempo.

E se Redis muore? Si riavvia vuoto, e per dieci minuti la mappa è più povera del solito. Nessun ripristino, nessuna replica da promuovere, nessun dato da recuperare, perché non c’è nulla da recuperare. Quando ho fatto i conti per capire quanta memoria servisse davvero mi è venuta questa tabella, dove ogni posizione in lista costa intorno ai cinquanta byte, e dentro Redis in ogni istante vive solo un sesto delle segnalazioni di un’ora:

Un sistema che copre il mondo intero sta in una macchina con un gigabyte di memoria, e la crescita non cambia il disegno: quando una sola istanza non basta più, le chiavi si distribuiscono su un cluster Redis senza che l’API se ne accorga, perché una chiave tempo-zona è indipendente da tutte le altre. L’API stessa non ha stato, e si moltiplica dietro un bilanciatore quante volte serve.

Concludo

L’idea che ha retto tutto è una sola: la struttura dei dati deve assomigliare alla vita dei dati. Una segnalazione di parcheggio vive dieci minuti ed è utile solo a chi è lì in quei dieci minuti, quindi la chiave contiene il luogo e il minuto, l’archivio sta in memoria e dimentica da solo, e la domanda “cosa c’è intorno a me adesso?” diventa la lettura di dieci chiavi che il server non deve nemmeno cercare, perché le sa costruire. Il database relazionale resta per ciò che ha davvero una storia, i conteggi per zona, e riceve poche scritture ordinate invece di milioni di righe da cancellare.

Il limite del disegno è quello che si vede: la griglia è fissa, e se un giorno servisse una scala diversa, isolati interi o singole vie, bisognerebbe scegliere una seconda granularità e scrivere ogni segnalazione due volte, cosa che Redis regge senza fatica ma che va decisa prima. E la precisione di una segnalazione resta quella del GPS del telefono, qualche metro in città: per un parcheggio basta, per un posto numerato in un garage no, e non era quello il prodotto.