Copy On Write ( COW )


Immer wieder werde ich gefragt, was denn nun eigentlich COW ist und wie ZFS Datenblöcke schreibt.
In diesem Zusammenhang werde ich auch oft mit anderen, sogeannten COW Verfahren konfrontiert, wie beispielsweise der Beschreibung von IBM, die diesen Begriff auch fuer ihr Verfahren zur Erstellung von Snapshots verwendet. Allerdings hat deren Verfahren mit COW herzlich wenig zu tun, und die Definition von COW wird verballhornt.

Copy-on-write, Snapshots und andere Verfahren

Copy-on-write bezeichnet zunaechst einmal ein Optimierungsverfahren/Algorithmus, bei denen Prozesse auf ein und dieselben Daten einer Speicherseite zugreifen koennen, so dass diese Daten nicht mehrfach gespeichert werden muessen. Die Adressbereiche der Prozesse verweisen dann auf die gleiche Speicherseite. Die Daten liegen im Speicher nur read-only vor.

Erst wenn diese Daten manipuliert werden sollen, wird eine Kopie, und dies auch nur teilweise erstellt, so dass die Aenderungen fuer die anderen Prozess nicht sichtbar sind. Vorteil dieses Verfahrens ist, dass solange Daten nicht modifiziert werden, keine Kopie erstellt werden muss. Deswegen heisst es, copy-on-write (COW ).

Fuer Dateisysteme heisst Copy-on-write, dass geaenderte Datenbloecke nicht ueberschrieben werden.
Sie werden stattdessen an einen freien Platz geschrieben und die Metadatenbloecke werden anschliessend angepasst und verweisen nun auf den neuen Block. Die originalen Bloecke bleiben erhalten, so dass diese nun den Snapshot bilden koennen.
Damit unterscheidet sich ZFS von herkoemmlichen Dateisystemen, die mit dem Verfahren read-modify-write arbeiten. In diesem Falle werden die Datenbloecke in einer sog. atomaren Operation eingelesen, veraendert und anschliessend überschrieben.
Sollte bei diesem Schreibvorgang die Daten korrumpiert worden sein, so gibt es kein Zurueck, da die originalen Daten ueberschrieben wurden.

COW ist keine Erfindung von Netapp oder IBM oder Sun mit ZFS, sondern diesen Algorithmus gibt es schon lange in Unix Systemen.

Literatur allgemein zu COW:
http://de.wikipedia.org/wiki/Copy-On-Write

COW wird hauptsaechlich in Virtual-Memory-Subsystemen verwendet. Das heisst, ein Prozess erstellt eine Kopie von sich selbst, und die zu aendernden Speicherseiten der Kopie oder des Prozesses selbst werden markiert als „copy-on-write“.
Veraendert ein Prozess die Daten im Speicher, sorgt das Betriebssystem vorher dafuer, dass eine Kopie der Seiten erstellt wird, die dann geaendert wird. Die Aenderungen bleiben fuer die anderen Prozesse unsichtbar.

Literatur: COW im VM subsystem, Algorithmus:

http://courses.cs.vt.edu/~cs3204/spring2009/butta/local/lectures/lecture-18.pdf
http://tkhanson.net/virtual_memory.pdf
https://www.systems.inf.ethz.ch/education/past-courses/fs10/operating-systems-and-networks/slides/chapter17-6up.pdf

COW Verfahren wird auch noch zu anderen Zwecken eingesetzt, beispielsweise in Virtualisierungssoftware oder Emulatoren wie QEMU, so dass VMs auf das gleiche VM Disk Image zu greifen koennen, was den Speicherbedarf reduziert.

ZFS nutzt das copy-on-write, transaktionale Objekt Modell.
Bloecke werden niemals ueberschrieben, sondern es wird stattdessen ein neuer Block allokiert, die Daten werden im neuen Datenblock modifiziert, dann werden die Metadatenbloecke auf den neuen Block referenziert und wenn dies erfolgreich abgeschlossen werden konnte, erst dann ist die Transaktion beendet.
Damit der Overhead reduziert wird, werden mehrere Aenderungen zu Transaktionsgruppen zusammengefasst und bei synchronen Schreibvorgaengen wird der intent log eingesetzt.

Da die originalen, veralteten Bloecke nicht ueberschrieben werden, koennen diese fuer Snapshots genutzt werden. Das ist auch der Grund, warum die Snapshots in ZFS sehr schnell erstellt werden, da die Daten ja bereits vorhanden sind, – sie sind eben im ZFS immanent enthalten.
Ausserdem verbrauchen sie keinen zusaetzlichen Speicherplatz, da nur geaenderte Daten neu gespeichert werden. Nicht modifizierte Daten werden vom Dateisystem und den Snapshots gemeinsam genutzt.

