Read Lock Plan

How to improve Mercurial's coherency with read locks

1. Why read locks?

As described in LockingDesign, Mercurial currently is designed to use no locking for read-only operations. This generally works quite well with Mercurial's append-only design and means that there can be an unlimited number of simultaneous readers (for instance, with hgweb), but various features can conflict with it:

• rollback
• strip / rebase
• bookmarks
• phases

For instance, a clone that's in progress when a rollback happens can be corrupted.

A read lock is a type of lock that allows any number of other readers but does not allow writers. Thus, it would protect any in-progress read-only operations (like clones) from operations like rollback or strip that might cause issues.

2. Design

2.1. Definitions

• a reader is a client that wants to do a read-only or read-write operation
• an appender is a client that wants to append data in a way that won't upset readers
• a destroyer is a client that wants to change data (eg strip) that might upset readers

2.2. Requirements

Ideally, we want to have:

• any number of simultaneous readers
• readers exclude destroyers but not appenders
• appenders exclude other appenders, but not readers
• destroyers exclude readers and appenders

Mercurial currently handles the first two, but not the last (limited to extensions and the rollback command). To add appenders to the mix, we need to be able to do the following:

• keep track of an arbitrary number of readers efficiently
• atomically exclude new readers
• keep destroyers from waiting forever

2.3. Implementation

We can accomplish this with a new reader/ lock directory in .hg/store. When the directory exists, readers just need to create a uniquely-named lock file in the directory to indicate they're in the process of reading and delete it when they're done. This obviously isn't as fast as doing nothing, but should still be pretty fast.

When a destroyer wants to take over, it first takes the write lock to exclude appenders and other destroyers. It then attempts to delete the reader directory. If there are no read locks in the directory, rmdir will succeed. If rmdir fails, it loops until it succeeds. To unlock, it recreates the reader directory, and releases the write lock.

However, a destroyer may wait forever if new readers keep appearing. To prevent this, it renames the reader directory to reader-blocked. New readers will wait for the reader directory to reappear, while old readers will try deleting their read locks from both locations.

Appenders continue to work as before, however all appenders should take a read lock when they start to prevent destroyers from confusing them.

2.4. Issues

• Taking a read lock is impossible on a read-only filesystem
• Directory rename may not be atomic on some filesystems (Plan 9?)

3. See also

• LockingDesign