Lockfree. Write-ahead logging. In a system using WAL, all modifications are written to a log before they are applied.
Usually both redo and undo information is stored in the log. The purpose of this can be illustrated by an example. Imagine a program that is in the middle of performing some operation when the machine it is running on loses power. Upon restart, that program might well need to know whether the operation it was performing succeeded, half-succeeded, or failed. If a write-ahead log were used, the program could check this log and compare what it was supposed to be doing when it unexpectedly lost power to what was actually done. WAL allows updates of a database to be done in-place. ARIES is a popular algorithm in the WAL family. File systems typically use a variant of WAL for at least file system metadata called journaling. The PostgreSQL database system also uses WAL to provide point-in-time recovery and database replication features.[1] SQLite database also uses WAL. Shadow paging. A page in this context refers to a unit of physical storage (probably on a hard disk), typically of the order of to bytes.
If the referring pages must also be updated via shadow paging, this procedure may recurse many times, becoming quite costly. One solution, employed by the WAFL file system (Write Anywhere File Layout) is to be lazy about making pages durable (i.e. write-behind caching). This increases performance significantly by avoiding many writes on hotspots high up in the referential hierarchy (e.g.: a file system superblock) at the cost of high commit latency.
Write ahead logging is a more popular solution that uses in-place updates. Shadow paging is similar to the old master-new master batch processing technique used in mainframe database systems. Shadow paging is also similar to purely functional data structures, in that in-place updates are avoided. File System Design for an NFS File Server Appliance (The WAFL paper) PatHelland's WebLog : SOA and Newton's Universe. Bill de hOra and my old friend (from our Amazon days) Mike Dierken commented on my use of SOA versus "distributed systems".
There was also an interest in my perspective on the CAP Conjecture. Let me spew forth some thoughts... It may be a bit unusual, but my way of thinking of "distributed systems" was the 30+ year (and still continuing) effort to make many systems look like one. Distributed transactions, quorum algorithms, RPC, synchronous request-response, tightly-coupled schema, and similar efforts all try to mask the existence of independence from the application developer and from the user.
In other words, make it look to the application like many systems are one system. I wrote a paper for CIDR 2005 called "Data on the Outside versus Data on the Inside". In "distributed computing" (in my unusual usage... not in the commonly accepted vernacular), we are trying to extend this notion across multiple machine.
-----> Now, let's rant for a while about the CAP Conjecture... - Pat.