Redis - REmote DIctionary Server

Thursday, 12 February 09
Per ora sto lavorando finalmente, nuovamente, ad un progetto che ho in mente da piu' di un anno. Avete presente memcached? Immaginatelo persistente, e con funzioni piu' avanzate secondo me irrinunciabili per non avere solo una semplice cache ma una alternativa ai database relazionali.

Il tutto sara' rilasciato sotto una licenza BSD. E' da qualche settimana che ci ho rimesso le mani e sono vicino ad avere un prototipo funzionante. Mentre Fabio sta scrivendo una lib per accedere al server via PHP. E' il momento giusto per rivere feedbacks, per cui posto di seguito parte del README che fa capire come funziona il database e cosa offre di preciso. Grazie per qualunque feedback.

Redis non ha alcuna dipendenza, e' scritto in C, e richiede un sistema POSIX per girare.

REDIS - REmote DIctionary Server

============= WHAT'S REDIS? =============

Redis is a database. To be more specific redis is a very simple database implementing a dictionary where keys are associated with values. For example I can set the key "surname_1992" to the string "Smith".

Redis takes the whole dataset in memory, but the dataset is persistent since from time to time it writes a dump of the dataset on disk. The dump is loaded every time the server is restarted.

This means that it can happens that after a system crash the last modifications of the dataset are lost, but it's the price to pay for a lot of speed. Redis is the right database for all the applications where it is acceptable after a crash that some modification gets lost, but where speed is very important.

However you can configure Redis to save the DB after a given number of modifications and/or after a given amount of time since the last change in the dataset. Saving happens in background so the DB will continue to server queries while it is saving the DB dump on disk.

================================= HOW REDIS DIFFERS FROM MEMCACHED? =================================

Maily in two ways:

- Memcached is not persistent, it just holds everything in memory without saving since its main goal is to be uesd as a cache. Redis instead can be used as the main DB for the application. - Like memcached Redis uses a key-value model, but while keys can just be strings, values in Redis can be lists and sets, and complex operations like intersections and concatenations can be performed against sets and lists.

================ REDIS DATA TYPES ================

Redis support the following three data types as values:

- Strings: just any sequence of bytes. Redis strings are binary safe so they can not just hold text, but images, copressed data and everything else. - Lists: lists of strings, with support for operations like append a new string on head, on tail, list length, obtain a range of elements, truncate the list to a given length, sort the list, and so on. - Sets: an unsorted set of strings. It is possible to add or delete elements from a set, to perform set intersection, union, subtraction, and so on.

Values can be Strings, Lists or Sets. Keys can be a subset of strings not containing newlines ("\n") and spaces (" ").

Implementation details ----------------------

Strings are implemented as dynamically allocated strings of characters. Lists are implemented as doubly liked lists with cached length. Sets are implemented using hash tables that use chaining to resolve collisions.
post letto 5393 volte (1.7 letture al giorno in media)
Postato alle 16:32:13 permalink | 16 commenti | stampa | posta | trackbacks

Commenti

ludo Scrive:
12 Feb 09, 23:08:16
Bel progetto!

Potrebbe essere usato come "poor man's message queue" sfruttando le liste.

Se ti interessa un client Python fammi un fischio. Io lo userei volentieri anche in alfa su BlogBabel.
antirez Scrive:
13 Feb 09, 18:28:51
Ciao Ludo!

esatto, come per INCR/DECR di memcachediana memoria e presenti anche in redis, sono presenti operazioni atomiche anche con le liste, come popl e popr (rispettivamente prendono e rimuovono atomicamente un elemento dalla testa e dalla coda della lista).

Altri algoritmi possono essere implementati grazie alla funzione 'randomkey' che ritorna una chiave a
caso in O(1) e 'poprandomkey' che ritorna la chiave
e il suo valore rimuovendola. Questa funzione fa
assomigliare Redis ad un 'tuple space' dove vari
"consumatori" in una computazione distribuita possono
prendere delle chiavi, processarle, restituirle "computate" in un server diverso.

Insomma ce la mettero' tutta perche' ci siano delle funzioni che permettano l'implementazione di algoritmi distribuiti locking free.

Riguardo al client Python, certamente! E' molto interessante. Fabio lo scrive per PHP, a Kiurma lo scriviamo per Ruby, se potessi fare quello Python la triade sarebbe completa :) Grazie mille, ti scrivo una email con i link non appena ho una alpha un po' piu' completa. Ce l'ho gia' a dire il vero ma le operazioni sulle liste non sono complete, almeno vorrei finire queste, per le operazioni tra i set forse ci vorra' qualche settimana in piu'.

Grazie!
ludo Scrive:
13 Feb 09, 21:02:30
Ottimo. E' proprio quello che cercavo da un po', mi sembra un progetto super interessante. :)

Per il client Python fammi un fischio quando sei pronto, ovviamente sono curioso di vedere la "bestia" in funzione, il client è una scusa per averlo subito (scherzo).

