|

Effizientes Speichern im Local Storage

Bei Webanwendungen mit einem hohen Anteil an State-Handling-Logik im Frontend kommt es vor, dass man manchmal, zumindest temporär Informationen im Local Storage ablegen muss. In einem Projekt, an dem ich zurzeit arbeite greifen wir häufiger auf diese Form der temporären Datenhaltung zurück. Da der Local Storage einer Webanwendung aber ein knappes Gut ist und ich an einem Teil der Anwendung war, bei dem häufig und paarweise ähnliche Datensätze in JSON in den Local Storage zwischengespeichert werden mussten, bin ich auf die Suche gegangen um den raren Local Storage nicht zu sehr zu binden. In diesem Artikel erkläre ich, wie wir den Local Storage durch einsatz von LZW-Kodierung effizienter nutzen.

1. Die Problemstellung

Im eingangs beschriebenen Fall muss ich häufig bis sehr häufig auftretende Ereignisse mitschreiben und möglichst bald an den Server senden. Der Einfachheit halber abstrahiere ich hier ein bisschen und sage mal, dass so ein Datensatz beispielhaft so aussieht:

{
  eventType: 'fetchError`,
  eventTime: '20200420150701' //20.04.2020 um 15:07:01 Uhr
  eventData: 'Irgendwelche Infos zum Event - hier z.B. ein Trace oder so.'
}

Ich möchte möglichst sicherstellen, dass jedes Event irgendwann mal beim Server ankommt. Es ist aber nicht wichtig, dass es sehr schnell dort ankommt. Es sollte, im Gegenteil, nicht bei jedem neuen Ereignis eine Verbindung mit dem Server aufgebaut werden.
Aus der Problemstellung folgt, dass ein Puffer für angelaufene Ereignisdatensätze irgendwo im Client gut aufgehoben wäre, um dann in großen "Brocken" ans Backend geschickt zu werden. Da der Puffer einen Reload überleben soll (und aus weiteren anderen Gründen), haben wir uns für das Ablegen des Puffers im Local Storage entschieden. Um die Wahrscheinlichkeit zu erhöhen, dass dieser Puffer, gemeinsam mit anderen Daten den Local Storage nicht überfüllt, möchte ich den Puffer komprimieren.

2. LZW (Lempel-Ziv-Welch)

Irgendwann in meinem Studium hatte ich ein Modul, in dem ich eine Komprimierungssoftware schreiben musste. Aus diesem Modul erinnerte ich mich an die LZW-Methode zur wörterbuchbasierten Kompression. Diese ist 1983 spezifiziert worden und - ja! - sie funktioniert auch auf JSON angewendet noch sehr gut.

Im nächsten Absatz (2.1.) erkläre ich wie LZW funktioniert. Wenn du nur den Code sehen willst, dann überspring 2.1.

2.1. LZW Algorithmus am Beispiel

Ich werde den Algorithmus am Wort "abracadabra" erklären. Normalerweise benutzt man für die Codierung ASCII-Codes (zwischen 0 und 255) hier gilt der Einfachheit halber: a=1, b=2, c=3, d=4, r=5. Das ist unser initiales Wörterbuch.

Einleitende Worte: Der Algorithmus liest die Eingabe (hier ein String) von Anfang bis Ende durch, baut dabei ein implizites Wörterbuch auf und speichert so wiederkehrende Eingabe-, hier Textfragmente effizienter.

