[IOTDB-948] [Distributed]Use binary search when checking the follower's match index when catchup

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Done
• Component/s: Core/Cluster
• Labels: pull-request-available
• Assignee: Houliang Qi
• Reporter: Houliang Qi
• Created: 20/Oct/20 02:06
• Updated: 12/Jan/21 07:16
• Resolved: 29/Oct/20 12:00

Description

Now, when the follower lags behind the leader a lot, one catchup task will be triggered. When catchup, it will judge whether a certain log saved in the leader's memory is consistent with the follower. If so, the leader can use logs in its memory to catch up. If the leader cannot find a log in memory that matches the follower, the leader needs to send snapshots.

When checking whether the leader's log match with the follower's, the current implementation starts from the largest index of the stored log in memory, and traverses from large to small to see whether it is consistent with the follower. However, each traversal will send one RPC. Since the maximum number of logs in memory is 1000, there may be 1000 times of RPC, and the time is O( n ). If it becomes a binary search, it only needs O(log n), and 1000 logs only need 10 RPC communications, it'll save communication cost.

Issue Links

• is a child of: IOTDB-68 IoTDB supports distributed version
• links to: GitHub Pull Request #1836