Die unbekannte Geschichte von SQLite

xguru · 2021-07-05T10:21:01+09:00

Zusammenfassung eines Interview-Podcasts mit dem SQLite-Entwickler Richard Hipp (38 Minuten, mit Transkript) Hauptberuflich Softwareentwickler für Systeme auf Zerstörern der US Navy → Das an Bord verwendete Informix verursachte häufig Fehler, Server stürzten ab und Verbindungen brachen regelmäßig ab → Da es sich um ein Kriegsschiff handelte, musste das System auch dann robust weiterlaufen, wenn es im Gefecht beschädigt wurde – ohne Pop-up wie „Keine Verbindung zur DB möglich“ Transaktionen waren auch nicht nötig; die Daten mussten unter allen Umständen in den RAM eingelesen werden → Er suchte nach einer SQL-DB-Engine, die ohne Server läuft, fand aber keine und beschloss deshalb, selbst eine zu bauen SQLite V1 (2000) Schrieb eine Bytecode-Engine, die SQL-Anweisungen wie Programme behandelt, Queries kompiliert und ausführt Wurde im eigentlichen Projekt nie eingesetzt (der Kunde wollte Informix verwenden) Für Entwicklungszwecke genutzt und ins Internet gestellt, woraufhin Leute anfingen, sie zu verwenden Er sah Rückmeldungen wie „Ich habe eine SQL-DB auf einem Palm Pilot ausgeführt“, was Aufmerksamkeit erzeugte und ihn motivierte, weiter daran zu arbeiten Motorola Zwischen 2001 und 2002 rief Motorola an und sagte, man wolle SQLite in das neue Telefon-OS integrieren Wenn er die benötigten Funktionen unterstütze, würde man dafür bezahlen Damals wurde ihm zum ersten Mal klar, dass man mit Open Source Geld verdienen kann Rund $80.000 waren nach heutigen Maßstäben nicht viel, für ihn aber ein erstaunlicher Betrag Zusammen mit drei Kollegen arbeitete er an dem Projekt; das war der Anfang America Online Phones Danach meldete sich AOL Das war noch die Zeit, in der CDs per Post verschickt wurden, und auf diesen CDs wurde eine Datenbank benötigt Man wollte also SQLite auf die CD packen und brauchte dafür neue Funktionen Symbian OS und Nokia Zu Thanksgiving flog er für ein Meeting nach London (in Großbritannien gibt es schließlich kein Thanksgiving) Gesucht wurde eine DB für Symbian OS, im Wettbewerb mit anderen Datenbanken (2 Open-Source-, 7 kommerzielle) Die anderen 9 DBs bekamen Gelegenheit zum Tuning, aber SQLite gewann am Ende Bus Factor [1] und das Konsortium Der Bus Factor ist ein Maß dafür, wie viele Leute „vom Bus überfahren“ werden müssten, damit die Entwicklung stoppt Er arbeitete zwar bereits Vollzeit mit mehreren Leuten zusammen, aber bei Symbian hieß es, der Bus Factor müsse erhöht werden Also kam die Idee eines SQLite-Konsortiums auf, das das Projekt finanziert und mehr Menschen langfristig beteiligt Zunächst entstand die verrückte Idee, allen Konsortiumsmitgliedern Stimmrechte zu geben Mitchell Baker von der Mozilla Foundation hörte davon irgendwo und rief an → „Richard, du machst das völlig falsch. Ich erkläre dir, wie man ein Konsortium aufbaut.“ → Sie begann, die Regeln festzulegen → „Die Entwickler müssen die Kontrolle behalten. Ihre Entscheidungen sind endgültig. Man darf nicht allein durch den Beitritt ein Stimmrecht bekommen.“ → „Die Unternehmen, die das nutzen, erhalten die Ehre, Geld beizutragen, aber die endgültige Entscheidung musst du treffen.“ → Sie war sehr bestimmt und brachte alles in Ordnung. Sie ist Juristin Als Richard fragte: „Wie bringt man Leute dazu mitzumachen? Was ist der Anreiz?“, sagte sie: → „Machen Sie sich keine Sorgen. Sie werden mitmachen. Und wenn Sie es so machen, wird Mozilla Gründungsmitglied.“ Mit Unterstützung von Mozilla, Symbian und Adobe startete das Konsortium mit diesen drei Unternehmen → Als Symbian anfangs sagte, ein Konsortium sei nötig, wusste er nicht, wie er das angehen sollte. Wie Mitchell Baker davon hörte und anrief, weiß er bis heute nicht – aber es war eine erstaunliche Reise Enter Android: der Beginn von Android Weil praktisch alle Smartphones SQLite nutzten, konnte Richard die frühe Smartphone-Entwicklung aus allen Blickwinkeln beobachten 2005 gab es ein Meeting mit Android – noch bevor Android oder das iPhone veröffentlicht waren SQLite wurde auf einem Blackberry-ähnlichen Gerät mit kleinem Display oben und voller QWERTY-Tastatur debuggt Mit GDB auf einem Telefon zu debuggen, das an ein echtes Mobilfunknetz angeschlossen war, war eine erstaunliche Erfahrung Damals tat niemand bei Motorola, Symbian oder Nokia so etwas, und da wusste er, dass Android riesig werden würde Guy, This Is Important: Leute, das ist wirklich wichtig Andere Anbieter hatten damals sehr lange Hardware- und Software-Update-Zyklen von rund 30 Tagen, aber Android spielte mehrmals täglich neue OS-Versionen auf Telefone im echten Netz Der unter NDA erhaltene Prototyp eines Android-Telefons hatte zwar ein Gehäuse, das wie 3D-gedruckt aussah, war aber immerhin tragbar → Die Geräte anderer Firmen waren große Breadboards und Prototypen, nicht einmal ans Netz angeschlossen und als Telefon unbrauchbar Er hätte den Leuten bei Motorola und Symbian gern gesagt: „Das ist wichtig, ihr müsst das lösen“, konnte es wegen der NDA aber nicht – und genau das machte den Unterschied Testing and Aviation Standards: Testen und Luftfahrtstandards Adam (Interviewer): „Richards DB ist heute in einem wirklich spannenden Zustand. Das Team ist talentiert und stark, aber am Ende ist es eine Software-Beratungsfirma mit 1 bis 4 Leuten, die die Datenbank unterstützt, die in allen Android-Telefonen steckt. Entwickler nehmen DBs sehr ernst und hassen Datenprobleme.“ Wir hatten allen ganz naiv erzählt, SQLite habe keine Bugs, aber Android bewies eindeutig, dass wir falschlagen Er dachte, man könne Software ohne Bugs bauen, aber wenn Software auf Millionen Geräten installiert wird, ist es erstaunlich, wie viele Bugs auftauchen können Um diese Zeit arbeitete er mit Rockwell Collins, einem Avionik-Unternehmen, das ihm das Konzept von DO-178B [2] vorstellte → DO-178B ist ein Qualitätsstandard für sicherheitskritische Luftfahrtprodukte und im Unterschied zu anderen Qualitätsstandards tatsächlich „lesbar“ → Er kostet ein paar Hundert Dollar, ist aber dünn genug, dass man ihn unbedingt lesen sollte SQLite begann tatsächlich, den Prozessen von DO-178B zu folgen; einer davon war 100 % MCDC-Testabdeckung MCDC (Modified Condition / Decision Coverage) [3] bedeutet, dass Tests jede einzelne Verzweigung mindestens einmal durchlaufen müssen Es dauerte bei 60 Stunden pro Woche ein ganzes Jahr, SQLite auf 100 % MCDC zu bringen. Es war extrem schwer. Täglich 12 Stunden, sehr ermüdend 90 bis 95 % Testabdeckung sind einfach, aber die letzten 5 % sind wirklich schwer. Nach diesem Jahr erreichte man schließlich 100 %, und danach kamen aus Android keine Bugreports mehr Ab da funktionierte es, und es machte einen riesigen Unterschied. Danach gab es 8 bis 9 Jahre lang keine Bugs Milliarden von Tests Die erste Testsuite wurde in TCL (Tool Command Language) geschrieben und war ein typischer Entwickler-Test Dieser erste TCL-Test wird bis heute gepflegt und ist öffentlich. Er deckt zwar nicht 100 % ab, testet aber alle Funktionen von SQLite sehr detailliert Die 100-%-MCDC-Abdeckung heißt TH3 und ist nicht öffentlich (proprietary) Man wollte damit Geld verdienen, indem man es an Luftfahrtunternehmen verkauft, aber es wurde kein einziges Exemplar verkauft – wirtschaftlich brachte es also nichts Es half aber enorm dabei, das Produkt wirklich robust zu halten und neue Funktionen sowie Bugfixes schnell umzusetzen Die Zahl der Tests ist schwer zu zählen, aber 100.000 Einzeltests sind parametrisiert und führen zu Milliarden ausgeführter Tests Es gibt eine Checkliste, und vor jedem Release wird mindestens drei Tage lang getestet Getestet wird absichtlich auf vielen verschiedenen Betriebssystemen → Heute sind fast alle Geräte Little Endian, früher gab es aber viele Big-Endian-Systeme. Deshalb wurde auf einem PowerPC iBook Big Endian getestet → Tests liefen auf 32-Bit-Plattformen sowie ARM und Intel, auf 64-Bit-Plattformen, Windows, Linux, Mac, OpenBSD und allen Plattformen und OSs, die verfügbar waren → Es gibt mehrere unterschiedliche Test-Suites, darunter das ursprüngliche TCL, TH3 sowie kontinuierlich laufende Fuzzer (Fuzz Testing) Es gibt auch SQL-Logic-Tests → Eine riesige Sammlung von SQL-Anweisungen, die Shane Harrelson vor 10 Jahren erstellt hat → Diese wurden gegen jede DB getestet, die man in die Finger bekam, und alle DB-Engines scheiterten daran oder erzeugten Segmentation Faults – einschließlich SQLite. Mit einer Ausnahme: Postgres → Nur Postgres lieferte immer ein Ergebnis, und man konnte keinen Fehler finden. Die Postgres-Entwickler meinten zwar, man habe sich nicht genug angestrengt, aber wir waren trotzdem tief beeindruckt → Selbst die kommerzielle Version von Oracle crashte, und auch DB2 stürzte ab → Der wichtige Punkt war, SQLite dazu zu bringen, bei all diesen Queries dieselben Antworten zu liefern Building From First Principles Als er anfing, suchte er nach Referenzen dafür, wie man eine SQL-DB-Engine baut, fand aber nichts. Also musste er es selbst herausfinden; es war eine völlig eigenständige Aufgabe Es gab zwar viel Theorie an MIT, Harvard und Berkeley, aber wenn man nicht an diesen Hochschulen war, wusste man nicht einmal, dass diese Theorie existierte – geschweige denn, wie man sie finden sollte Das Volcano-Modell von Postgres und das Bytecode-Modell von SQLite konvergieren bei genauerem Hinsehen beide zu denselben Ideen Von oben betrachtet beginnen sie an sehr unterschiedlichen Punkten, aber bei der Frage, wie man es schneller macht, landen beide im selben Bereich Er sieht darin eine Art theoretische Bestätigung: zwei unabhängige Entwicklungslinien kommen zur gleichen Antwort Zum Beispiel wusste er über Covering Indexes überhaupt nichts, bis er auf einer PHP-Konferenz in Deutschland war, auf der auch David Axmark von MySQL sprach → In diesem Vortrag erklärte er, wie MySQL Covering Indexes implementiert hatte → Wenn ein Index in einer DB mehrere Spalten enthält, eine Query nur die vorderen Spalten abfragt und die Antwort in den übrigen Spalten liegt, kann die DB den Index allein nutzen, ohne die Originaltabelle nachzuschlagen – das beschleunigt die Arbeit → Auf dem Rückflug, als im Flugzeug wenig los war, klappte er seinen Laptop auf und implementierte über dem Atlantik Covering Indexes in SQLite B-Trees and The Art of Computer Programming Vieles musste er selbst bauen. Niemand hatte ihm je B-Bäume beigebracht; er hatte nur davon gehört Als er selbst einen B-Baum entwickeln wollte, fand er im Regal Don Knuths TAOCP, schlug B-Bäume nach und bekam dort die Algorithmen erklärt Komischerweise erklärt das Buch Such- und Einfügealgorithmen für B-Bäume detailliert, liefert aber keinen Löschalgorithmus. Der steht als Übungsaufgabe am Kapitelende, also musste er das Problem lösen, bevor er seinen eigenen B-Baum bauen konnte. „Danke, Don, vielen Dank.“ Menschen heute sollten TAOCP zumindest lesen oder wenigstens durchblättern Freedom to Build It Yourself: die Freiheit, es selbst zu bauen SQLite hängt von nichts anderem ab als von dem, was Richard selbst gebaut hat (abgesehen von einem C-Compiler und libc). Er baute sogar sein eigenes Versionskontrollsystem und seinen eigenen Bug-Tracker. Das gibt ihm Freiheit Freiheit (Freedom) bedeutet, selbst für sich sorgen zu können Wenn Rucksackreisende alles Nötige auf dem Rücken tragen und sich frei fühlen, dann deshalb, weil sie sich selbst versorgen können Wenn man alles selbst baut, ist man an niemanden gebunden – und genau darin liegt Freiheit Angenommen, man hätte für SQLite 2 Berkeley DB als Storage Engine gewählt → Damals war Berkeley DB Open Source, wurde später aber an Oracle verkauft und in ein proprietäres Dual-Source-Modell überführt, sodass man ohne Lizenzgebühren nicht mehr an den Quellcode der neuesten Version kam Auch der Parser Generator von SQLite ist nicht Yacc oder Bison, sondern ein selbst geschriebenes Werkzeug namens Lemon. So konnte er es anpassen, wenn neue Sprachfeatures nötig waren, ohne an diese Tools gebunden zu sein Anfang der 2000er nutzten alle Projekte CVS, also tat er das auch. Mitte der 2000er kamen dann Ideen für verteilte Versionsverwaltung auf Fossil aufbauen Er sah sich Git und Mercurial an, definierte seine Anforderungen und beschloss dann, selbst ein Versionskontrollsystem zu bauen Fossil funktioniert inzwischen gut und ist zu einem eigenen Projekt geworden Linus Torvalds baute Git zur Unterstützung der Linux-Kernel-Entwicklung; wenn man also am Linux-Kernel arbeitet, ist Git das perfekte Versionskontrollsystem Fossil ist dagegen genau das richtige Versionskontrollsystem für die Arbeit an SQLite. Weil er es selbst gebaut hat, erfüllt es seine Anforderungen exakt Indem man Dinge selbst entwickelt, kontrolliert man sein eigenes Schicksal, gewinnt mehr Freiheit und macht sich unabhängig von Dritten Selbstversorgung Wie nennt man Menschen, die die Stadt verlassen und ihr eigenes Essen anbauen, um selbstständig zu leben? Survivalist? Oder Prepper? „Wie Sie auch während unseres Austauschs bemerkt haben, verhält sich mein Gmail etwas merkwürdig. E-Mails kommen ständig zurück. Deshalb will ich meinen eigenen Mailserver aufsetzen. Selbst während wir dieses Meeting organisiert haben, habe ich dazu Notizen gemacht. Es wird wohl nicht schwieriger sein, als eine DB-Engine zu schreiben, aber ich möchte nicht von Gmail abhängig sein. Ich will nicht, dass sie mein Schicksal kontrollieren. Ich will nicht, dass sie die Aufzeichnungen all meiner Gespräche kontrollieren. Ich will selbst die Kontrolle haben, also werde ich versuchen, eine Lösung zu finden, die ich selbst steuern kann – auch wenn das schmerzhaft ist und viel Arbeit macht. Ich kann dafür eine VM in der Cloud mieten und betreiben und muss dann nicht von einem Dritten abhängig sein.“ Wenn jemand kommt und sagt, er werde dein Problem für dich lösen, dann solltest du wissen, dass er dir damit auch deine Freiheit nimmt. „Wenn du frei sein willst, musst du es selbst tun.“ Rat für andere Ich habe mit der verrückten Idee angefangen, eine DB-Engine zu bauen, die direkt auf die Festplatte liest und schreibt, ohne einen Server zu brauchen Wenn man Experten fragt, sagen sie: „Das ist unmöglich. Das wird niemals funktionieren. Das ist eine dumme Idee.“ Zum Glück kannte ich solche Experten nicht, also habe ich es einfach gemacht – und dann ist all das passiert Hört nicht zu sehr auf Experten. Macht Dinge, die Sinn ergeben. Löst euer Problem -- [1] Bus Factor: Ein Risikomaß dafür, dass ein Team in Schwierigkeiten gerät, wenn Teammitglieder „vom Bus überfahren werden“. Es beschreibt das Risiko, das entsteht, wenn Wissen und Zuständigkeiten nicht im Team geteilt sind Ein höherer Wert bedeutet, dass Wissen besser verteilt ist und die Arbeit nicht auf Einzelpersonen konzentriert wird [2] DO-178B: Software Considerations in Airborne Systems and Equipment Certification Von der FAA als Nachweisverfahren für die Zertifizierung von Luftfahrtsoftware übernommen [3] MCDC: Modified Condition / Decision Coverage Eine Methode zur Gestaltung von Testfällen, bei der bei mehreren Bedingungen jede einzelne Bedingung das Ergebnis des Gesamtausdrucks unabhängig von den anderen Bedingungen beeinflussen muss

