1. Mit Hilfe eines Hashverfahrens kann auf unverschlüsselten Daten eine Prüfsumme ermittelt werden. Diese dient als Signatur, um beispielsweise die Authentizität einer Datei zu überprüfen. Aus der Signatur kann nicht auf die Datei geschlossen werden.  Die Erzeugung zweier verschiedener Dateien mit identischer Signatur (Kollision) sollte praktisch unmöglich sein. Ein Hashverfahren welches dieses leisten soll ist beispielsweise SHA-1 oder MD5.   
2. FTP-Client Befehl: Der Client soll beim Empfangen und Senden ein Nummernzeichen (#) anzeigen.                                                   

Cyclic Redundancy Check (CRC) ist eine zyklische Redundanz-Prüfung. Sie wird überwiegend bei Datenübertragungen und Datenaufzeichnung zur Fehlerüberwachung benutzt.  Bei diesem Algorithmus wird durch eine Division und deren Restebildung eine Prüfsumme errechnet, die die Richtigkeit eines vorangegangenen Bits überprüft.                                                       

Ein Datenpaket ist eine Einheit in einem ISO-OSI-Modell (Internationale Organisation für Normung, Open System Interconnection), welches sich wiederum unterteilt in Daten und einen Header.  Der Header beinhaltet eine ID-Nummer, die Quell- und die Zieladresse sowie eine Prüfsumme. Manchmal wird ein Datenpaket unterschieden von einem IP-Paket oder IP-Datagramm. Datenpakete werden allgemein in paketorientierten Netzwerken versendet.  Der Kopfbereich (Header) von IPv4-Paketen ist in RFC 791 definiert. Er ist 32 Bit lang und enthält Angaben zu:
- Version (IPv4 oder IPv6)
- IP Header Length (IHL) 
- Type of Service (ToS: Priorität, Quality of Service (QoS))
- Länge des gesamten Paketes (Total Length: 16 Bit breit → maximal 65535 Bytes oder 64 Kibibyte) 
- Fragment Offset: dient der Verwaltung fragmentierter Pakete
- Lebensdauer eines Paketes (Time-To-Live, TTL): soll die Lebensdauer begrenzen, damit ein Paket bei
→ Fehlleitungen nicht ewig im Netz umherirrt und Ressourcen bindet,  heute oftmals als Hop-Count realisiert
- Angaben zur Quell- und Zieladresse
- einer Prüfsumme
- und Zusatzinformationen, welche Vorgaben für das Routing geben:
⇒Strict Routing: ein kompletter Routing Pfad  ist vorgegeben
⇒Free Routing: gibt eine Liste von Routern an, über die das Paket gehen soll
- einen Zeitstempel u.a.
Der Aufbau eines IPv6 Headers unterscheidet sich stark vom IPv4 Header. Obwohl  er eine grössere Adressinformation trägt (Länge der Ziel- und Quelladresse ist 128 Bit (bei IPv4 32 Bit) ist er nur 40 Byte lang. Er enthält keine Angabe über die Grösse und keine Prüfsumme.  Die Fragmentierungsmöglichkeit ist als eigener Header realisiert. Der IPv6 Header enthält einen 20-Bit grossen Bereich der Flow-Label genannt wird: es handelt sich dabei um eine Zufallszahl welche zusammen mit der Absenderadresse  einen Flow (Datenstrom) angibt. Mit Hilfe des Flow Labels kann ein Router anhand einer Hash-Tabelle schneller entscheiden, was mit dem Datenpaket geschehen soll. Der Flow Label erlaubt die Zuweisung eines Datenstroms der aus mehreren verbundenen  Datenpaketen mit demselben Sender und Empfänger besteht. Datenströme können nach Quality of Service  und Priorität extra von den Routern behandelt werden. Beispielsweise ist bei einer Multimedia-Konferenz mit einer Multicast Adresse möglich, getrennte Flows für Audio, Video und Grafiken zu realisieren.  Das 8-Bit Feld Next Header gibt den Typ des nachfolgenden Headers an: es kann sich um den das darüberliegenden TCP-Protokolls oder um einen Extension Header handeln (Header für  Fragmentierung, Routing, Authentifikation, Verschlüsselung oder Hop-by-Hop bzw. End-to-End Steuerung). Diese Header bilden eine Liste, der eine verweist auf den nächsten. Die Payload Length ist ein 16 Bit Feld und gibt die Länge des Datenteils  (Nutzdaten) an. Die maximale Grösse der Nutzdaten ist 65535 Byte. Für grössere Datenpakte ist ein Jumbogram im Extension Header vorgesehen: Datenpakete bis zu einer Grösse von 2 ^ 32 Byte (4096 Mebibyte) sind erlaubt.                             

Bedarf an IP-Adressen und Koexistenz mit IPv6 
IPv4 ist das gegenwärtig am meisten genutzte Internet-Protokoll und umfasst einen Adressraum von 32-Bit. Es bildet das Rückgrat des Internet, wird jedoch bis ca. 2025 sukzessive von IPv6 abgelöst. Problematisch ist der auf 32-Bit begrenzte Adressraum,  welcher eine maximale Anzahl von 4,295 Milliarden Hosts adressieren kann. Mit dem Wirtschaftsboom in Asien und dem Bedarf an IP-Adressen für Mobile Endgeräte, für Haushaltsgeräte (Kühlschrank), Sensor-Netzwerke für Brücken, Häuser usw. oder  RFID-Chips steigt der Bedarf an IP-Adressen rapide an.  Die USA wiederum als grösste Wirtschafts- und Internetmacht verfügen aus historischen Gründen noch eine Zeit lang über genügend IP-Adressen, so dass von dieser Seite keine Forcierung zur  Umstellung auf IPv6 zu erwarten ist. IPv6 ist auch mit Kosten verbunden, da neue Router/Bridges/Switches benötigt werden. Diese Problem wird wahrscheinlich in der Übergangszeit durch den Einsatz von Routern gelöst, die beide Protokolle beherrschen  (dual stack), oder durch "Tunnelung" von IPv6 Datagrammen: sie werden einfach an einen IPv4 Header angehängt oder der Header enthält beide Versionsnummern. 

IPv4-Header
Ein IPv4 Datagramm (Datenpaket) ist aufgeteilt in einen Header und den Nutzteil (eigentliche Daten).  Der Kopfbereich (Header) von IPv4-Paketen ist in RFC 791 definiert. Er ist 32 Bit lang und enthält Angaben zur Version (IPv4 oder IPv6), zur IP Header Length (IHL), Type of Service (ToS: Priorität, Quality of Service), Länge des gesamten Paketes  (Total Length: 16 Bit breit → maximal 65535 Bytes oder 64 Kibibyte), Fragment Offset: dient der Verwaltung fragmentierter Pakete, Lebensdauer eines Paketes (Time-to-Live, TTL): soll die Lebensdauer begrenzen, damit ein Paket bei Fehlleitungen  nicht ewig im Netz umherirrt und Ressourcen bindet, heute oftmals als Hop-Count realisiert, sowie Angaben zur Quell- und Zieladresse, einer Prüfsumme und Zusatzinformationen, welche Vorgaben für das Routing geben: Strict Routing:  ein kompletter Routing Pfad ist vorgegeben, Free Routing: gibt eine Liste von Routern an, über die das Paket gehen soll, ein Zeitstempel u.a. 

Routing Protokolle unter IPv4
Routing Protokolle die unter IPv4 verwendet werden sind u.a.: Border Gateway Protocol (BGP): BGP ist ein  Exterior Gateway Protokoll um Erreichbarkeitsinformationen zwischen Autonomen Systemen (AS) auszutauschen, d. h. es liefert Informationen darüber, welche Netze erreichbar sind. Diese Informationen werden von den Routern der ASe  verwendet, um interne Routing Daten für das Open Shortest Path First (OSPF) Verfahren oder das Routing Information Protocol (RIP) zu erstellen. Ein Autonomes System ist eine Anzahl von IP-Netzen die einheitlich administriert werden und  durch ein oder mehrere Interior Gateway Protocols (IGP) verbunden sind. Ein IGP ist ein Routing-Protokoll für ASe: sie können mit komplexen Netzwerktopologien umgehen. Beispiele sind: OSPF, RIP, IS-IS (Intermediate System to  Intermediate System Protocol) oder IGRP (Interior Gateway Routing Protocol). ASe können sich aus mehreren Teilnetzen zusammensetzen und werden meistens von ISPs (Internet Service Provider), Firmen oder Organisationen betrieben.  Eine Weiterentwicklung von IGRP ist EIGRP (Enhanced Interior Gateway Routing Protocol), das 1994 von Cisco vorgestellt wurde. OSPF und IS-IS arbeiten mit dem Routing-Algorithmus Link-State-Routing-Protokoll (LS). Damit bauen Router komplexe  Datenbanken mit Informationen über Netzwerktopologien auf. Link State arbeitet mit dem Shortest Path First (SPF) Algorithmus von Edsger Dijkstra. Im Unterschied zu den Distanzvektorprotokollen (RIP, IGPR) liegen bei  LS Informationen über die gesamte Netzwerktopologie vor. LS tauscht nur Änderungen der Routingtabellen aus: dies erfolgt über Link-State-Announcement/Advertisements (LSA) per Multicast unter benachbarten Routern.                   

Redundant Array of Inexpensive (oder Independent) Disks (entwickelt in Berkeley 1987): durch Zusammenschluss mehrerer physikalischer Festplatten wird ein stabileres Logisches Laufwerk erreicht. Ergebnis: Erhöhung der Datensicherheit durch  Redundanz, Steigerung der Transferraten und der Aufbau grosser logischer Laufwerke. Zu diesem Zweck teilen sich mehrere Festplatten Daten (so dass sie gleichzeitig von mehreren Festplatten geliefert werden können → Performance)  oder sie speichern sie doppelt (Sicherheit, Redundanz). Realisiert wird dies durch Hardware- oder Software-RAID-Controller.

RAID-Level 0-2:
RAID 0:  2 oder mehr Festplatten werden zu einer logischen Platte verbunden. RAID 0 ist eigentlich kein RAID, fällt eine Platte aus, so sind alle Daten weg. Vorteil: bessere Verteilung, schneller.  RAID 1 (Mirroring/Duplexing): Parallele Speicherung aller Daten auf 2 Platten. RAID 2: Verwendung von Hamming Codes (Fehlerkorrekturcode durch den Hamming-Algorithmus: Error Correction Code (ECC))  zur Steigerung der Fehlertoleranz.

RAID-Level 3 und 4:
RAID 3: Speicherung von Prüfsummen unter Verwendung  von XOR-Operationen (Paritäten). Die Prüfsummen (Parity) werden für jede Datenreihe angelegt: ein Parity Byte (Prüfbyte) wird auf einer weiteren Festplatte, der Parity-Platte im Disk Array abgelegt.  Die Parity oder Fehlerkorrektur wird durch eine XOR Verknüpfung erstellt. Nachdem die Nutzdaten auf mindestens 2 Laufwerke verteilt wurden (Stripping) werden diese mit dem XOR-Operator verknüpft. Die XOR-Operation ist ein Bit-weiser  Vergleich der Daten: wenn in einer Reihe eine ungerade Anzahl von Einsen steht, so ist das Ergebnis eine 1, ansonsten eine 0. Beispiel: Platte 1: 1001010 Platte 2: 0011011 Parity: 1010001. Wenn eine  der beiden Platten P1 oder P2 ausfällt ist eine Rekonstruktion mit Hilfe der Parity Platte möglich. Auch die Parity Platte kann rekonstruiert werden, falls sie ausfällt. Fallen jedoch 2 Platten aus, so ist keine Rekonstruktion mehr möglich. 

RAID 4: mehrere READ/WRITE Operationen gleichzeitig möglich. Die Daten werden nicht in Bytes sondern in Blöcke aufgeteilt (8, 16, 32, 64 oder 128 KB). RAID 4 eignet sich nur bei grossen, zusammenhängenden Datenmengen, da sonst zu oft auf den  Parity Block zugegriffen werden muss.

RAID-Level 5:
RAID 5 benötigt mindestens 3 Festplatten.  Jeder Sektor wird um eine Prüfsumme erweitert und auf alle Platten verteilt. Bei Ausfall ist eine Platte rekonstruierbar. Die Parity-Daten werden also nicht auf einer separaten Parity Platte gespeichert, sondern auf alle  Festplatten mit Nutzdaten verteilt und in ein Array (Parity Block) geschrieben. Da das Parity Laufwerk entfällt, wird es auch nicht ständig kontaktiert. RAID 5 bietet sowohl bessere Performance als auch Redundanz und ist die am weitesten  verbreitete Variante. Beim Lesen sind die Parity-Informationen nicht notwendig, alle Platten stehen also parallel zur Verfügung. Die nutzbare Gesamtkapazität errechnet sich aus: Kapazität der kleinsten Platte im Array * (Anzahl der Platten -1).  Der Ausfall einer Platte wird bei RAID 5 immer abgefangen. Bei der Rekonstruktion (Rebuild) der Daten auf der Hotspare-Platte (Ersatzfestplatte die bei Ausfall automatisch eingebunden wird) bzw. nach Austausch der defekten Platte lässt die Leistung  jedoch zunächst deutlich nach, da viele zusätzliche Zugriffe notwendig werden (Rekonstruktion beim Lesen und Schreiben und zusätzliche Zugriffe des Rebuild-Vorganges).  Eine Verbesserung ist daher präemptives RAID 5: mit Hilfe von internen Fehlerkorrekturstatistiken, z. B. mit S.M.A.R.T. (Self-Monitoring, Analysis and Reporting Technology), wird versucht, die Ausfallwahrscheinlichkeit einer  Platte zu berechnen. Die Daten derjenigen Platte, die am wahrscheinlichsten ausfallen wird, werden dann vorsorglich auf der Hotspare-Platte synchronisiert.

RAID-Level 6 und 7 
RAID 6: funktioniert ähnlich wie RAID 5. Es werden mind. 4 Platten benötigt. Es kann jedoch der Ausfall von 2 Festplatten abgefangen werden. Es werden nicht ein, sondern zwei Fehlerkorrekturwerte berechnet. Diese werde über alle Platten verteilt.  Der Rechenaufwand bei den XOR-Operationen und einer eventuellen Resynchronisation ist jedoch höher als bei RAID 5. Die Paritätsbits müssen über mehrere Daten-Zeilen berechnet werden. Die Berechnungen der Resynchronisation erfolgen über Matrizen und  Untermatrizen.
RAID 7: Wie RAID 5, nur läuft im Controller ein lokales Echtzeitbetriebssystem, das Lese- und Schreiboperationen steuert. RAID 7 wird selten verwendet. 

Kombinations-RAIDs:
Kombinations-RAIDs sind Zusammenfassungen von RAID-Systemen zu einem weiteren RAID.  Beispielsweise können mehrere RAID 0 Systeme zu einem RAID 0 Array zusammengefasst werden, und mehrere RAID 0 Arrays zu einem RAID 5 Array.           

Das Fourth Extended Filesystem (ext4) ist ein Journaling Dateisystem für Linux. Es weist folgende Verbesserungen gegenüber ext3 auf: ext4 unterstützt Partitionen oder Volumes bis zu zu 1 Exbibyte.  Die Adressierung von Speichereinheiten kann über Extends erfolgen, wobei die Speichereinheiten in Blocks organisiert sind. Dadurch wird der Zugriffsaufwand vermindert.  Ext4 ist resistenter gegenüber Festplattenbeschädigungen. Ext4 unterstützt Unterverzeichnisse und Dateigrößen die die Größe des Dateisystemes haben sowie Online-Defragmentierung und Zeitstempel auf Nanosekundenbasis und den Einsatz von Prüfsummen.  Es besteht die Möglichkeit, ext3-Partitionen ohne Neuformatierung in ext4 umzuwandeln. Die Verzeichnisse sind in Form von Tabellen oder H-Bäumen abgelegt. 

ext4 und Google
Google hat im 1. Quartal 2010 den Chefentwickler von ext4, Ted Ts'o eingestellt, um u.a. sein Dateisystem von ext2 auf ext4 umzustellen. Dies ist aus Performance-Gründen notwendig.  Das Linux-Dateisystem ext4 und XFS haben  in Benchmark-Tests gut abgeschnitten, wobei auch JFS getestet wurde. Der Umstellungsaufwand bei ext4 ist jedoch am geringsten, da hier kaum Ausfallzeiten zu befürchten sind ('sanftes' Update von ext2 nach ext4 möglich).                                             

Backlinks, Hypertextanalyse, Semantische Umgebung
BackRub ist der technische Vorläufer der Suchmaschine Google. BackRub wurde von den damaligen Stanford Doktoranden Sergey Brin und Lawrance Page in Stanford am Computer Science Department entwickelt.  Die Entwickler erkannten den Wert von Suchmaschinen für das Internet und deren mögliche semantische Power. Der Name BackRub leitet sich ab aus der Analyse von Backlinks zum Bewerten von Webseiten. Im Konzept für  BackRub sind schon enthalten: Hypertextanalyse, semantische Umgebung und Keywords, der PageRank und die Formel sowie die technische Architektur von Google. Die Tatsache der Implementierung auf Linux Server mit C und C++ für die Algorithmen  ist ebenfalls im entsprechenden White Paper zu BackRub zu finden.

BackRub Technik, URL Crawler, Parser, WordID, DocID, Indexer
Nachdem Crawler und URLCrawler das Web durchsucht haben werden die Webpages nach bestimmten  Kriterien durch einen Parser geparst. Ein Wörter Lexikon mit über 14 Millionen Wörtern hilft beim Erkennen von Wörtern. Es werden WordIDs und DocIDs vergeben. Indexiert werden die Seiten durch einen Indexer und einen  Sorter.

Repository, Barrels, URL-Resolver, Anchor File
Der Indexer liest das Repository aus, entpackt die Dokumente und parst sie.  Jedes Dokument wird in Bezug gesetzt zu einer Gruppe von definierten Wortstämmen die 'Hits' genannt werden. Die Hits beinhalten das Wort, die Position im Dokument sowie eine Abkürzung für die Typo-Grösse und die Gross-Klein-Schreibweise.  Der Indexer verteilt diese Hits auf eine Anzahl von 'Barrels', wodurch ein vorsortierter Forward Index entsteht. Weitehin parst der Indexer alle Hyperlinks in einem Dokument und speichert die Informationen darüber in einem Anchor File. Das Anchor File  enthält Informationen darüber, von wo nach wo der Link genau führt, sowie den dazugehörigen Text. Der URL-Resolver liest das Anchor File aus und wandelt relative URLs in absolute URLs um. Den absoluten URLs werden DocIDs zugeordnet. 

Forward Index, Link-Datenbank, DocID
Der Anchor Text wird dem Forward Index zugeordnet, welcher mit den DocIDs und den Anchor Punkten verknüpft ist. Der URL-Resolver generiert auch eine Link-Datenbank, welche aus Paaren von DocIDs besteht.  Mit Hilfe dieser Link Datenbank wird der PageRank berechnet. Der Sorter bedient sich der Barrels, die nach DocID sortiert sind und sortiert sie nach WordID um: dadurch wird der Inverted Index erzeugt. 

Ein Programm, das DumpLexikon genannt wird, nimmt diese erzeugten Listen zusammen mit dem Lexikon, welches durch den Indexer generiert wurde, und erzeugt ein neues Lexikon, welches von dem Searcher verwendet wird. 

Der Searcher läuft auf einem Web Server und benutzt das Lexikon welches durch DumpLexikon bereitgestellt wurde zusammen mit dem Inverted Index und dem PageRank um Suchanfragen zu beantworten.  Die Datenstruktur von Google ist so konzipiert, dass eine optimale Verarbeitung von grossen Datenstrukturen und Indexen gewährleistet ist und das Web entsprechend schnell gecrawalt werden kann. Dies wird zu geringst möglichen Kosten gemacht. Trotz der  enormen Datenmengen bleibt eine Suche auf den Festplattensystemen i.d.R. unter 10 ms bis zur Antwort. Google vermeidet das Suchen auf den Festplattensystemen wo immer das möglich ist, was auch einen grossen  Einfluss auf die Systemarchitektur von Google hatte.

Google verwendet das Konzept von BigFiles. BigFiles sind virtuelle Files welche eine Mehrzahl von File Systemen umspannt und durch 64-Bit Integers adressierbar sind.  Die Allokation auf Multiple File Systemen wird automatisch durchgeführt. Das BigFile Konzept beinhaltet die Allokation und Deallokation von File Deskriptoren sowie Optionen zum Packen von Daten. 

Das Repository beinhaltet die volle HTML-Struktur der Webseiten. Jede Seite ist durch zlib komprimiert. Im Repository sind die Dokumente nacheinander gespeichert und vorgefertigt durch die DocID, URL und Länge. Das Repository  benötigt für den Zugang keine weitere Datenstruktur: die hilft beim Aufrecht erhalten der Datenkonsistenz und erleichtert die Entwicklerarbeit.

Batch Update Modus, Width File, Batch Lauf 
Der Dokumenten Index beinhaltet die Informationen über jedes Dokument. Er ist in einer MySQL ISAM Struktur festgelegt, sortiert nach DocID. Die Informationen die an jedem Eintrag festgelegt sind beinhalten den laufenden Dokumenten Status, einen Zeiger  zum Repository, eine Prüfsumme für das Dokument und einige statistische Angaben. Wenn das Dokument gecrawlt wurde, enthält es auch einen Zeiger zu einem variablen Width File, welches docinfo genannt wird. Docinfo enhält die URL und den Title.  Wenn das Dokument noch nicht gecrwalt wurde zeigt der Zeiger auf die URLList, welche ausschliesslich die URL enthält.  Die Entscheidung für die Design Struktur resultiert aus dem Bedürfnis nach einer kompakten Datenstruktur und der Möglichkeit, einen Eintrag in einer einzigen Suchaktion zu durchsuchen. Zusätzlich gibt es ein File welches URLs in DocIDs umwandelt.  Es handelt sich um eine Liste von URL Prüfsummen mit den zugehörigen DocIDs welche nach der Prüfsumme sortiert sind. Um die DocID einer bestimmten URL zu finden, wird die Prüfsumme der betreffenden URL ermittelt und eine binäre Suche  über der Prüfsumme durchgeführt um die DocID zu finden. URLs können in DocIDs in einem Batch-Lauf umgewandelt werden in dem sie mit dem File zusammengeführt werden. Mit dieser Technik wandelt der URLResolver URLs in DocIDs um. Dieser Batch Update  Modus ist sehr bedeutend für den Erfolg von Google, da man ansonsten für jeden Link eine Suche durchführen müsste, was impliziert dass man für eine Platte mit einem Link Data Set von 322 Millionen Einträgen einen Monat brauchen würde.

Das  Lexikon hat verschiedene Ausprägungen: es kommt in der BackRub Implemetierung mit einem Hauptspeicher von 256 MB aus. Es enthält in dieser Ausführung 14 Millionen Wörter und ist in 2 Teilen implemetiert: eine Wortliste die untereinander verbunden und  durch Nullen getrennt ist und eine Hash Tabelle von Zeigern.

Forward Index, Invertierter Index
Der Forward Index ist vorsortiert und in 64 Barrels gespeichert.  Jeder Barrel enthält eine Bandbreite von WordIDs.

Der Invertierte Index enthält dieselben Barrells, die jedoch durch den Sorter verarbeitet wurden. Für eine valide WordID enthält das Lexikon  einen Zeiger an die entsprechende WordID im Barrel. Er zeigt auf eine Doclist der DocID zusammen mit der entsprechenden Hit List. Die Doclist repräsentiert alle Vorkommnisse von Wörtern in allen Dokumenten.