Los geht's:

  1. Schritt:
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5}
    Output: []
    Zuletzt gelesenes Wort (LW): ``
    Gelesener Buchstabe (CW): a.
    LW+CW: a ist im Wörterbuch ==> tu nichts!
  2. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5}
    Output: []
    Zuletzt gelesenes Wort (LW): a
    Gelesener Buchstabe (CW): b.
    LW+CW: ab ist nicht im Wörterbuch
    ==> Output = Output + code von LW = [1]
    ==> Wörterbuch = Wörterbuch + ab:6
  3. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6}
    Output: [1]
    Zuletzt gelesenes Wort (LW): b
    Gelesener Buchstabe (CW): r.
    LW+CW: br ist nicht im Wörterbuch
    ==> Output = Output + code von LW = [1,2]
    ==> Wörterbuch = Wörterbuch + br:7
  4. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7}
    Output: [1,2]
    Zuletzt gelesenes Wort (LW): r
    Gelesener Buchstabe (CW): a.
    LW+CW: ra ist nicht im Wörterbuch
    ==> Output = Output + code von LW = [1,2,5]
    ==> Wörterbuch = Wörterbuch + ra:8
  5. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7, 'ra':8}
    Output: [1,2,5]
    Zuletzt gelesenes Wort (LW): a
    Gelesener Buchstabe (CW): c.
    LW+CW: ac ist nicht im Wörterbuch
    ==> Output = Output + code von LW = [1,2,5,1]
    ==> Wörterbuch = Wörterbuch + ac: 9
  6. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7, 'ra':8, 'ac':9}
    Output: [1,2,5,1]
    Zuletzt gelesenes Wort (LW): c
    Gelesener Buchstabe (CW): a.
    LW+CW: ca ist nicht im Wörterbuch
    ==> Output = Output + code von LW = [1,2,5,1,3]
    ==> Wörterbuch = Wörterbuch + ca: 10
  7. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7, 'ra':8, 'ac':9, 'ca':10}
    Output: [1,2,5,1,3]
    Zuletzt gelesenes Wort (LW): a
    Gelesener Buchstabe (CW): d.
    LW+CW: ad ist nicht im Wörterbuch
    ==> Output = Output + code von LW = [1,2,5,1,3,1]
    ==> Wörterbuch = Wörterbuch + ad: 11
  8. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7, 'ra':8, 'ac':9, 'ca':10, 'ad':11}
    Output: [1,2,5,1,3,1]
    Zuletzt gelesenes Wort (LW): d
    Gelesener Buchstabe (CW): a.
    LW+CW: da ist nicht im Wörterbuch
    ==> Output = Output + code von LW = [1,2,5,1,3,1,4]
    ==> Wörterbuch = Wörterbuch + da: 12
  9. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7, 'ra':8, 'ac':9, 'ca':10, 'ad':11, 'da':12}
    Output: [1,2,5,1,3,1,4]
    Zuletzt gelesenes Wort (LW): a
    Gelesener Buchstabe (CW): b.
    LW+CW: ab ist im Wörterbuch!!!! ENDLICH
    ==> Achtung: Das letzte Wort ist jetzt ab
  10. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7, 'ra':8, 'ac':9, 'ca':10, 'ad':11, 'da':12}
    Output: [1,2,5,1,3,1,4]
    Zuletzt gelesenes Wort (LW): ab
    Gelesener Buchstabe (CW): r.
    LW+CW: abr ist nicht im Wörterbuch
    ==> Output = Output + code von LW = [1,2,5,1,3,1,4,6]
    ==> Wörterbuch = Wörterbuch + abr: 13
  11. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7, 'ra':8, 'ac':9, 'ca':10, 'ad':11, 'da':12, 'abr':13}
    Output: [1,2,5,1,3,1,4,6]
    Zuletzt gelesenes Wort (LW): r
    Gelesener Buchstabe (CW): a.
    LW+CW: ra ist im Wörterbuch!!!!
    ==> Achtung: Das letzte Wort ist jetzt ra
  12. Schritt
    Wörterbuch: {'a':1, 'b':2, 'c':3, 'd':4, 'r':5, 'ab':6, 'br':7, 'ra':8, 'ac':9, 'ca':10, 'ad':11, 'da':12, 'abr':13}
    Output: [1,2,5,1,3,1,4,6]
    Zuletzt gelesenes Wort (LW): ra
    Gelesener Buchstabe (CW): EOF.
    LW+CW: EOF ist das Ende, also
    ==> Schreibe Code von LW in Output: [1,2,5,1,3,1,4,6,8]

Ende vom Lied:

  • Eingabe: [1,2,5,1,3,1,4,1,2,5,1] = abracadabra
  • Ausgabe: [1,2,5,1,3,1,4,6,8] = abracadxy

Wir haben in der Ausgabe 9 Elemente im Array und in der Eingabe 11 Elemente im Array. Das heißt, von 11 Zeichen wurden 2 eingespart. Das sind 18 % weniger Speicher, der benutzt werden muss. Aber dann wäre da ja noch das ganze Wörterbuch! Das richtig Elegante an LZW ist, dass dieses ganze Wörterbuch durch die Vorgehensweise begründet in der Ausgabezahlenreihe steckt (daher nennt man es implizit). Wir brauchen das Wörterbuch nicht zu speichern.

Ich hoffe, du hast jetzt einen Eindruck davon, wie der Algorithmus funktioniert. Ich überlasse es deinem Ideenreichtum, hier herauszufinden, wie du abracadxy decodieren könntest.

Das Wort Abracadabra, übrigens, ist ein relativ selbstunähnlich. Daher haben wir "nur" 18% eingespart. Aber stell dir mal vor, du würdest hunderte von unter 1. angegebene Ereignis-JSONs LZW-codieren. Da gibt es schon ein gehöriges Maß an Selbstähnlichkeit bzw. wiederholenden Mustern. Zum Beispiel die drei Schlüssel, die auch noch alle mit "event" beginnen. Oder die Zeitstempel, die in unserem Use-Case alle in mindestens 60% der Zeichen übereinstimmen. Bei sowas hat man dann schon bessere Quoten.

2.2. LZW-Kompressionsbenchmark

