Persistente Datenstrukturen für Python?

[sma]

Sagen wir, ich will einen Key-Value-Store bauen, der im Prinzip auf einem `dict` basiert und regelmäßig diesen in eine Datei schreibt.

Mein erster Versuch (abgeguckt von Redis) war, per `os.fork` ein Kind abzuspalten, das das `dict` auf Platte "pickelt". Leider klont `os.fork` auch alle offenen Datei-Handles, insbesondere das Socket meines HTTP-Servers und leider fängt das benutzte Web-Rahmenwerk (bottle) auch `SystemExit`, sodass sich mein abgespaltenes Kind nicht beenden kann, sondern versucht, einen Fehler HTTP 500 in das Socket zu schreiben.

Fork ist praktisch, da es atomar ist und Unix eine copy-on-write-Semantik für den Speicher hat. Ich konserviere somit den Stand des `dict` genau zu dem Zeitpunkt, zu dem ich `os.fork` aufrufe und es gibt keinen inkonsistenten Zustand. Außerdem ist es speichereffizient und passt prima zu Python mit seinem GIL.

Leider kann ich bei einer WSGI-Architektur nicht explizit den geklonten Datei-Handle schließen, wenn ich das richtig sehe. Ich wollte aber gerne einfach HTTP als Kommunikationsprotokoll benutzen.

Welche Alternativen habe ich?

Ich könnte einen Thread abspalten und zum Sichern des `dict` benutzen. (Jedenfalls, wenn ich weiß, dass ich in keiner CGI-artigen Run-Once-Umgebung laufe.)

Nun kann es aber zu Änderungen am `dict` kommen während ich es speichern will.

Ich bräuchte eine "persistente" Datenstruktur, wie sie Clojure hat. Persistent meint hier nicht wie bei vielen objektreationalen Mappern, das man sie irgendwie in eine DB geschrieben hat, sondern, dass sie nach dem Anlegen unveränderbar ist. Ein persistentes `dict` ändert sich nie. Operationen um dort neue Schlüssel und Werte einzutragen erzeugen neue Datenstrukturen, die sich in der Regel so viel Speicher wie möglich mit der alten Struktur teilen.

Gibt es so etwas für Python? Die Clojure-Implementierung ist nämlich alles andere als trivial. Ich glaube, sie basiert für "PersistentMap" auf einem Red-Black-Tree.

Hier ist eine Arme-Leute-Implementierung:

Code: Alles auswählen

class PersistentDict(object):
	def __init__(self, dct):
		self.dct = dct
	
	def get(self, key, default=None):
		return dct.get(key, default)
	
	def put(self, key, val):
		old = self.get(key)
		if old is val:
			return self
		return PersistentDict(dict(self.dct, **{key: val}))

Leider hat diese Struktur den Nachteil, dass ich das `dict` komplett kopieren muss. Will ich 1.000.000 Datensätze speichern und jeder braucht sagen wir 32 Bytes, sind mal eben 32 MB weg.

Speziell für meinen Key-Value-Store könnte ich das optimieren, indem ich, solange ich das `dict` auf Platte schreibe, ein Flag setze, das dafür sorgt, dass ich bei Änderungen einmalig ein neues `dict` klone:

Code: Alles auswählen

def put(key, val):
    with dict_lock.acquire():
        if need_to_clone:
            store = dict(store)
            need_to_clone = False
    store[key] = val

def background_save():
    with dict_lock.acquire():
        store_ref = store
        need_to_clone = True
    try:
        with open("...") as f:
            pickle.dump(store_ref, f)
    finally:
        with dict_lock.acquire():
            need_to_clone = False

Oder ich gebe meine Idee, HTTP zu benutzen auf. Wenn ich z.B. asynchat als Basis für den Server benutzen würde, kann ich wohl das Socket manuell schließen.

Oder ich benutzen bsddb oder sqlite statt alles im Hauptspeicher zu halten. Aber wo ist denn dann noch der Spaß bei der Sache? Außerdem finde ich das einfache `dict`-Programmiermodell durchaus attraktiv.

Wir würdet ihr es machen?

Stefan

[Dauerbaustelle]

Leider hat diese Struktur den Nachteil, dass ich das `dict` komplett kopieren muss. Will ich 1.000.000 Datensätze speichern und jeder braucht sagen wir 32 Bytes, sind mal eben 32 MB weg.

Naja, du könntest ja eine Art Parent-Children-Hirarchie aufbauen und Kinder erstmal in ihren Eltern nach den entsprechendes Keys suchen lassen.

Zum Beispiel so:

Code: Alles auswählen

class PersistentDict(object):
    def __init__(self, dct=None, superdict=None, **new_values):
        self.dct = dict(dct if dct is not None else {}, **new_values)
        self.superdict = superdict

    def has(self, key):
        return key in self.dct

    def get(self, key, default=None):
        if self.has(key):
            return self.dct[key]

        superdict = self.superdict
        while superdict is not None:
            if superdict.has(key):
                return superdict.get(key)
            superdict = superdict.superdict
        return default

    def put(self, key, val):
        old = self.get(key, default=None)
        if old is val:
            return self
        return PersistentDict(superdict=self, **{key : val})

Code: Alles auswählen

>>> a = PersistentDict({'a' : 42})
>>> a.dct, a.get('a')
({'a': 42}, 42)
>>> b = a.put('b', 21)
>>> b.dct, b.get('b'), b.get('a')
({'b': 21}, 21, 42)
>>> c = b.put('c', 11)
>>> c.dct, c.get('c'), c.get('b'), c.get('a')
({'c': 11}, 11, 21, 42)
>>> c.get('invalid', default=0)
0

[tordmor]

A “shelf” is a persistent, dictionary-like object.

[cofi]

Nein, tordmor. sma meint ein anderes "persistent":

Ich bräuchte eine "persistente" Datenstruktur, wie sie Clojure hat. Persistent meint hier nicht wie bei vielen objektreationalen Mappern, das man sie irgendwie in eine DB geschrieben hat, sondern, dass sie nach dem Anlegen unveränderbar ist. Ein persistentes `dict` ändert sich nie.

Ein Shelve ist nunmal veraenderbar.

[sma]

Dauerbaustelle, deine Lösung hat nicht mehr die für Hash Tables interessante Eigenschaft, dass Zugriffe in O(1) ablaufen. Ich meine persistente Datenstrukturen basierend auf Bäumen laufen zumindest in O(log n), bei deiner Lösung kann es aber zu O(n) kommen. B-Trees oder die schon erwähnten Red-Black-Trees sind spezielle Datenstrukturen, die nicht entarten. Leider sind sie nicht-trivial zu implementieren (über 1000 Zeilen im Falle von Clojure).

Was persistente Datenstrukturen angeht, hier ist z.B. ein Stack:

Code: Alles auswählen

class PersistentStack:
    def __init__(self, root=None):
        self.root = root
    
    def empty(self):
        return self.root is None
    
    def push(self, val):
        return PersistentStack((val, self.root))
    
    def pop(self):
        return self.root[0], PersistentStack(self.root[1])

Stefan