GoJournal: a verified, concurrent, crash-safe journaling system

The main contribution of this paper is GoJournal, a verified, concurrent journaling system that provides atomicity for storage applications, together with Perennial 2.0, a framework for formally specifying and verifying concurrent crash-safe systems. GoJournal's goal is to bring the advantages of journaling for code to specs and proofs. Perennial 2.0 makes this possible by introducing several techniques to formalize GoJournal's specification and to manage the complexity in the proof of GoJournal's implementation. Lifting predicates and crash framing make the specification easy to use for developers, and logically atomic crash specifications allow for modular reasoning in GoJournal, making the proof tractable despite complex concurrency and crash interleavings.

GoJournal is implemented in Go, and Perennial is implemented in the Coq proof assistant. While verifying GoJournal, we found one serious concurrency bug, even though GoJournal has many unit tests. We built a functional NFSv3 server, called GoNFS, to use GoJournal. Performance experiments show that GoNFS provides similar performance (e.g., at least 90% throughput across several benchmarks on an NVMe disk) to Linux's NFS server exporting an ext4 file system, suggesting that GoJournal is a competitive journaling system. We also verified a simple NFS server using GoJournal's specs, which confirms that they are helpful for application verification: a significant part of the proof doesn't have to consider concurrency and crashes. Method Description Spec func Begin() *Op Start operation §5.2 func (*Op) ReadBuf(addr Addr, sz uint64) *Buf Read a buffer §5.3 func (*Buf) SetDirty() Mark a buffer as modified §5.3 func (*Op) OverWrite(a Addr, sz uint64, data []byte) Write without reading §5.3 func (*Op) Commit(wait bool) bool Commit by appending to in-memory log. §5.6 If wait=true, also wait until changes are on disk. func Flush() bool Flush in-memory log func (*Lockmap) Acquire(i uint64) Acquire ith lock §5.4 func (*Lockmap) Release(i uint64) Release ith lock §5.4