SNOWBALL - SCALABLE STORAGE ON NETWORKS OF WORKSTATIONS WITH BALANCEDLOAD

Networks of workstations are an emerging architectural paradigm for hi gh-performance parallel and distributed systems. Exploiting networks o f workstations for massive data management poses exciting challenges. We consider here the problem of managing record-structured data in suc h an environment. For example, managing collections of HTML documents on a cluster of WWW servers is an important application for which our approach provides support. The records are accessed by a dynamically g rowing set of clients based on a search key (e.g.,a URL). To scale up the throughput of client accesses with approximately constant response time, the records and thus also their access load are dynamically red istributed across a growing set of workstations. The paper addresses t wo problems of realistic workloads: skewed access frequencies to the r ecords and evolving access patterns where previously cold records may become hot and vice versa. Our solution incorporates load tracking at different levels of granularity and automatically chooses the appropri ate granularity for dynamic data migrations. Experimental results base d on a detailed simulation model show that our method is indeed succes sful in providing scalable cost/performance and explicitly controlling its level.