L'email dovresti averla, comunque ludo_at_qix_it.
davidonzo Scrive:
14 Feb 09, 10:03:36
Sarebbe l'ideale per whoishim.
Abbiamo scelto di fare valutazione di ogni motore come *mondo* a se stante e pure particolareggiata per la stringa. Ergo, una miriade di chiamate al database, che comunque è strutturalmente abbastanza semplice.

Appena rilasciate qualcosa mi piacerebbe implementarlo lì e vedere il guadagno. Le perdite occasionali di dati non sono un problema.
capobecchino Scrive:
14 Feb 09, 15:37:07
@antirez: come fare per poterti contattare in privato? ho provato alla tua mail ma non rispondi :(
antirez Scrive:
14 Feb 09, 15:52:46
@ludo: ok ci siamo quasi :) credo che tra una settimana si puo' gia' iniziare a testare. Lo stato attuale e' un core che funziona bene con i client di test ma supporta solo le operazioni sulle stringhe e alcune di base sulle liste. Il tutto e' stabile, testato con valgrind, fixati bachi, memory leaks, e il comportamento in caso di comandi spediti in pipelining e altre situazioni che probabilmente si presenteranno nella pratica. Credo che tra 1 settimana ti spedisco la prima beta. Sure l'email ce l'ho :)

@davidonzo: tante chiamate + strutturalmente semplice = probabilmente potreste usare Redis senza problemi :)
Redis sara' la struttura su cui poggia il nuovo LLOOGG, e probabilmente anche altri due progetti che per via di partnership avranno alti carichi. In tutti e tre i casi l'approccio e' misto: tutte le tabelle di "dati puri" e in grandi quantita' stanno su Redis, cose invece come le tabelle degli utenti ed altre cose dove e' desiderabile fare query di alto livello stanno su MySQL. Ti faccio sapere presto.

@capobecchino: scusami a volte non vedo le email, non leggo la posta con moltissima attenzione visto che non riesco ad accettare il tempo che ci vuole per leggerla bene... ti prego di rispedirmi questa email con un subject esplicativo! Grazie mille.

Non so come fare questo atteggiamento sembra quasi altezzoso, credimi chiunque mi conosce ti potra' dire che sono abbastanza umile da non fare queste minchiate, e' che ODIO l'email, come il telefono ;)
ludo Scrive:
17 Feb 09, 07:57:30
Ottimo, aspetto la tua mail con il sorgente allora. Se avessi voglia/tempo di descrivere il protocollo di comunicazione con i client potrei farmi un'idea di cosa c'è da fare, ma va benissimo anche un'occhiata al client PHP (che immagino sia nei sorgenti che mi mandi).
Doxaliber Scrive:
17 Feb 09, 19:31:33
Sembra una cosa davvero interessante. Attendo la beta per poterlo provare personalmente.
antirez Scrive:
17 Feb 09, 20:18:04
Prima di rispondere agli ultimi due commenti un aggiornamento: in questi giorni ho implementato il supporto per DB multipli e l'operazione atomica MOVE che sposta una chiave da un DB ad uno diverso atomicamente. In questo modo ad esempio in nel DB 0 ci possono essere delle chiavi da processare da parte di N clients workers, quando uno acquisisce una chiave sul DB 0 grazie a "RANDOMKEY" lo fa facendo un MOVE sul DB 1, move che fallisce se la chiave esiste gia' nel DB 1 o se non esiste piu' nel DB 0: in pratica e' un meccanismo di locking. Poi la chiave sara' processata da chi la acquisisce e la riposta scritta nel DB 2, tanto per fare un esempio.

Era facile implementare questo supporto multi-DB e mi e' sembrato utile farlo subito. Di conseguenza ho aggiornato il formato di dump sul disco che ora salva tutti i DB. D'altra parte se non si usa il comando SELECT che seleziona il DB tutte le connessioni sono per default sul DB 0 e dunque si comporta come memcached come se fosse un unico dizionario.

Altra modifica degli ultimi giorni, la GET zero-copy, in pratica il buffer di uscita ora e' una lista di buffer, e gli oggetti sono dotati di reference counter, dunque nel buffer di output ci stanno gli stessi oggetti, referenziati magari N volte in diversi buffer, e questo aumenta le prestazioni in maniera sensibile.

Ora pero' ho fatto talmente modifiche che sto ritestando tutte le funzioni con valgrind, leaks, eccetera dunque a questo punto sto scrivendo una piccola suite di test automatica da far girare ad ogni modifica. Insomma sono davvero vicinissimo ad avere una cosa da spedire.

@ludo: mi sa che il client non e' ancora pronto! Ma il server e' a buon punto ed e' documentato. Il protocollo e' banale, facilmente parsabile programmaticamente ma anche usabile via telnet, sara' banale implementare i client.

