In che modo il lease token risolve il problema dei set stantii nei server memcached di Facebook?

La ragione per cui non stai capendo come funziona è perché stai facendo un piccolo ma importante presupposto sbagliato. Tu scrivi:

Supponiamo che il client A abbia cercato di ottenere la chiave K, ma è un miss. Ottiene anche il token di locazione L1. Allo stesso tempo, anche il client B cerca di recuperare la chiave K, ma è di nuovo un fallimento. B ottiene il lease token L2 > L1. Entrambi hanno bisogno di recuperare K dal DB.

Tuttavia, questo non accadrà perché se il server memcached ha recentemente dato un lease token, non ne darà un altro. In altre parole, B non riceve un lease token in questo scenario. Invece ciò che B riceve è un risultato di hot miss che dice al client B che un altro client (cioè il client A) è già diretto al DB per quel valore, e che il client B dovrà riprovare più tardi.

Quindi, i lease funzionano in pratica perché solo un client è diretto al DB in qualsiasi momento per un particolare valore nella cache.

Inoltre, quando arriva una nuova cancellazione, memcached saprà che il prossimo lease-set (quello del client A) è già stantio, quindi accetterà il valore (perché è più nuovo) ma lo segnerà come stantio e il prossimo client a chiedere quel valore otterrà un nuovo token di lease, e i client successivi otterranno ancora una volta risultati hot miss.

Nota anche che i risultati hot miss includono l'ultimo valore stantio, così un client può prendere la decisione di andare avanti con dati leggermente stantii, o riprovare (tramite backoff esponenziale) per ottenere i dati più aggiornati possibili.