[Python] Python, redis e bottleneck

[enrico franchi]

2013/12/17 Pietro Battiston <me a pietrobattiston.it>


> Ma in generale sono dati estremamente semplici - in alcuni
> casi ad ogni chiave è associata una breve stringa, in altri una lista di
> brevi stringhe, in altri un piccolo dizionario i cui valori sono brevi
> stringhe (insomma, tutti tipi perfettamente supportati da Redis). Ad
> esempio un set di dati che utilizzo è la descrizione di una rete. Quindi
> la struttura base è un semplice dizionario
>
> { "elemento1" : ["elemento53", "elemento114", "elemento54"],
>   "elemento2" : ["elemento1", "elemento32"],
> ... }
>
> Io ho bisogno di rispondere in modo più veloce possibile alla domanda "a
> chi è collegato elementox?".


Ho chiacchierato ampiamente di queste cose ad Europython. Comunque
preparati a soffrire veramente tanto se i dati sono tanti, tu non ti mangi
teoria dei grafi a colazione *e* hai un'ottima comprensione di tutto lo
stack software che usi.

Cioe', gia' la rappresentazione che scegli la sopra, intendiamoci, o Python
riesce ad internare tutte quelle stringhe (e se hai facile facile 1 milione
di nodi sarebbero cazzi comunque)… vuoi scoprire se due nodi sono lo stesso
nodo? Un confronto che potrebbe essere fatto in un'operazione, deve invece
confrontare stringhe con prefisso comune.

Se poi invece di vuoler scoprire a chi e' collegato 1, vuoi scoprire se 1 e
42 sono collegati… buona fortuna! Paga O(n) per qualcosa che potrebbe
essere O(1). Vedi la classica rappresentazione dei grafi in Python. Vedi
anche la mia presentazione ad EP2013 per vedere come stanno le cose in
memoria e il dolore che ti porti appresso a quando cominci a nestare
liberalmente strutture dati.

Il che si risolve in:
1) passi a teoria algebrica dei grafi e ti smanacci matrici sparse (facile
-- se sei forte in algebra -- efficiente, veloce, ma non scala
indefinitivamente -- a meno che tu non abbia sistemi per fare calcolo
distribuito su anelli arbitrari di matrici, cosa che noi iniziammo a
costruire e non finimmo realmente, e che non mi risulta esista altrove)

2) cerchi di cominciare in termini di map-reduce e hai qualcuno che ti
sostiene tale infrastruttura (non vuoi davvero mettere su e tenere in piedi
dei cluster)

3) ti rendi conto che map-reduce per problemi sui grafi non funziona sempre
troppo bene, e guardi a qualche implementazione di Pregel… buona fortuna qui

4) provi a vedere se qualche nosql graph db funziona per le tue cose, se no
provi a simularlo con qualcosa di diverso -- anche relazionale, altro che
denormalizzato! -- Poi e' noto che query SQL per esprimere cose sui grafi
sono un dolore veramente grosso, ma non e' che denormalizzando il dolore
passa, aumenta, semmai.


> Veniamo al problema 2: dopo che ho fatto tutte le analisi che devo fare
> sul dizionario tipo quello descritto sopra, devo spostare la mia
> attenzione ad un altro dizionario. Diciamo che la dimensione di ognuno
> di questi dizionari è dell'ordine di grandezza di 1-2 GB, e di RAM
> disponibile, inclusa quella che uso per il sistema, ne ho 5 GB. Quindi:
> faccio il flush del database Redis, carico la descrizione del nuovo
> dizionario.
>

Ma allora e' roba piccola piccola! Non ci sono problemi.
Se poi lo passi invece che in strutture orribilmente ridondanti a qualcosa
di compatto tipo una matrice sparsa, vedi che la RAM ti droppa
drasticamente. Scegli le strutture dati opportune, prima di metterti in
mezzo con strumenti relativamente complicati.

-- 
.
..: -enrico-
-------------- parte successiva --------------
Un allegato HTML è stato rimosso...
URL: <http://lists.python.it/pipermail/python/attachments/20131218/cb765123/attachment-0001.html>