@Doxaliber: con piacere! in qualche giorno spedisco questa alpha a te, ludo e Davide. Grazie dell'interesse.
ludo Scrive:
18 Feb 09, 07:33:25
Oh, l'affare si complica. :)

Poi sarà magari utile mettere giù qualche guideline per i "meccanici dell'informatica" come me per spiegare vantaggi e svantaggi di usare DB multipli, ecc. Aspetto con ansia l'alpha, anche perchè è un po' di tempo che cerco un "poor man's queue manager" senza trovare niente di sufficientemente stabile/semplice.
riffraff Scrive:
19 Feb 09, 21:52:28
fico, un paragone con tokyo cabinet/tyrant?
antirez Scrive:
19 Feb 09, 22:31:04
@riffraff: ci sono molte differenze, ti illustro solo quelle davvero importanti a mio avviso:

- tokyo cabinet e' una hash table su disco. Redis e' una hash table in memoria, che salva sul disco ogni tanto (configurabile dall'utente) in background. Per cui hai le prestazioni che ti puoi aspettare da una cosa che funziona solo in memoria come memcached, ma in realta' anche la persistenza. Ovviamente nell'informatica tutto ha un costo, il costo e' che se ti si spegne la macchina puoi perdere magari gli ultimi minuti di query invece che l'ultima.

- Il layer di networking fa parte integrante di Redis, non c'e' la separazione di Tokyo cabinet/tyrant dunque Redis e' pensato in maniera specifica per uno uso da server, non e' supportata la possibilita' di usarlo come libreria.

- Redis non implementa una hash table chiave/valore, il valore puo' essere una lista o un set. Questa parte ancora e' in fase di implementazione dunque non so di preciso cosa sara' supportato ma certamente c'e' tutto quello che ti puoi aspettare da una lista linkata oltre a popl popr atomici. Anche le operazioni sui set saranno supportate, ad esempio se in un set hai messo tutti gli ID di pagine dove c'e' la parola 'ciao' e in un set quelle di 'mondo' puoi farti ritornare l'intersezione tra le due per avere solo le pagine dove c'e' sia 'ciao' che 'mondo'.

Penso che queste siano le differenze principali, bisogna vedere dove mi porta lo sviluppo ma non voglio complicare le cose oltre un certo livello.

Una cosa che supporto DI CERTO e ho gia' progettato abbastanza dettagliatamente e' la replication. Funziona piu' o meno cosi':

./redis-server --replicate 192.168.1.2 6379

il server che parte in questo modo si connette al master indicato con IP/porta come un normale client
ma gli spara il comando REPLICATE. Il master tiene
ferme tutte le altre connessioni, gli passa tutto il DB
che ha in memoria in quel momento, appena hanno finito ripartono assieme e lasciano il canale aperto e tutte le nuove modifiche che arrivano al master vengono comunicate allo slave tramite quel canale.

Non e' ancora chiaro cosa deve fare lo slave se cade la connessione. Di certo deve risincronizzarsi ma dovrebbe continuare a rispondere? Ci sto pensando un po' su... consigli apprezzatissimi.
antirez Scrive:
19 Feb 09, 22:37:02
ah... cosi' per dovere di cronaca. Ieri ho perso una giornata appresso a redis perche' su Linux (testo sempre sia su Linux che Mac os X) accadeva una strana cosa. C'era un ritardo di alcuni millisecondi in ogni GET facendone una serie molto velocemente... il che lo rendeva lentissimo.

Di norma fa tipo 15000 GET al secondo sul macbook, invece andava una merda. Al che ho detto, sara' certamente il nagle algorithm, con una botta di
TCP_NODELAY me ne esco. Ho chiamato subito la lib che
uso per queste cose di networking che mi sono scritto
una volta per tutte N anni fa, ma niente da fare.

E dire che il problema sembrava quello... dopo N ore di debugging (accavallato da N ore di fare altre cose di lavoro vero) vado a vedere la lib di networking
e guarda caso la funzione anetTcpNoDelay() faceva
tutt'altro ;) settava il buffer di uscita a 8k, frutto
di un residuato bellico di un programma a cui lavoravo
anni fa (tcpcam).

Ogni baco ha una sua storia affascinante e frustrante allo stesso tempo!
j Scrive:
20 Feb 09, 14:43:44
sei un grande :)
Luca M Scrive:
21 Feb 09, 10:45:44
molto interessante, per un progetto di medie dimensioni lo scorso anno ho usato memcached per gestire delle code (con client in ruby), ma in quel caso la (non)persistenza non era un problema. Comunque una cosa come Redis sarebbe stata perfetta ;)

Mi piacerebbe provarlo (magari posso testare o aiutare per il client ruby)
accoral Scrive:
04 Mar 09, 16:22:58
Mi sembra molto interessante, mi guardo la parte client python, provo a vedere se risco a fare un connettore per FLEX
Comments closed