(corecursive.com)

47 Punkte von xguru 2021-07-05 | 16 Kommentare | Auf WhatsApp teilen

Zusammenfassung eines Interview-Podcasts mit dem SQLite-Entwickler Richard Hipp (38 Minuten, mit Transkript)
Hauptberuflich Softwareentwickler für Systeme auf Zerstörern der US Navy
→ Das an Bord verwendete Informix verursachte häufig Fehler, Server stürzten ab und Verbindungen brachen regelmäßig ab
→ Da es sich um ein Kriegsschiff handelte, musste das System auch dann robust weiterlaufen, wenn es im Gefecht beschädigt wurde – ohne Pop-up wie „Keine Verbindung zur DB möglich“
Transaktionen waren auch nicht nötig; die Daten mussten unter allen Umständen in den RAM eingelesen werden
→ Er suchte nach einer SQL-DB-Engine, die ohne Server läuft, fand aber keine und beschloss deshalb, selbst eine zu bauen

SQLite V1 (2000)

Schrieb eine Bytecode-Engine, die SQL-Anweisungen wie Programme behandelt, Queries kompiliert und ausführt
Wurde im eigentlichen Projekt nie eingesetzt (der Kunde wollte Informix verwenden)
Für Entwicklungszwecke genutzt und ins Internet gestellt, woraufhin Leute anfingen, sie zu verwenden
Er sah Rückmeldungen wie „Ich habe eine SQL-DB auf einem Palm Pilot ausgeführt“, was Aufmerksamkeit erzeugte und ihn motivierte, weiter daran zu arbeiten

