Come si progetterà una cache LRU "multithread" usando C ++ (unordered_map e Linkedlist)?

0

Si noti che si tratta di una cache LRU thread-safe (non semplicemente una cache LRU come specificato in link ). Non è un duplicato della domanda di progettazione della cache di LRU in quanto vi sono alcuni aspetti spinosi di Locking Hashtable / Linkedlist (LL) che non sono affrontati in altre domande di progettazione di LRU multithread.

L'approccio accreditato su come rendere la cache di LRU thread-safe in C ++ sembra essere dappertutto. Ho notato alcuni link che menzionano il fatto che bloccare sia Hashtable / LL è ok, mentre altri non affrontano direttamente il problema in C ++ e discutono vagamente su vari modi per farlo.

  • Qualcuno può descrivere un approccio funzionale ed efficiente utilizzando blocchi che includono ciò che è bloccato e quando si implementa una versione multithread della cache della LRU in C ++ link quindi tutte le operazioni get / set sono O (1)?

  • in che modo le cache come memcached by Facebook implementano il supporto multithreading?

posta Joe Black 14.08.2018 - 05:20
fonte

1 risposta

0

È possibile trovare un'implementazione C ++ open source di una hash-table / elenco basato su LRU Cache LRUCache.h e LRUCache.inl (nota: il" blocco apparente "in questa implementazione non è reale - le sue sole affermazioni per rilevare l'uso errato di thread non sicuri - per il codice che è sincronizzato esternamente ).

Puoi quindi trovare un semplice wrapper su questa cache che aggiunge la sincronizzazione interna condivisa (leggi blocchi e blocchi di scrittura) SynchronizedLRUCache.h e SynchronizedLRUCache.inl

E un piccolo test case ( Test.cpp # L721 per il wrapper di sincronizzazione: esistono altri test per LRUCache stesso.

Nota: anche se si utilizza un diverso set di classi di utilità per implementare LRUCache, l'implementazione di SynchronizedLRUCache rende chiaro come implementare la sincronizzazione utilizzando shared_lock / lock_guard.

    
risposta data 16.08.2018 - 03:38
fonte