ARIES/LHS: A concurrency control and recovery method using write-ahead logging for linear hashing with separators

Abstract

Larson has proposed a dynamic hashing algorithm called Linear Hashing with Separators (LHS) that, given a unique primary key value, uses a table in memory to allow the retrieval of the corresponding record in the file in one page access to secondary storage. Larson considers LHS to be the first practical method offering one-access retrieval for large dynamic files. He did not discuss the impact of concurrent operations by different users, some of whom are reading the file while others are performing operations like inserts, deletes, updates, file expansions or file contractions which can cause relocations of records. We present a method, called ARIES/LHS (Algorithm for Recovery and Isolation Exploiting Semantics for Linear Hashing with Separators), for controlling such concurrent operations with fine-granularity (e.g., record) locking, while guaranteeing serializability. ARIES/LHS prevents rolling back transactions from getting involved in deadlocks. It also includes recovery techniques for handling transaction and system failures, while allowing multiple operations in each transaction.