Motorola

Zwischen 2001 und 2002 rief Motorola an und sagte, man wolle SQLite in das neue Telefon-OS integrieren
Wenn er die benötigten Funktionen unterstütze, würde man dafür bezahlen
Damals wurde ihm zum ersten Mal klar, dass man mit Open Source Geld verdienen kann
Rund $80.000 waren nach heutigen Maßstäben nicht viel, für ihn aber ein erstaunlicher Betrag
Zusammen mit drei Kollegen arbeitete er an dem Projekt; das war der Anfang

America Online Phones

Danach meldete sich AOL
Das war noch die Zeit, in der CDs per Post verschickt wurden, und auf diesen CDs wurde eine Datenbank benötigt
Man wollte also SQLite auf die CD packen und brauchte dafür neue Funktionen

Symbian OS und Nokia

Zu Thanksgiving flog er für ein Meeting nach London (in Großbritannien gibt es schließlich kein Thanksgiving)
Gesucht wurde eine DB für Symbian OS, im Wettbewerb mit anderen Datenbanken (2 Open-Source-, 7 kommerzielle)
Die anderen 9 DBs bekamen Gelegenheit zum Tuning, aber SQLite gewann am Ende

Bus Factor [1] und das Konsortium

Der Bus Factor ist ein Maß dafür, wie viele Leute „vom Bus überfahren“ werden müssten, damit die Entwicklung stoppt
Er arbeitete zwar bereits Vollzeit mit mehreren Leuten zusammen, aber bei Symbian hieß es, der Bus Factor müsse erhöht werden
Also kam die Idee eines SQLite-Konsortiums auf, das das Projekt finanziert und mehr Menschen langfristig beteiligt
Zunächst entstand die verrückte Idee, allen Konsortiumsmitgliedern Stimmrechte zu geben
Mitchell Baker von der Mozilla Foundation hörte davon irgendwo und rief an
→ „Richard, du machst das völlig falsch. Ich erkläre dir, wie man ein Konsortium aufbaut.“
→ Sie begann, die Regeln festzulegen
→ „Die Entwickler müssen die Kontrolle behalten. Ihre Entscheidungen sind endgültig. Man darf nicht allein durch den Beitritt ein Stimmrecht bekommen.“
→ „Die Unternehmen, die das nutzen, erhalten die Ehre, Geld beizutragen, aber die endgültige Entscheidung musst du treffen.“
→ Sie war sehr bestimmt und brachte alles in Ordnung. Sie ist Juristin
Als Richard fragte: „Wie bringt man Leute dazu mitzumachen? Was ist der Anreiz?“, sagte sie:
→ „Machen Sie sich keine Sorgen. Sie werden mitmachen. Und wenn Sie es so machen, wird Mozilla Gründungsmitglied.“
Mit Unterstützung von Mozilla, Symbian und Adobe startete das Konsortium mit diesen drei Unternehmen
→ Als Symbian anfangs sagte, ein Konsortium sei nötig, wusste er nicht, wie er das angehen sollte. Wie Mitchell Baker davon hörte und anrief, weiß er bis heute nicht – aber es war eine erstaunliche Reise