Clones, also schreibbare Snapshots, bilden ein eigenes unabhaengiges Dateisystem, das sich eine Sammlung von Bloecken mit den Snapshots teilt.
Wenn nun eine Aenderung im Clone stattfindet, dann werden neue Datenbloecke erstellt, die diese Aenderungen enthalten, aber die ungeaenderten Datenbloecke werden weiterhin miteinander geteilt, unabhaengig davon wie viele Clones bestehen moegen.

Literatur zu COW und ZFS:
http://all-unix.blogspot.com/2007/03/zfs-cow-and-relate-features.html

IBM hat Patente die auf COW aufsetzen, ebenso wie NetApp ( siehe unten die Literaturhinweise).
Das heisst, sie alle nutzen den COW Algorithmus, verwenden aber eigene Methoden, die sie dann patentieren lassen.

So mag NetApp der Meinung sein Sun haette mit ZFS ehemals ihr WAFL Patent penetriert, aber das hat mit COW erstmal nichts zu tun, da dies ein Algorithmus ist, und kein Patent.
Dass das Optimierungsverfahren schon frueher fuer Filesysteme genutzt wurde, sieht man auch an Joerg Schillings Diplomarbeit zu WoFS, also vor WAFL und ZFS.

IBM beschreibt den COW Vorgang fuer Snapshots auf dieser Seite ganz anders:
http://www.ibm.com/developerworks/tivoli/library/t-snaptsm1/index.html
Es wird deutlich, dass die hier beschriebene Verfahren mit COW im eigentlichen Sinne nichts zu tun haben.

Dort steht:
A snapshot of a storage volume is created using the pre-designated space for the snapshot. When the snapshot is first created, only the meta-data about where original data is stored is copied. No physical copy of the data is done at the time the snapshot is created. Therefore, the creation of the snapshot is almost instantaneous. The snapshot copy then tracks the changing blocks on the original volume as writes to the original volume are performed. The original data that is being written to is copied into the designated storage pool that is set aside for the snapshot before original data is overwritten, hence the name „copy-on-write“.

Das beschreibt lediglich, wie IBM Snapshots erzeugt.
Naemlich:
erst werden die Bloecke in einen designierten Storage Pool kopiert ( Der originale Datenblock wird eingelesen und in ein anderes Volume kopiert ), bevor dann die originalen Daten veraendert werden ( Der originale Datenblock wird veraendert und dann an seine usprüngliche Stelle zurueckgeschreiben, so dass dieser nun ueberschrieben ist).

Der Begriff „copy-on-write“ wird hier nicht richtig verwendet. So wie IBM verfaehrt, muesste der Vorgang heissen: first-copy-then-overwrite.

Das oben beschreibene Verfahren von IBM unterscheidet sich grundlegend von der Art und Weise wie ZFS Datenblöcke per COW modifiziert.
1. ZFS schreibt nicht eine Kopie des originalen Datenblocks in einen designierten Pool.
2. ZFS überschreibt keine Datenblöcke.
3. ZFS liest einen Datenblock ein, veraendert diesen und schriebt diesen dann an eine freie Stelle im Pool.
4. Der originale Block, der noch vorhanden ist, stellt den Snapshot dar, sofern dieser erzeugt wurde.

Und weiter heisst es bei IBM:
Before a write is allowed to a block, copy-on-write moves the original data block to the snapshot storage. This keeps the snapshot data consistent with the exact time the snapshot was taken. Read requests to the snapshot volume of the unchanged data blocks are redirected to the original volume, while read requests to data blocks that have been changed are directed to the „copied“ blocks in the snapshot. Snapshot contains the meta-data that describes the data blocks that have changed since the snapshot was first created. Note that original data blocks are copied only once into the snapshot storage when the first write request is received.

Das beschriebene Verfahren bezieht sich wiederum auf das Handling der Bloecke im Storage, aber nicht die Art und Weise wie damit im Memory und VM Subsystemen umgegangen wird.
COW meint nicht, dass ein Datenblock erst an eine andere Stelle kopiert wird, das Original eingelesen, dann veraendert und schliesslich das urprüngliche Original ueberschrieben wird.
COW meint, dass ein Datenblock eingelesen, veraendert und dann an andere Stelle geschrieben werden, so dass ein neuer Block entsteht, und der Originale erhalten bleibt.

Das sind also zwei voellig unterschedliche Vorgehensweisen.

Weiter in dem IBM Artikel, wird dann noch ein weiteres Verfahren beschrieben wie IBM mit Snapshots umgeht:

