[HBASE-19917] Improve RSGroupBasedLoadBalancer#filterServers() to be more efficient

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Fixed
• Fix Version/s: 2.0.0-beta-2, 1.4.2, 2.0.0
• Component/s: rsgroup
• Hadoop Flags: Reviewed
• Assignee: Xiang Li
• Reporter: Xiang Li
• Created: 02/Feb/18 00:41
• Updated: 01/Feb/19 20:21
• Resolved: 05/Feb/18 01:24

Description

hbase-rsgroup/src/main/java/org/apache/hadoop/hbase/rsgroup/RSGroupBasedLoadBalancer.java

private List<ServerName> filterServers(Collection<Address> servers,
    Collection<ServerName> onlineServers) {
  ArrayList<ServerName> finalList = new ArrayList<ServerName>();
  for (Address server : servers) {
    for(ServerName curr: onlineServers) {
      if(curr.getAddress().equals(server)) {
        finalList.add(curr);
      }
    }
  }
  return finalList;
}

filterServers is to return the union of servers and onlineServers. The current implementation has time complexity as O(m * n) (2 loops), could be in O(m + n) if HashSet is used. The trade-off is space complexity is increased.

Another point which could be improved: filterServers() is only called in filterOfflineServers(). filterOfflineServers calls filterServers(Set, List). The current filterServers(Collection, Collection) seems could be improved.