Lightweight Recoverable Virtual MemoryM. Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steere, James J. KistlerSchool of Computer ScienceCarnegie Mellon UniversityThis combination of circumstances is most likely to beAbstractfound in situations involving the meta-data of storageRecoverable virtual memory refers to regions of a virtualrepositories. Thus RVM can benefit a wide range ofaddress space on which transactional guarantees areapplications from distributed file systems and databases, tooffered. This paper describes RVM, an efficient, portable,and easily used implementation of recoverable virtualobject-oriented repositories, CAD tools, and CASE tools.memory for Unix environments. A unique characteristicRVM can also provide runtime support for persistentof RVM is that it allows independent control over theprogramming languages. Since RVM allows independenttransactional properties of atomicity, permanence, andcontrol over the basic transactional properties of atomicity,serializability. This leads to considerable flexibility in thepermanence, and serializability, applications haveuse of RVM, potentially enlarging the range ofconsiderable flexibility in how they use transactions.applications than can benefit from transactions. It alsosimplifies the layering of functionality such as nesting andIt may often be tempting, and sometimes unavoidable, todistribution. The paper shows that RVM performs welluse a mechanism that is richer in functionality or betterover its intended range of usage even though it does notintegrated with the operating system. But our experiencebenefit from specialized operating system support. It alsohas been that such sophistication comes at the cost ofdemonstrates the importance of intra- and inter-portability, ease of use and more onerous programmingtransaction optimizations.constraints. Thus RVM represents a balance between thesystem-level concerns of functionality and performance,1. Introductionand the software engineering concerns of usability andHow simple can a transactional facility be, while remainingmaintenance. Alternatively, one can view RVM as ana potent tool for fault-tolerance? Our answer, as elaboratedexercise in minimalism. Our design challenge lay not inin this paper, is a user-level library with minimalconjuring up features to add, but in determining what couldprogramming constraints, implemented in about 10K linesbe omitted without crippling RVM.of mainline code and no more intrusive than a typicalWe begin this paper by describing our experience withruntime library for input-output. This transactional facility,Camelot [10], a predecessor of RVM. This experience, andcalled RVM, is implemented without specialized operatingour understanding of the fault-tolerance requirements ofsystem support, and has been in use for over two years on aCoda [16, 30] and Venari [24, 37], were the dominantwide range of hardware from laptops to servers.influences on our design. The description of RVM followsRVM is intended for Unix applications with persistent datain three parts: rationale, architecture, and implementation.structures that must be updated in a fault-tolerant manner.Wherever appropriate, we point out ways in which usageThe total size of those data structures should be a smallexperience influenced our design. We conclude with anfraction of disk capacity, and their working set size mustevaluation of RVM, a discussion of its use as a buildingeasily fit within main memory.block, and a summary of related work.This work was sponsored by the Avionics Laboratory, Wright Research2. Lessons from Camelotand Development Center, Aeronautical Systems Division (AFSC), U.S.Air Force, Wright-Patterson AFB, Ohio, 45433-6543 under Contract2.1. OverviewF33615-90-C-1465, ARPA Order No. 7597. James Kistler is nowCamelot is a transactional facility built to validate theaffiliated with the DEC Systems Research Center, Palo Alto, CA.thesis that general-purpose transactional support wouldThis paper appeared in ACM Transactions on Computer Systems, 12(1),simplify and encourage the construction of reliableFeb. 1994 and Proceedings of the 14th ACM Symposium on OperatingSystems Principles, Dec. 1993.distributed systems [33]. It supports local and distributednested transactions, and provides considerable flexibility inthe choice of logging, synchronization, and transactioncommitment strategies. Camelot relies heavily on the Camelot would be something of an overkill. Yet weexternal page management and interprocess persisted, because it would give us first-hand experience incommunication facilities of the Mach operating system [2], the use of transactions, and because it would contributewhich is binary compatible with the 4.3BSD Unix towards the validation of the Camelot thesis.operating system [20]. Figure 1 shows the overall structureWe placed data structures pertaining to Coda meta-data inof a Camelot node. Each module is implemented as a1recoverable memory on servers. The meta-data includedMach task and communication between modules is viaCoda directories as well as persistent data for replicaMach’s interprocess communication facililty(IPC).control and internal housekeeping. The contents of eachCoda file was kept in a Unix file on a server’s local filesystem. Server recovery consisted of Camelot restoringrecoverable memory to the last committed state, followedby a Coda salvager which ensured mutual consistencybetween meta-data and data.2.3. ExperienceThe most valuable lesson we learned by using Camelot wasthat recoverable virtual memory was indeed a convenientand practically useful programming abstraction for systemslike Coda. Crash recovery was simplified because datastructures were restored in situ by Camelot. Directoryoperations were merely manipulations of in-memory datastructures. The Coda salvager was simple because therange of error states it had to handle was small. Overall,Mach KernelComponentsSystemCamelotRecoverableProcessesLibraryApplicationLibraryLibraryData ServerLibraryNode ServerData ServerLibrary Disk ManagerLogTransactionCom Manager Recovery ManagerLog Control Master Camelot NCAthe encapsulation of messy crash recovery details intoThis figure shows the internal structure of Camelot as well as itsCamelot considerably simplified Coda server code.relationship to application code. Camelot is composed of severalMach tasks: Master Control, Camelot, and Node Server, as