Algorithm for Dynamic Data Distribution Preliminary Version

摘要

The replication scheme of a distributed database determines how many replicas ofeach object are created, and to which processors these replicas are allocated. This scheme critically affects the performance of a distributed system, since reading an object locally is less costly than reading is from a remote processor. Therefore in a read-intensive network a widely distributed replication is mandated. On the other hand, an update of an object is usually written to all, or a majority of the replicas, and therefore in a write-intensive network a narrowly distributed replication is mandated. In other words, the optimal replication scheme depends on the read-write pattern for each object. Currently, the replication scheme is established in a static fashion, when the distributed-database is designed, and it remains fixed until the designer manually intervenes to change the number of replicas or their location. If the read-write patterns are fixed and are known a priori, this is a reasonable solution. However, if the read-write patterns change dynamically, in unpredictable ways, a static replication scheme may lead to severe performance problems. In this paper we propose a practical algorithm, called Dynamic-Data-Allocation (DDA), that changes the replication scheme of an object(i.e. the processors which store a replica of the object) dynamically as the read-write pattern of the object changes in the network. We assume that the changes in the read-write pattern are not known a priori.