Study On Fine-Grained Partitioning Strategy For Load Balancing Based On Asynchronous Checkpoint Mechanism

Data skewness is a very common phenomenon in stream processing which is the main cause of load imbalance and may have side effect on the performance of stream processing system by increasing the latency of data processing.A more suitable partitioning strategy is needed to deal with data skewness by distributing the following data evenly to downstream operators.State migration mechanism is always needed to ensure that the position where state is hold in suits the new partitioning strategy.And inappropriate timing of partitioning strategy changes can cause consistency issues.In the state-of-art research on load balance of stream processing system,the state migration mechanism used by load balance strategy is implemented according to the one-time migration process,which suspends the stream processing system and then transfers all the states that need to be migrated.Performing migration,which will bring very high latency,can be said to be a load balance method at the cost of significantly reducing the availability of stream processing system.Therefore,we propose a fine-grained load balance strategy,named S1 load balance model,to reduce the delay of one-time migration and complete load balance at a low cost.We propose a fine-grained state migration mechanism,which divides a one-time migration into multiple fine-grained migrations,thereby reducing the cost of a single migration,and making the delay caused by the migration less abrupt.The fine-grained load balancing strategy is implemented based on this mechanism.In order to support the fine-grained state migration mechanism,we propose the S1 selection model.We define the load calculation method and the calculation method of load imbalance cost and migration cost.Among the multiple fine-grained migrations,we need to choose the state with the most benefits(that is,the least cost)to migrate preferentially,and leave the rest to the subsequent fine-grained migration.The S1 selection model provides the destination of state transition and state priority ranking queue,which can be regarded as a special grouping strategy to automatically build the model.In order to implement the fine-grained state migration mechanism,we propose the S1 partition model.We found that a fine-grained migration has a fixed minimum time,so we collect the time of the last fine-grained migration,so as to speculate the remaining state of the migration,from the remaining time and the minimum time we can calculate the most appropriate number of subsequent migrations and the state size of a single migration.This paper proposes two division strategies: maximum time division strategy and self-balancing division strategy.The maximum time division strategy can complete a fine-grained migration within the maximum time specified by the user.The model of the self-balancing division strategy is more accurate,and does not require the user to explicitly give the maximum time requirement,which is more adaptable to fine-grained migration.Based on the asynchronous checkpoint mechanism,we determine the timing of the replacement of the grouping strategy and the timing of the state transition.We can change the grouping strategy and the state of migration while maintaining distributed consistency and exactly-once semantics,thereby elegantly handling the data tilt problem.We implemented the fine-grained load balancing model on the Apache Flink platform,named S1 load balancer,and analyzed the system parameters.Experiments show that the proposed balance model can balance the load well under the condition of data tilt.And,the delay peak caused by the fine-grained migration after division is significantly reduced compared with the traditional one-time migration.We also compared the advantages and disadvantages of the S1 selection model with other grouping strategy generation models,as well as the differences between the selfbalancing division strategy and the maximum time division strategy.