FLeeC: a Fast and Lock-Free Applicational Cache

Abstract

Access to data in applications that make use of external storage systems (e.g., Databases) can be a major performance bottleneck. A common solution is to first query a cache application to reduce data access overhead. These cache applications leverage fast main memory access rates and the parallelism capabilities of hardware to provide high performance. To this end, a cache application needs a concurrency control mechanism to maintain correctness under conflicting concurrent accesses, of which mutual-exclusion locks (blocking concurrency control) are the most common mechanism used. Blocking concurrency control strategies fail to provide a high level of performance when under medium to high contention, as the pessimistic nature of blocking concurrency can not completely avoid needlessly synchronizing operations that do not conflict. Conversely, non-blocking (or lock-free) concurrency control strategies can provide high degrees of performance in parallel shared memory contexts, especially in high contention scenarios. This work proposes FLeeC, an application-level cache system based on Memcached, which leverages non-blocking re-designed data structures concurrency to improve performance by allowing any number of concurrent writes and reads to its main data structure. FLeeC features a hash table with embedded eviction policy to allowthe correct functioning of its non-blocking algorithms; a memory reclamation scheme adapted to cache semantics; a non-blocking hash table expansion mechanism to preserve the strong progress guarantees that non-blocking concurrency provides; and dedicated replacement algorithm to minimize false misses that can occur in non-mutually exclusive environments. We have extensively evaluated FLeeC under varied scenarios and workloads and found that, when compared to Memcached, it is capable of achieving 6× higher performance when under high contention scenarios, 1.2× higher performance when under low contention scenarios and equivalent performance in scenarios with no contention. FLeeC can thus be used to further improve the performance of any application that currently uses Memcached

O acesso a dados pode ser uma limitação de desempenho em aplicações que utilizam sistemas de armazenamento externos (e.g. Bases de dados). Uma solução comum consiste em primeiro fazer pedidos a uma cache aplicacional par reduzir o custo associado ao acesso a dados. As caches aplicacionais aproveitam a velocidade de acesso à memória principal assim como as capacidades de paralelismo presentes no hardware para proporcionar alto desempenho. Para este fim, uma cache aplicacional precisa de mecanismos de controlo de concorrência para garantir correção na presença de acessos concorrentes conflituosos. O mecanismo de controlo de concorrência mais comum baseia-se em garantir exclusão mútua em acessos a estruturas de dados. Estes mecanismos (bloqueantes) não conseguem fornecer um alto teor de desempenho quando os níveis de contenção são médio-altos, pois a sua natureza pessimista não consegue evitar totalmente sincronização entre duas operações não conflituosas. Por outro lado, mecanismos de controlo de concorrência não bloqueantes permitem alto desempenho, especialmente em cenários de alta contenção. Este trabalho propõe o FLeeC, uma cache aplicacional baseada no Memcached, que aproveita estruturas de dados redesenhadas não bloqueantes paa melhorar o desempenho ao não restringir o número de escritas e leituras feitas concorrentemente na sua estrutura de dados principal. O FLeeC tem uma hash table com uma política de eviction embebida com o fim de garantir correção na utilização de algoritmos não bloqueantes; um esquema de reutilização de memória adaptado às semânticas de uma cache; um algoritmo não bloqueante de expansão da sua hash table para manter garantias de progresso fortes provenientes da filosofia não bloqueante; e um algoritmo de substituição que minimiza cache misses falsos que pode acontecer na ausência de exclusão mútua. Avaliámos extensivamente o FLeeC sob vários cenários e descobrimos que, quando comparado com o Memcached, o FLeeC é capaz de ter 6× mais desempenho em cenários de alta contenção, 1.2× mais desempenho em cenários de baixa contenção e desempenho equivalente na ausência de contenção. O FLeeC pode então ser utilizado para melhorar o desempenho de qualquer aplicação que atualmente utilize o Memcached.