Why do SQL databases use a write-ahead log over a command log?

Question

I read about Voltdb's command log. The command log records the transaction invocations instead of each row change as in a write-ahead log. By recording only the invocation, the command logs are kept to a bare minimum, limiting the impact the disk I/O will have on performance.

Can anyone explain the database theory behind why Voltdb uses a command log and why the standard SQL databases such as Postgres, MySQL, SQLServer, Oracle use a write-ahead log?

Redevelop

How does Voltdb implement "undo" functionality? If I do UPDATE some_table SET some_column=2 then knowing the command doesn't allow me to roll back the change? – Remex

It is also a reliable means to identify incomplete DB writes in the event of a power failure. – Marylynnmarylynne

@MartinSmith, answering your question: latest snapshot + command replay starting from that time. voltdb.com/docs/graphics/CmdLogPicture.png – Spermatium

VoltDB doesn't run commands concurrently - it runs single commands to completion from a queue - therefore a command log suffices - if you "rerun" the command log, it will give you the state of the db to the point of the last command run - with concurrency, that isn't the case - commands are interleaved! – Trafficator

Answer 1

I think it is better to rephrase:

Why does new distributed VoltDB use a command log over write-ahead log?

Let's do an experiment and imagine you are going to write your own storage/database implementation. Undoubtedly you are advanced enough to abstract a file system and use block storage along with some additional optimizations.

Some basic terminology:

• State : stored information at a given point of time
• Command : directive to the storage to change its state

So your database may look like the following:

Next step is to execute some command:

Please note several important aspects:

1. A command may affect many stored entities, so many blocks will get dirty
2. Next state is a function of the current state and the command

Some intermediate states can be skipped, because it is enough to have a chain of commands instead.

Finally, you need to guarantee data integrity.

• Write-Ahead Logging - central concept is that State changes should be logged before any heavy update to permanent storage. Following our idea we can log incremental changes for each block.
• Command Logging - central concept is to log only Command, which is used to produce the state.

There are Pros and Cons for both approaches. Write-Ahead log contains all changed data, Command log will require addition processing, but fast and lightweight.

VoltDB: Command Logging and Recovery

The key to command logging is that it logs the invocations, not the consequences, of the transactions. By recording only the invocation, the command logs are kept to a bare minimum, limiting the impact the disk I/O will have on performance.

Additional notes

SQLite: Write-Ahead Logging

The traditional rollback journal works by writing a copy of the original unchanged database content into a separate rollback journal file and then writing changes directly into the database file.

A COMMIT occurs when a special record indicating a commit is appended to the WAL. Thus a COMMIT can happen without ever writing to the original database, which allows readers to continue operating from the original unaltered database while changes are simultaneously being committed into the WAL.

PostgreSQL: Write-Ahead Logging (WAL)

Using WAL results in a significantly reduced number of disk writes, because only the log file needs to be flushed to disk to guarantee that a transaction is committed, rather than every data file changed by the transaction.

The log file is written sequentially, and so the cost of syncing the log is much less than the cost of flushing the data pages. This is especially true for servers handling many small transactions touching different parts of the data store. Furthermore, when the server is processing many small concurrent transactions, one fsync of the log file may suffice to commit many transactions.

Conclusion

Command Logging:

1. is faster
2. has lower footprint
3. has heavier "Replay" procedure
4. requires frequent snapshot

Write Ahead Logging is a technique to provide atomicity. Better Command Logging performance should also improve transaction processing. Databases on 1 Foot

Confirmation

VoltDB Blog: Intro to VoltDB Command Logging

One advantage of command logging over ARIES style logging is that a transaction can be logged before execution begins instead of executing the transaction and waiting for the log data to flush to disk. Another advantage is that the IO throughput necessary for a command log is bounded by the network used to relay commands and, in the case of Gig-E, this throughput can be satisfied by cheap commodity disks.

It is important to remember VoltDB is distributed by its nature. So transactions are a little bit tricky to handle and performance impact is noticeable.

VoltDB Blog: VoltDB’s New Command Logging Feature

The command log in VoltDB consists of stored procedure invocations and their parameters. A log is created at each node, and each log is replicated because all work is replicated to multiple nodes. This results in a replicated command log that can be de-duped at replay time. Because VoltDB transactions are strongly ordered, the command log contains ordering information as well. Thus the replay can occur in the exact order the original transactions ran in, with the full transaction isolation VoltDB offers. Since the invocations themselves are often smaller than the modified data, and can be logged before they are committed, this approach has a very modest effect on performance. This means VoltDB users can achieve the same kind of stratospheric performance numbers, with additional durability assurances.

Spermatium