Enter Android: der Beginn von Android

Weil praktisch alle Smartphones SQLite nutzten, konnte Richard die frühe Smartphone-Entwicklung aus allen Blickwinkeln beobachten
2005 gab es ein Meeting mit Android – noch bevor Android oder das iPhone veröffentlicht waren
SQLite wurde auf einem Blackberry-ähnlichen Gerät mit kleinem Display oben und voller QWERTY-Tastatur debuggt
Mit GDB auf einem Telefon zu debuggen, das an ein echtes Mobilfunknetz angeschlossen war, war eine erstaunliche Erfahrung
Damals tat niemand bei Motorola, Symbian oder Nokia so etwas, und da wusste er, dass Android riesig werden würde

Guy, This Is Important: Leute, das ist wirklich wichtig

Andere Anbieter hatten damals sehr lange Hardware- und Software-Update-Zyklen von rund 30 Tagen, aber Android spielte mehrmals täglich neue OS-Versionen auf Telefone im echten Netz
Der unter NDA erhaltene Prototyp eines Android-Telefons hatte zwar ein Gehäuse, das wie 3D-gedruckt aussah, war aber immerhin tragbar
→ Die Geräte anderer Firmen waren große Breadboards und Prototypen, nicht einmal ans Netz angeschlossen und als Telefon unbrauchbar
Er hätte den Leuten bei Motorola und Symbian gern gesagt: „Das ist wichtig, ihr müsst das lösen“, konnte es wegen der NDA aber nicht – und genau das machte den Unterschied

