Bara för att jag kommenterar så sent skall du få ett exempel ur Verkligheten(TM). Namn har utelämnats för att minska spårbarheten tillbaka till mig.
För sisådär tio år sedan jobbade jag som datalagrings-ansvarig på en större ISP. Bland de saker som lagrades på mina filservrar var alla våra kunders websidor och all deras mail. Det där var saker som kunderna blev sura om de försvann, så vi hade ett backupsystem. Det var ett stort, dyrt backupsystem från ett av de största företagen i backup- och datalagrings-branschen, med tillhörande bandrobotar och saker. En av komponenterna i backupsystemet var ett index, en databas över vilken fil som backats upp när och på vilket band i vilken robot dess backup fanns. När man skulle återställa en fil från backup så slog man först upp den i indexet och valde en viss backup av den att återställa, varpå systemet sade åt rätt robot att sätta i rätt band och allt sådant. Om man sade åt den att läsa tillbaka flera filer optimerade den bandladdning och sådant så att den bara behövde använda varje band en gång och så. Det var rätt smutt, på det hela taget.
Med ett litet problem.
Systemet fungerade jättebra när företaget demonstrerade sin produkt. Det gick jättfort att både ta backuper och läsa tillbaka dem på alla upptänkliga vis. Men när vi sedan började använda systemet på riktigt var det inte så smidigt längre. Visst, det tog backuper jättebra. Men att läsa tillbaka en fil tog rätt lång tid. Det tog flera minuter bara att välja filen ur indexet. Vilket var irriterande, men gick att leva med. Det hände inte ens varje vecka att någon kund ville ha något återläst.
Men så en dag fick vi ett större haveri. Varför är irrelevant, men det ledde till att vi behövde återställa ett helt filsystem från backup. Så vi sade åt systemet att göra det. Och det började tugga. Och tugga. Och tugga. Efter att det gått några timmar och den fortfarande inte ens börjat säga åt robotarna att sätta band i bandstationerna börjde vi gräva i vad den höll på med. Vilket blev något av en chock. Efter att ha sett vad den sysslade med gjorde vi en snabb överslagsberäkning på hur lång tid det skulle ta innan den faktiskt började läsa saker från band, och kom fram till bortåt tvåtusen år.
Av någon anledning blev vår VD inte så nöjd över beskedet att backupåterläsningen borde klar någonstans runt år 4003, troligen på hösten. Det blev några _rätt_ sura telefonsamtal till leverantören av backupsystemet, som hjälpte oss gå runt problemet så återläsningen blev klar på bara ett par dagar.
Så vad var det som hände där? Jo, den där indexdatabasen bestod av en enkel textfil med rader av en bestämd längd. När en fil backades upp lade systemet bara till en rad i slutet av filen. Enkelt och snabbt. När det skulle lista alla gånger en fil backats upp inför en återläsning, så läste det hela filen från början till slut för att hitta alla rader som handlade om en viss fil. Också enkelt. Snabbt? Njae... Och när vi sedan bad den återställa ett helt filsystem, ja, då började den ta varenda fil på det filsystemet och slå upp den i indexet. Enkelt? Jovars. Snabbt? Fetnej med extra superlim.
Komplexitetsmässigt blir situationen rätt illustrativ. För att ta en backup behövde systemet bara skriva en rad till en fil, en operation med en komplexitet på O(1) (för programmet, operativsystemet lär ha tagit mer tid på sig, men det bortser vi från här). Att hämta data för återläsning av en fil krävde en läsning av hela index-filen, så där blev komplexiteten proportionell mot antalet indexerade filer, alltså O(n). Och för en filsystemsåterläsning gjorde den en sådan läsoperation för varje fil: O(n^2).
Det där fungerade ju fint i en demonstration med som mest ett par dussin filer. Men vi hade ett system som lagrade alla våra användares mail i var sin fil. Våra filsystem hade sisådär hundra miljoner filer på sig, så när O(n) var irriterande långsamt blev O(n^2) fullständigt hopplöst.
I nästa version av backupsystemet som kom ändrade de indexfilen till ett binärt format där det gick att slå upp all information om en fil med en komplexitet på O(log n), och med en särskild funktion för att återläsa hela filsystem som kringgick indexet helt. Vi uppgraderade till den versionen väldigt fort (och med en mycket rejäl rabatt).
Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 24 november 2010