impl/src/main/java/org/opencord/olt/impl/ConsistentHasher.java

/*
 * Copyright 2020-present Open Networking Foundation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.opencord.olt.impl;

import com.google.common.hash.Hashing;
import org.onosproject.cluster.NodeId;

import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Returns a server hosting a given key based on consistent hashing.
 */
public class ConsistentHasher {

    private static class Entry implements Comparable<Entry> {
        private final NodeId server;
        private final int hash;

        public Entry(NodeId server, int hash) {
            this.server = server;
            this.hash = hash;
        }

        public Entry(int hash) {
            server = null;
            this.hash = hash;
        }

        @Override
        public int compareTo(Entry o) {
            if (this.hash > o.hash) {
                return 1;
            } else if (this.hash < o.hash) {
                return -1;
            } // else
            return 0;
        }
    }

    private final int weight;

    private List<Entry> table;

    /**
     * Creates a new hasher with the given list of servers.
     *
     * @param servers list of servers
     * @param weight weight
     */
    public ConsistentHasher(List<NodeId> servers, int weight) {
        this.weight = weight;

        this.table = new ArrayList<>();

        servers.forEach(this::addServer);
    }

    /**
     * Adds a new server to the list of servers.
     *
     * @param server server ID
     */
    public synchronized void addServer(NodeId server) {
        // Add weight number of buckets for each server
        for (int i = 0; i < weight; i++) {
            String label = server.toString() + i;
            int hash = getHash(label);
            Entry e = new Entry(server, hash);
            table.add(e);
        }

        Collections.sort(table);
    }

    /**
     * Removes a server from the list of servers.
     *
     * @param server server ID
     */
    public synchronized void removeServer(NodeId server) {
        table.removeIf(e -> e.server.equals(server));
    }

    /**
     * Hashes a given input string and finds that server that should
     * handle the given ID.
     *
     * @param s input
     * @return server ID
     */
    public synchronized NodeId hash(String s) {
        Entry temp = new Entry(getHash(s));

        int pos = Collections.binarySearch(this.table, temp);

        // translate a negative not-found result into the closest following match
        if (pos < 0) {
            pos = Math.abs(pos + 1);
        }

        // wraparound if the hash was after the last entry in the table
        if (pos == this.table.size()) {
            pos = 0;
        }

        return table.get(pos).server;
    }

    private int getHash(String s) {
        // stable, uniformly-distributed hash
        return Hashing.murmur3_128().hashString(s, Charset.defaultCharset()).asInt();
    }
}