Ich habe in unserem Use-Case zur Prüfung der absehbaren Kompressionperformanz mit vielen verschiedenen Konstellationen geprüft, wie gut die Kompressionsrate für die verschiedenen Parameterbelegungen sind. Wichtige Parameter für die Performanz sind:

  • Anzahl der Ereignis-Objekte im JSON
  • Anzahl der verschiedenen Ereignistypen im JSON
  • Individualität der eventDatas.
    Ich möcht hier nicht ins Detail gehen, kann aber folgende Regeln angeben:
  1. Je mehr Daten komprimiert werden umso besser werden sie komprimiert. Bei 40 Ereignissen hatte ich eine Einsparung von im Mittel 75 %. Zu 95 % war die Kompression zwisch 70 % und 90 %.
    Die Tabelle gibt den zu erwartenden Zusammenhang zwischen der Anzahl an Ereignis-Objekten (n) und der Kompressionrate (r) wider:
    Anzahl Ereignisse im JSON Erwartungswert Kompression
    1 18
    5 53
    10 66
    40 75
    120 90
    250 95
    Die 95 % bedeutet, dass wir bei 250 Ereignissen statt etwa 560 kB nur noch etwa 28 kB in den Local Storage laden.
  2. Die Anzahl verschiedener Objekttypen oder die Reihenfolge der Schlüssel hat keine (große) Auswirkung auf die Kompressionsrate
  3. Die Individualität der EventData-Werte ist nicht von großem Belang, solange sie nicht zufallsgeneriert sind. Denn die Ereignisdaten sind bei uns stets auf Text-Templates zusammengebaute Strings aus einem Satz an Template-Möglichkeiten. Auch wenn es da 10 verschiedene von gibt, hat LZW diese Muster recht schnell "gelernt".

3. Umsetzung Kompression und Dekompression

Zuvorletzt möchte ich jetzt noch etwas zur Umsetzung schreiben und erklären, wie die oben beschriebene Methodik in Typescript aussehen kann.

lzwCompress(original: string) {
    const dictionary = {};
    const plainTextCharArray = original.split('');
    const outputDictionaryCodes: Array<number> = [];
    let currentChar: string;
    let phrase = plainTextCharArray[0];
    let code = 256;
    for (let inputIndex = 1;
         inputIndex < plainTextCharArray.length;
         inputIndex++) {
      currentChar = plainTextCharArray[inputIndex];
      if (dictionary[phrase + currentChar] != null) {
        phrase += currentChar;
      } else {
        outputDictionaryCodes.push(
          phrase.length > 1
            ? dictionary[phrase]
            : phrase.charCodeAt(0));
        dictionary[phrase + currentChar] = code;
        code++;
        phrase = currentChar;
      }
    }
    outputDictionaryCodes.push(
      phrase.length > 1
      ? dictionary[phrase]
      : phrase.charCodeAt(0));
    return outputDictionaryCodes.reduce(
      (acc, val) => {
        return acc + String.fromCharCode(val);
      }, ''
    );
}

Analog die Dekompression: Hier möchte ich darauf hinweisen (gilt aber auch für oben), dass bestimmte "merkwürdige" Arten der Entwicklung, wie einen String als Array aus Strings zu bauen, um ihn dann am Ende zusammenzuführen, nicht der Programmäshetik sondern der Performance dienen.

lzwDecompress(compressedString: string) {
    const dictionary = {};
    const inputData = compressedString.split('');
    let currentChar = inputData[0];
    let oldPhrase = currentChar;
    const clearTextCharArray: Array<string> = [currentChar];
    let code = 256;
    let phrase;
    for (let inputIndex = 1;
         inputIndex < inputData.length;
         inputIndex++) {
      const currentCode = inputData[inputIndex].charCodeAt(0);
      if (currentCode < 256) {
        phrase = inputData[inputIndex];
      } else {
        phrase = dictionary[currentCode]
          ? dictionary[currentCode]
          : (oldPhrase + currentChar);
      }
      clearTextCharArray.push(phrase);
      currentChar = phrase.charAt(0);
      dictionary[code] = oldPhrase + currentChar;
      code++;
      oldPhrase = phrase;
    }
    return clearTextCharArray.join('');
}

4. Ein paar Gedanken

Es ist wichtig, abzuwägen, ob man die Strapazen (Rechenkosten) des Komprimierens und Dekomprimierens in kauf nimmt für das Einsparen von einem Teil des Speicherplatzes.
Einige wichtige Faktoren sind:

  1. Häufige Updates - wird der Content im Local Storage häufig geändert erfordert das jedes Mal eine komplette Dekompressions-Kompressionsrunde! Das lohnt sich bei hochfrequenten Änderungen nicht.
  2. Selbstähnlichkeit des Contents - haben wir es mit sehr monotonen Daten zu tun, welche immer gleiche Muster aufweisen, dann ist es plausibel, dass die Kompressionsraten gut sind. Beispiele für solchen Content sind: JSON, Quellcode, einsprachige Texte, Binäre (Bild)daten ohne Kompression. Beispiele für nicht solchen Content sind: Rauschen, Binäre (Bild)daten die komprimiert sind.
  3. Speicherplatzproblem - nur wenn überhaupt ein Speicherengpass oder -knappheit vorliegt, ist ein solches Vorgehen angebracht.