Testing and Aviation Standards: Testen und Luftfahrtstandards

Adam (Interviewer): „Richards DB ist heute in einem wirklich spannenden Zustand. Das Team ist talentiert und stark, aber am Ende ist es eine Software-Beratungsfirma mit 1 bis 4 Leuten, die die Datenbank unterstützt, die in allen Android-Telefonen steckt. Entwickler nehmen DBs sehr ernst und hassen Datenprobleme.“
Wir hatten allen ganz naiv erzählt, SQLite habe keine Bugs, aber Android bewies eindeutig, dass wir falschlagen
Er dachte, man könne Software ohne Bugs bauen, aber wenn Software auf Millionen Geräten installiert wird, ist es erstaunlich, wie viele Bugs auftauchen können
Um diese Zeit arbeitete er mit Rockwell Collins, einem Avionik-Unternehmen, das ihm das Konzept von DO-178B [2] vorstellte
→ DO-178B ist ein Qualitätsstandard für sicherheitskritische Luftfahrtprodukte und im Unterschied zu anderen Qualitätsstandards tatsächlich „lesbar“
→ Er kostet ein paar Hundert Dollar, ist aber dünn genug, dass man ihn unbedingt lesen sollte
SQLite begann tatsächlich, den Prozessen von DO-178B zu folgen; einer davon war 100 % MCDC-Testabdeckung
MCDC (Modified Condition / Decision Coverage) [3] bedeutet, dass Tests jede einzelne Verzweigung mindestens einmal durchlaufen müssen
Es dauerte bei 60 Stunden pro Woche ein ganzes Jahr, SQLite auf 100 % MCDC zu bringen. Es war extrem schwer. Täglich 12 Stunden, sehr ermüdend
90 bis 95 % Testabdeckung sind einfach, aber die letzten 5 % sind wirklich schwer. Nach diesem Jahr erreichte man schließlich 100 %, und danach kamen aus Android keine Bugreports mehr
Ab da funktionierte es, und es machte einen riesigen Unterschied. Danach gab es 8 bis 9 Jahre lang keine Bugs