With WAL, readers read from pages from unflushed logs. With command logging, do you have have the ability to read from the command log... nope. So command logging is vastly different. VoltDB uses command logging to create recovery points and ensure durability. WAL is used to ensure durability, but also to improve speed. For example, you can locate the WAL on a solid-state drive, and watch as SQLITE performance approaches in-memory DB's like Volt and Redis - while taking up a fraction of RAM. – Egret

@ErikAronesty, don't think I got you. Is there significant difference between WAL and CL? Sure, the difference is pretty significant. Both provides recovery points. So, what is the point? – Spermatium

Are there non-deterministic operations in Volt, such as random()? If so, how is a command like this expressed? I presume it is materialized on the receiver node and then replicated? – Forthcoming

What do you think of my comment to the OP? – Trafficator

Answer 2

From the description of Postgres' write ahead http://www.postgresql.org/docs/9.1/static/wal-intro.html and VoltDB's command log (which you referenced), I can't see much difference at all. It appears to be the identical concept with a different name.

Both sync only the log file to the disk but not the data so that the data could be recovered by replaying the log file.

Section 10.4 of VoltDB explains that their community version does not have command log so it would not pass the ACID test. Even in the enterprise edition, I don't see the details of their transaction isolation (e.g. http://www.postgresql.org/docs/9.1/static/transaction-iso.html) needed to make me comfortable that VoltDB is as serious as Postges.

Wad

Answer 3

With WAL, readers read from pages from unflushed logs. No modification is made to the main DB. With command logging, you have no ability to read from the command log.

Command logging is therefore vastly different. VoltDB uses command logging to create recovery points and ensure durability, sure - but it is writing to the main db store (RAM) in real time - with all the attendant locking issues, etc.

Egret

Answer 4

The way I read it is as follows: (My own opinion)

Command Logging as described here logs only transactions as they occur and not what happens in or to them. Ok, so here is the magic piece... If you want to rollback you need to restore the last snapshot and then you can replay all the transactions that were applied after that (Described in the link above). So effectively you are restoring a backup and re-applying all your scripts, only VoltDB has now automated it for you.

The real difference that i see with this is that you cannot rollback to a point in time logically as with a normal transaction log. Normal transaction logs (MSSQL, MySQL etc.) can easily rollback to a point in time (in the correct setup) as the transactions can be 'reversed'.

Interresting question comes up - referring to the pos by pedz, will it always pass the ACID test even with the Command Log? Will do some more reading...

Add: Did more reading and I don't think this is a good idea for very big and busy transactional databases. A DB snapshot is automatically created when the Command Logs fill up, to save you from big transaction logs and the IO used for this? You are going to incur large IO amounts with your snapshots being done at a regular interval and you are also using your memory to the brink. Alos, in my view you lose your ability to rollback easily to a point in time before the last automatic snapshot - think this will get very tricky to manage.

I'll rather stick to Transaction Logs for Transactional systems. It's proven and it works.

Bibliotheca

Answer 5

Its really just a matter of granularity. They log operations at the level of stored procedures, most RDBMS log at the level of individual statements (and 'lower'). Also their blurb regarding advantages is a bit of a red herring:

One advantage of command logging over ARIES style logging is that a transaction can be logged before execution begins instead of executing the transaction and waiting for the log data to flush to disk.

They have to wait for the command to be logged too, its just a much smaller record.

If I'm not mistaken VoltDB's unit of transaction is a stored proc. Traditional RDBMS usually need to support ad-hoc transactions containing any number of statements, so procedure-level logging is out of the question. Furthermore stored procedures are often not truly deterministic in traditional RDBMS (i.e. given params+log+data always produce same output), which they would have to be for this to work.

Nevertheless the performance improvements would be substantial for this constrained RDBMS model.

Forefoot

Answer 6

Few terminologies before I start explaining:

Logging schemes: The database uses logging schemes such as Shadow paging, Write Ahead Log (WAL), to implement concurrency, isolation, and durability (how is a different topic).

In order to understand why WAL is better, let's see an issue with shadow paging. In shadow paging, the database uses a master version and a shadow version of the database so that if the table size is 1 billion and the buffer pool manager does not have enough memory to hold all the tuple (records) in the memory the dirty pages are not written to the master version until the transaction(s) are not committed.

Once all the transactions are committed, the flag is switched and the shadow version becomes the master version. In the diagram above there are Page 3 and Page 5 that are old and can be garbage collected.

1. The issue with this approach is a large number of fragmented tuples left behind which is randomly located, this is slower as compared to if the dirty pages are sequentially accessed, and this is what Write Ahead Log does.

2. The other advantage of using WAL is the runtime performance (as you are not doing random IO to flush out the pages) but slower recovery time. Whereas, with shadow paging, the recovery performance is faster (which is required occasionally).

Iolaiolande