Research On Self-adaptive Mixed Consistency Management

The research of consistency management has developed along With the birth of distributed systems. Maintaining data consistency in distributed systems is a fundamental and complex task. In a distributed system, in order to achieve processing acceleration, there may be the same copy of a shared data in the same block on different processing nodes. Thus, if modification to a shared data block on a node happens, consistency conflicts will arise. So a mechanism that can notice other nodes is needed to avoid the consistency of conflict when modification happens.We analyzed the consistency strategies of multi-processor shared memory systems and distributed shared memory (DSM) system in this paper. After that, we concluded that there are three basis consistency strategies that they are mutex, write-invalidate and write-update. Studies to all the existing consistent strategies have shown that every consistent strategy is not fit to all applications and even the same procedure have different requirements on the consistency strategy in different processing periods. Then use one uniform consistent policy will not satisfy all the needs of applications. Therefore, a variety of consistency strategies are needed. Choose one strategy where it's appropriate. Thus, it needs to determine what the circumstances in a strategy adapt and how to change strategy. The existing mechanisms are either not self-adaptive or only basing on static analysis of program behavior. But the basic problem of coherency management is to measure the competition. In the final analysis, the inconsistent is due to several visitors competing to update the same shared block copy. Therefore, not accurate measure of the competition can't produce an efficient consistent strategy. However, just from the static analysis of program behavior is not possible to measure competition accurately, and only from the static analysis of program behavior characteristics to choose an algorithm is not accurate.Moreover, both write-invalidate and write-update are not suitable for big block cache systems.In this paper, we proposed a self-adaptive mixed consistency management mechanism to solve these problems. We combine static analysis of program behavior and measuring competition dynamically to select a consistency strategy. The mechanism includes mutex strategy, write-invalidate strategy and write-update strategy and choose one of them automatically to adaptive to a certain program. Thus, it can enhance the adaptability of the system. The real-time tasks have the requirements of exclusively access to data; in order to meet this demand, real-time tasks need to use mutex strategy. For common tasks, it is need to choose strategy between write-invalidate strategies and write-update strategy. By the compiler analysis of the program we can get two basic parameters. So we can measure behavior characteristics of the block through these two parameters, which can estimate the operating behaviors of the program to share data within the block. Thus, at a time when the program is to (or out) of a block of competition, you can calculate the cost of different strategies on the difference. Thus, at the time that the program is to (or out) of a block of competition, the cost of the block using one strategy can be calculate separately. So we can measure the cost of the two strategies when the node join (or leave) the competition to the block. If the current consistent strategy is more expensive (that is, when the profit value becomes negative) then it is necessary transforming to less expensive strategy. It is not needed to recalculate the formula each time, but only calculate the incremental benefits and amending costs of the previous nodes.Actually, the shared memory is separated into three logical block sets. All blocks in a same set use a same strategy. As time progresses, competition changes, all blocks move among the three sets. There are also three consistency algorithms running on each node. They control separately parts of the work set of the program and using the appropriate strategy to minimize the cost. Thus, by using a strategy that can minimize the transient cost of a shared block can minimize the total cost of managing consistency.The main factors affect the cost of the mechanism are failure rate, replacement rate, number of nodes and the number of competing nodes. Failure rate and replacement rate for most systems are not great, which means that the state of competition, once established, it will be stable for some time, which means that only the initial access to shared data in tasks begin (or swap the shared blocks at the task end), the mechanism will cause the cost and only in this case can strategy change happened.We also gave an implementation of the mechanism in a loosely coupled distributed environment in this paper. In this implementation, a coordinator is used to manage the control blocks and to choose the strategy. So that the cost is reduced further. A seamless sequencer is used in the system to meet the request sequential consistency. Experiments show that the adaptive mixed consistency management mechanism can choose an appropriate coherence strategy base on the current competition with less overhead and both to avoid the appearance of trashing and extra update propagation. In addition, the mechanism has a stronger ability to adapt more complicated applications.After verified the effectiveness of the mechanism, we briefly introduced the application of the mechanism in a data retrieval clustered system. The project acceptance confirmed the practical of the mechanism.