Houliang Qi created IOTDB-948: --------------------------------- Summary: Use binary search when checking the follower's match index when catchup Key: IOTDB-948 URL: https://issues.apache.org/jira/browse/IOTDB-948 Project: Apache IoTDB Issue Type: Improvement Components: Core/Cluster Reporter: Houliang Qi
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. -- This message was sent by Atlassian Jira (v8.3.4#803005)