Milliarden von Tests

Die erste Testsuite wurde in TCL (Tool Command Language) geschrieben und war ein typischer Entwickler-Test
Dieser erste TCL-Test wird bis heute gepflegt und ist öffentlich. Er deckt zwar nicht 100 % ab, testet aber alle Funktionen von SQLite sehr detailliert
Die 100-%-MCDC-Abdeckung heißt TH3 und ist nicht öffentlich (proprietary)
Man wollte damit Geld verdienen, indem man es an Luftfahrtunternehmen verkauft, aber es wurde kein einziges Exemplar verkauft – wirtschaftlich brachte es also nichts
Es half aber enorm dabei, das Produkt wirklich robust zu halten und neue Funktionen sowie Bugfixes schnell umzusetzen
Die Zahl der Tests ist schwer zu zählen, aber 100.000 Einzeltests sind parametrisiert und führen zu Milliarden ausgeführter Tests
Es gibt eine Checkliste, und vor jedem Release wird mindestens drei Tage lang getestet
Getestet wird absichtlich auf vielen verschiedenen Betriebssystemen
→ Heute sind fast alle Geräte Little Endian, früher gab es aber viele Big-Endian-Systeme. Deshalb wurde auf einem PowerPC iBook Big Endian getestet
→ Tests liefen auf 32-Bit-Plattformen sowie ARM und Intel, auf 64-Bit-Plattformen, Windows, Linux, Mac, OpenBSD und allen Plattformen und OSs, die verfügbar waren
→ Es gibt mehrere unterschiedliche Test-Suites, darunter das ursprüngliche TCL, TH3 sowie kontinuierlich laufende Fuzzer (Fuzz Testing)
Es gibt auch SQL-Logic-Tests
→ Eine riesige Sammlung von SQL-Anweisungen, die Shane Harrelson vor 10 Jahren erstellt hat
→ Diese wurden gegen jede DB getestet, die man in die Finger bekam, und alle DB-Engines scheiterten daran oder erzeugten Segmentation Faults – einschließlich SQLite. Mit einer Ausnahme: Postgres
→ Nur Postgres lieferte immer ein Ergebnis, und man konnte keinen Fehler finden. Die Postgres-Entwickler meinten zwar, man habe sich nicht genug angestrengt, aber wir waren trotzdem tief beeindruckt
→ Selbst die kommerzielle Version von Oracle crashte, und auch DB2 stürzte ab
→ Der wichtige Punkt war, SQLite dazu zu bringen, bei all diesen Queries dieselben Antworten zu liefern

Building From First Principles

