# Cap. 19: Production Recommender Systems - TikTok

### Explain why building a scalable and real-time recommendation system is crucial for platforms like TikTok. How does TikTok's system differ from general-purpose deep learning frameworks?

> Alternative:
> - What unique challenges does TikTok face in terms of sparsity, dynamism, and non-stationary distribution? How do these challenges impact the design of their recommendation system?

TikTok nasce in un contesto molto particolare (mercato asiatico) con obiettivi abbastanza diversi dai classici sistemi di raccomandazione: se i sistemi classici hanno problemi nelle raccomandazioni real time (e nella gestione del feedback in tempo reale), TikTok nasce proprio come un sistema estremamente time sensitive, basato sulle sessioni e sulla generazione di raccomandazioni in real time.

Tecnicamente, mentre i sistemi classici fanno forte affidamento alla parte offline, TikTok può essere definito interamente online (o meglio, il suo modello integra parte offline e parte online in un modello unico dove i pesi possono essere ricalibrati a real time).

### Describe the key features of TikTok's recommendation system, Monolith. How does Monolith handle sparsity and dynamism in user data?

> Alternative:
> - Explain the concept of a "collisionless hash table" and its significance in Monolith's architecture. How does Monolith ensure that different IDs do not collide in the embedding space?
> - What is the purpose of the distributed worker-parameter server setting in Monolith's architecture? How does this setting enable online training and real-time adaptation?
> - How does TikTok's Hash Table address memory efficiency while handling sparse parameters? Describe the filtering methods used for IDs and the concept of timed expiration.

Il problema principale affrontato dagli sviluppatori di TikTok è la sparsità e la dinamicità degli utenti e degli item. Per risolvere questo problema è stata sviluppata una hash table collisionless e un sistema di selezione dinamica delle feature addestrato in real time utilizzando un architettura distribuita composta da due tipi di server: i Parameter Server (che memorizzano i parametri del modello) e i Worker (che si occupano di aggiornare i parametri).


### Explain the use of Cuckoo Hashing in the Hash Table. How does this hashing technique help with insertion, lookup, and deletion operations?

La tecnica del Cuckoo Hashing funziona come spiegato di seguito:

- ci sono due tabelle $T_1, T_2$ con due funzioni di hashing $h_1, h_2$
- quando si inserisce un valore, si prova a inserlo in in $h_1(A)$ (nella prima tabella).
- Se $h_1(A)$ è occupato da un valore $B$, si prova a spostare il valore B nella seconda tabella con $h_2(B)$
- (se a sua volta la locazione è occupata, si ripete fintanto che non si raggiunge una configurazione stabile)

Si può dimostrare che in una tale tipo di struttura le inserzioni e i lookup hanno costo $O(1)$ anche nel caso peggiore. Le cancellazioni invece sono un po' più problematiche.

TikTok utilizza queste tabelle per inserire e reperire online le feature. Per evitare la saturazione della memoria tali feature vengono filtrate in base alla loro occorrenza e ad altri filtri probabilistici (si è ossservato che feature usate poche volte non contribuiscono molto alla qualità del modello).

### What are the two main stages of Monolith's training process? Describe both the batch training and online training stages.

1) Batch training: viene caricato un dataset di train, richiesti i parametri attuali dal Parameter Server da aggiornare, riaddestrato il modello e i parametri ottenuti reinviati al PS
2) Online training: in questo caso i parametri vengono aggiornati periodicamente da un Worker addestrato sui dati in tempo reale in modo che il modello si adatti ai feedback dell'utente nel brevissimo termine.

### What is the role of the streaming engine in Monolith's architecture? How does it seamlessly switch between batch and online training?

Lo Streaming Engine è il componente che si occupa di "scegliere" se entrare in modalità online o batch training basato su Apache Flink e Kafka. Il primo si occupa di generare i dataset di train in tempo reale, il secondo di gestire le code di log con le feature e le azioni dell'utente.

In fase di online training il modello viene addestrato direttamente sui dati ottenuti da Flink, in fase di batch training si utilizzando dati memorizzati in precedenza.


### Explain the concept of online joiner. How does it handle user action logs and features to produce training examples for online learning?

L'online joiner è il modulo software utilizzato da Flink per generare i training set in tempo reale.

Associa ad ogni azione dell'utente una feature con un struttura dati chiave-valore e una cache fatta per gestire situazioni in cui l'utente non interagisce.

Per risolvere lo sbilanciamento della distribuzione delle azioni (il numero di azioni negative supera di gran lunga quello delle azioni positive) si utilizza il negative sampling.


### Describe the challenge of parameter synchronization between training and serving systems. How does Monolith handle this challenge using incremental on-the-fly parameter synchronization?

Sostituire i parametri del modello (a seguito di un addestramento) è un'operazione che potrebbe interrompere il servizio (si tratterebbe di un trasferimento di molti TeraByte). Per questo motivo in Monolith i parametri vengno sostituiti incrementalmente, senza mai interrompere il modello.

### How does TikTok manage its online model to provide real-time recommendations to users?

Il sistema di raccomandazione di TikTok è basato su Deep Factorization Machine.