OXenstored An Efficient Hierarchical and Transactional Database using Functional Programming with Reference Cell Comparisons

摘要

We describe in this paper our implementation of the Xenstored ser-vice which is part of the XEN architecture. Xenstored maintains a hierarchical and transactional database, used for storing and man-aging configuration values. We demonstrate in this paper that mixing functional data-structures together with reference cell comparison, which is a limited form of pointer comparison, is: (i) safe; and (ii) efficient. This demonstra-tion is based, first, on an axiomatization of operations on the tree-like structure we used to represent the Xenstored database. From this axiomatization, we then derive an efficient algorithm for co-alescing concurrent transactions modifying that structure. Finally, we experimentally compare the performance of our implementa-tion, that we called OXenstored, and the C implementation of the Xenstored service distributed with the XEN hypervisor sources: the results show that OXenstored is much more efficient than its C counterpart. As a direct result of this work, OXenstored will be included in fu-ture releases of XENSERVER, the virtualization product distributed by Citrix Systems, where it will replace the current implementation of the Xenstored service.