Redirect-on-write
This method is quite similar to copy-on-write, without the double write penalty, and it offers storage space and performance efficient snapshots.
New writes to the original volume are redirected to another location set aside for snapshot. The advantage of redirecting the write is that only one write takes place, whereas with copy-on-write, two writes occur (one to copy original data onto the storage space, the other to copy changed data).

Es wird mit dem beschriebenen Verfahren, im Gegenstaz zum Vorherigen, keine Kopie des originalen Blocks im Snapshot Bereich erzeugt ( 1. write Operation ) und der originale Block dann ueberschrieben ( 2. write Operation ), sondern der bereits vorhandene Block im Snapshot Bereich wird direkt ueberschrieben ( 1. write Operation ). Auf diese Weise befindet sich nun der originale Block als Snapshot im originalen Volume, und die geaenderten Daten in dem Snapshot Volume. Als Folge davon muessen Datenbloecke im Falle des Loeschen von Snapshots vom Snapshotbereich zurueck kopiert werden in den originalen Bereich.

However, with redirect-on-write, the original copy contains the point-in-time data, that is, snapshot, and the changed data reside on the snapshot storage. When a snapshot is deleted, the data from the snapshot storage must be reconciled back into the original volume. Furthermore, as multiple snapshots are created, access to the original data, tracking of the data in snapshots and original volume, and reconciliation upon snapshot deletion is further complicated . The snapshot relies on the original copy of the data and the original data set can quickly become fragmented.

Wenn Snapshots mit ZFS geloescht werden, so geschieht das einfach damit, dass die Datenblöcke des Snapshots „gefreed“ werden.
Ein Kopieren von einem designierten Snapshot-Bereich zurueck in den originalen Pool ist nicht erforderlich.
Daher sind die Operationen, die mit ZFS benoetigt werden auch wesentlich geringer.

Literaturhinweise:
netapp snapshot patente:

http://www.patentgenius.com/patent/7467167.html
http://www.freepatentsonline.com/7467167.html
http://www.freepatentsonline.com/5819292.html

netapp WAFL patent mit COW:

http://www.freepatentsonline.com/6289356.html
http://www.freepatentsonline.com/5963962.html

Joerg Schillings master thesis fuer WORM file system basierend auf COW:

http://cdrecord.berlios.de/private/WoFS.pdf

IBM patent fuer COW im VM subsystem:

http://www.freepatentsonline.com/4742450.html
http://www.freepatentsonline.com/4742447.html

COW im VM subsystem, algorithmus:

http://courses.cs.vt.edu/~cs3204/spring2009/butta/local/lectures/lecture-18.pdf
http://tkhanson.net/virtual_memory.pdf
https://www.systems.inf.ethz.ch/education/past-courses/fs10/operating-systems-and-networks/slides/chapter17-6up.pdf

COW und ZFS:

http://all-unix.blogspot.com/2007/03/zfs-cow-and-relate-features.html

3 Gedanken zu “Copy On Write ( COW )

  1. Bernd schreibt:

    Die Idee CopyOnWrite ist bei allen ähnlich, aber nicht gleich umgesetzt!

    CopyOnWrite ist definitiv Microsoft NTFS. EMC Snapview nennt sein Verfahren CopyOnFirstWrite und ist nahezu identisch. NTFS schreibt aber in eine Datei und Snapview in ein Volumen.

    WAFL kann man als ReallocateOnWrite sehen oder Write Anywhere, welches ja auch das WA in WAFL bedeutet. ZFS selbst ist eigentlich ein AllocateOnWrite. ZFS schreibt nur neue Blöcke.

    CopyOnWrite hat mehr IO Operationen als WAFL und ich gehe davon aus, das ZFS ggf. sich sogar die Leseoperation sparen kann, die WAFL benötigt um die Blockdaten durch feste Blockgrößen reorganisieren zu müssen.

    Wenn ZFS als AllocateOnWrite und WAFL als WriteAnywhere bzw. ReallocatOnWrite, dann wäre die Diskussion um WAFL und ZFS wohl nie aufgekommen.

    Ich habe selbst bis auf EMC mit solchen Systemen zu tun. Kurz ZFS ist kein Abklatsch von WAFL, es ist eine verbesserte Umsetzung dieser Grundidee und dies stinkt den besagten WAFL Nutzern.

    • Microsoft NTFS ist ein journaling filesystem, welches seit NTFS v3 auch transactional ( atomare Operationen ) arbeitet, wie jedes andere log structured filesystem auch. Soweit ich weiß, ist NTFS kein COW filesystem.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s