Ever-increasing demands for high transaction rates, limitations of high-end processors, high availability and modular growth considerations are all driving forces towards distributed architectures for transaction processing. A key prerequisite to take advantage of the capacity of a distributed transaction processing system, however, is an effective strategy for workload allocation. The distribution of the workload should not only achieve load balancing, but also support an efficient transaction processing with a minimum of inter-system communication. To this end, adaptive schemes for transaction routing have to be employed which are highly responsive to workload fluctuations and configuration changes. Adaptive allocation schemes are also important for simplifying system administration which is a major problem in distributed transaction processing systems.

We develop a taxonomical framework for workload allocation, in particular transaction routing, in distributed transaction processing systems. This framework considers the influence of the underlying system architecture (e.g. shared nothing, shared disk) and transaction execution model as well as the major dependencies between workload, program and data allocation. The main part of the framework covers structural (or architectural) and implementational alternatives for transaction routing to help identify key factors and basic tradeoffs in the design of appropriate allocation schemes. Finally, we show how existing schemes fit under our taxonomy. The framework substantially facilitates a comparison of the different schemes and can guide the development of new, more effective protocols.