Serveur de Cache
Presentation
Objectif principal : Un serveur de cache style Memcached. Les clients stockent des paires cle-valeur en memoire pour eviter d'aller en base de donnees. Avec politique d'eviction LRU quand c'est plein.
Technologies utilisees : C avec sockets pour le serveur, hash table pour le stockage, liste doublement chainee pour le LRU. Protocole texte simple (GET key, SET key value, DEL key).
Fonctionnalites cles : GET/SET/DEL rapides en O(1), LRU pour virer les vieilles entrees quand le cache est plein, stats (hit rate, memoire utilisee), multi-clients.
Livrables attendus : Serveur de cache avec limite de memoire configurable. Client CLI pour tester. Benchmarks de performance.
Calendrier previsionnel : Deux semaines. Le LRU efficace demande de combiner hash table et liste chainee, c'est un pattern classique mais fallait le comprendre.
Parties prenantes & criteres de succes : Projet pour comprendre le caching et les structures de donnees avancees. Aussi pour pratiquer la programmation systeme.
Le Defi
Faire le LRU en O(1). Naif c'est O(n) pour trouver le plus vieux. La solution c'est une liste doublement chainee ou on deplace au debut a chaque acces, et la hash table pointe directement vers les noeuds de la liste.
La Solution
Chaque entree du cache est un noeud avec prev/next. La hash table associe la cle a ce noeud. A chaque GET, je deplace le noeud au debut de la liste (O(1) grace aux pointeurs). Quand c'est plein, je vire le dernier de la liste.
Architecture Technique
Structure CacheEntry avec key, value, prev, next. Module lru.c qui gere la liste (move_to_front, evict_last). Module cache.c qui combine hash table et LRU. Module server.c pour les sockets et le parsing des commandes. Stats calculees en live.
Points Cles
- LRU en O(1)
- Limite memoire avec eviction
- Stats en temps reel (hit rate)
Apercu
Resultats & Apprentissages
100k ops/sec sur ma machine, c'est correct. Le LRU marche bien, le hit rate est bon sur des acces realistes. J'ai compris pourquoi les caches sont si importants et comment ils fonctionnent en vrai.
Evolutions Futures
Autres politiques d'eviction (LFU, FIFO). Slab allocation comme Memcached pour eviter la fragmentation. Clustering pour distribuer sur plusieurs serveurs.