The performance of concurrent data structure algorithms
Dennis E. Shasha, Theodore J. Johnson · 1990
This thesis develops a validated of concurrent data structure algorithm performance, concentrating on concurrent B-trees. The thesis first develops two analytical tools, which are explained in the next two paragraphs, for the analysis. Yao showed that the space utilization of a B-tree built from random inserts is 69%. Assuming that nodes merge only when empty, we show that the utilization is 39% when the number of insert and delete operations is the same. However, if there are just 5% more inserts than deletes, then the utilization is at least 62%. In addition to the utilization, we calculate the probabilities of splitting and merging, important parameters for calculating concurrent B-tree algorithm performance. We compare merge-at-empty B-trees with merge-at-half B-trees. We conclude that merge-at-empty B-trees have a slightly lower space utilization but a much lower restructuring rate, making merge-at-empty B-trees preferable for concurrent B-tree algorithms. We analyze queues that service readers and writers. Readers are served concurrently and writers are served serially. Customers receive service in FCFS order. We show that the additional time that a writer must wait for preceding readers increases logarithmically with the proportion of readers to writers. From this, we can calculate the expected wait in the queue and the capacity of the queue. We use the analytical tools to model a representative set of concurrent B-tree algorithms. The algorithms use a variety of locking, restructuring and path recovery techniques. The analyses, which are validated by simulations, show that the Link-style algorithms are by far the best. The analyses are extended to account for buffering and database recovery. We show that holding non-leaf locks until commit time is bad for performance. The analysis of concurrent B-tree algorithms can be extended to cover other concurrent data structure algorithms. We describe a template for analyzing concurrent tree data structures, and apply the template to some concurrent extensible hashing schemes.