Als er anfing, suchte er nach Referenzen dafür, wie man eine SQL-DB-Engine baut, fand aber nichts. Also musste er es selbst herausfinden; es war eine völlig eigenständige Aufgabe
Es gab zwar viel Theorie an MIT, Harvard und Berkeley, aber wenn man nicht an diesen Hochschulen war, wusste man nicht einmal, dass diese Theorie existierte – geschweige denn, wie man sie finden sollte
Das Volcano-Modell von Postgres und das Bytecode-Modell von SQLite konvergieren bei genauerem Hinsehen beide zu denselben Ideen
Von oben betrachtet beginnen sie an sehr unterschiedlichen Punkten, aber bei der Frage, wie man es schneller macht, landen beide im selben Bereich
Er sieht darin eine Art theoretische Bestätigung: zwei unabhängige Entwicklungslinien kommen zur gleichen Antwort
Zum Beispiel wusste er über Covering Indexes überhaupt nichts, bis er auf einer PHP-Konferenz in Deutschland war, auf der auch David Axmark von MySQL sprach
→ In diesem Vortrag erklärte er, wie MySQL Covering Indexes implementiert hatte
→ Wenn ein Index in einer DB mehrere Spalten enthält, eine Query nur die vorderen Spalten abfragt und die Antwort in den übrigen Spalten liegt, kann die DB den Index allein nutzen, ohne die Originaltabelle nachzuschlagen – das beschleunigt die Arbeit
→ Auf dem Rückflug, als im Flugzeug wenig los war, klappte er seinen Laptop auf und implementierte über dem Atlantik Covering Indexes in SQLite

B-Trees and The Art of Computer Programming

Vieles musste er selbst bauen. Niemand hatte ihm je B-Bäume beigebracht; er hatte nur davon gehört
Als er selbst einen B-Baum entwickeln wollte, fand er im Regal Don Knuths TAOCP, schlug B-Bäume nach und bekam dort die Algorithmen erklärt
Komischerweise erklärt das Buch Such- und Einfügealgorithmen für B-Bäume detailliert, liefert aber keinen Löschalgorithmus. Der steht als Übungsaufgabe am Kapitelende, also musste er das Problem lösen, bevor er seinen eigenen B-Baum bauen konnte. „Danke, Don, vielen Dank.“
Menschen heute sollten TAOCP zumindest lesen oder wenigstens durchblättern

Freedom to Build It Yourself: die Freiheit, es selbst zu bauen

SQLite hängt von nichts anderem ab als von dem, was Richard selbst gebaut hat (abgesehen von einem C-Compiler und libc). Er baute sogar sein eigenes Versionskontrollsystem und seinen eigenen Bug-Tracker. Das gibt ihm Freiheit
Freiheit (Freedom) bedeutet, selbst für sich sorgen zu können
Wenn Rucksackreisende alles Nötige auf dem Rücken tragen und sich frei fühlen, dann deshalb, weil sie sich selbst versorgen können
Wenn man alles selbst baut, ist man an niemanden gebunden – und genau darin liegt Freiheit
Angenommen, man hätte für SQLite 2 Berkeley DB als Storage Engine gewählt
→ Damals war Berkeley DB Open Source, wurde später aber an Oracle verkauft und in ein proprietäres Dual-Source-Modell überführt, sodass man ohne Lizenzgebühren nicht mehr an den Quellcode der neuesten Version kam
Auch der Parser Generator von SQLite ist nicht Yacc oder Bison, sondern ein selbst geschriebenes Werkzeug namens Lemon. So konnte er es anpassen, wenn neue Sprachfeatures nötig waren, ohne an diese Tools gebunden zu sein
Anfang der 2000er nutzten alle Projekte CVS, also tat er das auch. Mitte der 2000er kamen dann Ideen für verteilte Versionsverwaltung auf

Fossil aufbauen

Er sah sich Git und Mercurial an, definierte seine Anforderungen und beschloss dann, selbst ein Versionskontrollsystem zu bauen
Fossil funktioniert inzwischen gut und ist zu einem eigenen Projekt geworden
Linus Torvalds baute Git zur Unterstützung der Linux-Kernel-Entwicklung; wenn man also am Linux-Kernel arbeitet, ist Git das perfekte Versionskontrollsystem
Fossil ist dagegen genau das richtige Versionskontrollsystem für die Arbeit an SQLite. Weil er es selbst gebaut hat, erfüllt es seine Anforderungen exakt
Indem man Dinge selbst entwickelt, kontrolliert man sein eigenes Schicksal, gewinnt mehr Freiheit und macht sich unabhängig von Dritten

Selbstversorgung

