Fractional data allocation method for distributed databases

Abstract

High performance transaction processing in a distributed database (DDB) system can only be achieved through a high degree of locality of access, which may be attainable by appropriate data allocation. In this paper we discuss an adaptive data allocation method for DDB systems maintaining resource allocation data, as in airline reservations and inventory control applications. According to the Fractional Data Allocation (FDA) method fractions of certain widely used resources are apportioned in the form of tokens among the nodes of the network, such that most resource allocation requests can be processed locally. When a resource allocation request cannot be processed locally, or a data fault occurs, tokens are borrowed from other network nodes through independent token transfer transactions. The initial allocation of tokens and system reconfiguration for token reallocation are based on anticipated demand. We also discuss the allocation of metadata in the DDB to make these activities possible. An abstract model, based on the count of token transfer messages, is used to specify an optimal initial data allocation, and to investigate the effect of token borrowing and reallocation policies.