Wie nennt man Menschen, die die Stadt verlassen und ihr eigenes Essen anbauen, um selbstständig zu leben? Survivalist? Oder Prepper?
„Wie Sie auch während unseres Austauschs bemerkt haben, verhält sich mein Gmail etwas merkwürdig. E-Mails kommen ständig zurück. Deshalb will ich meinen eigenen Mailserver aufsetzen. Selbst während wir dieses Meeting organisiert haben, habe ich dazu Notizen gemacht. Es wird wohl nicht schwieriger sein, als eine DB-Engine zu schreiben, aber ich möchte nicht von Gmail abhängig sein. Ich will nicht, dass sie mein Schicksal kontrollieren. Ich will nicht, dass sie die Aufzeichnungen all meiner Gespräche kontrollieren. Ich will selbst die Kontrolle haben, also werde ich versuchen, eine Lösung zu finden, die ich selbst steuern kann – auch wenn das schmerzhaft ist und viel Arbeit macht. Ich kann dafür eine VM in der Cloud mieten und betreiben und muss dann nicht von einem Dritten abhängig sein.“
Wenn jemand kommt und sagt, er werde dein Problem für dich lösen, dann solltest du wissen, dass er dir damit auch deine Freiheit nimmt. „Wenn du frei sein willst, musst du es selbst tun.“

Rat für andere

Ich habe mit der verrückten Idee angefangen, eine DB-Engine zu bauen, die direkt auf die Festplatte liest und schreibt, ohne einen Server zu brauchen
Wenn man Experten fragt, sagen sie: „Das ist unmöglich. Das wird niemals funktionieren. Das ist eine dumme Idee.“
Zum Glück kannte ich solche Experten nicht, also habe ich es einfach gemacht – und dann ist all das passiert
Hört nicht zu sehr auf Experten. Macht Dinge, die Sinn ergeben. Löst euer Problem

[1] Bus Factor: Ein Risikomaß dafür, dass ein Team in Schwierigkeiten gerät, wenn Teammitglieder „vom Bus überfahren werden“.

Es beschreibt das Risiko, das entsteht, wenn Wissen und Zuständigkeiten nicht im Team geteilt sind
Ein höherer Wert bedeutet, dass Wissen besser verteilt ist und die Arbeit nicht auf Einzelpersonen konzentriert wird

[2] DO-178B: Software Considerations in Airborne Systems and Equipment Certification

Von der FAA als Nachweisverfahren für die Zertifizierung von Luftfahrtsoftware übernommen

[3] MCDC: Modified Condition / Decision Coverage

Eine Methode zur Gestaltung von Testfällen, bei der bei mehreren Bedingungen jede einzelne Bedingung das Ergebnis des Gesamtausdrucks unabhängig von den anderen Bedingungen beeinflussen muss

16 Kommentare

enowy 2025-08-07

So einen guten Artikel gab es also. Zum Glück kann ich ihn in Übersetzung lesen.

mkeasy 2021-07-08

Das ist ein Text, den man immer wieder liest. Vielen Dank.

Wenn du frei sein willst, musst du es selbst tun.

Tu etwas, das sinnvoll ist.

Löse dein eigenes Problem.

edunga1 2021-07-05

Ein wirklich sehr interessanter Artikel!

„90–95 % Testabdeckung sind einfach, aber die verbleibenden 5 % sind wirklich schwierig. Aber nachdem man das ein Jahr lang so gemacht und schließlich 100 % erreicht hatte, kamen von Android keine Bug-Reports mehr.“

Unglaublich, dass das möglich ist.

panarch 2021-07-05

Ich habe den Artikel mit Interesse gelesen. Vielen Dank!

jsryu 2021-07-05

Das war sehr angenehm zu lesen. Vielen Dank.

falconer 2021-07-05

Ich habe es gerne gelesen.

gmlwo530 2021-07-05

Ich habe es mit Vergnügen gelesen!

kwangyeol 2021-07-05

Das hat sich sehr angenehm gelesen. Vielen Dank.

baeba 2021-07-05

Ich habe es mit großem Interesse gelesen.

Ich glaube, die Zusammenfassung zu ordnen ist noch schwieriger.

shaichoi 2021-07-05

Hat sich sehr gut gelesen. Das regt zum Nachdenken an. Vielen Dank :)

fureweb 2021-07-05

Ich habe den Artikel mit Interesse gelesen. Vielen Dank!

kalihman 2021-07-05

Gut gelesen.

jongpak 2021-07-05

Ich habe es gelesen, ohne zu merken, wie die Zeit vergeht, haha

Es ist mir fast peinlich, dass ich es als einfache eingebettete DB unterschätzt habe^^;

sixmen 2021-07-05

Ich habe es einfach nur als eine simple DBMS für die lokale Entwicklung betrachtet und verwendet, aber es ist überhaupt nicht so simpel!!

nicewook 2021-07-05

Ich habe es mit großem Vergnügen gelesen.

xguru 2021-07-05

Derzeit sind weltweit mehr als 1 Billion SQLite-Instanzen im Einsatz.

alle über 4 Milliarden Smartphones (Android, iOS)
Mac/Windows
FF/Chrome/Safari-Browser
PHP/Python
Skype/iTunes/Dropbox/Turbotax
die meisten Set-Top-Boxen und Fernseher
die Multimediasysteme der meisten Autos

https://www.sqlite.org/mostdeployed.html