Introduction

I have been reading about Consistent Hashing and in an attempt to better understand the concept, I wanted to implement a simple hash ring.

I did not implement the concept of virtual nodes / replication across multiple node. The focus of this exercise was to build a simple implementation of an in-memory hash ring where nodes and key/value pairs could be added and removed.

Discussion

The idea was that nodes and entries could occupy "positions" along the circumference of the hash ring. These positions would be represented by ints from 0 to Integer.MAX_INTEGER.

A client of the SimpleHashRing could add / remove nodes at certain "positions". They could also add / remove entries with a certain key - and there would be a mapping of each key to a position on the hash ring. These entries would then be assigned (based on their key's position) to the next node on the ring in ascending order, wrapping from Integer.MAX_INTEGER to 0, if necessary.

Design Decisions

The HashRing interface

Putting a Position class on the interface itself is restrictive in the sense that each implementation of the HashRing interface, must use a similar "position" paradigm. Maybe this is too restrictive?

The SimpleHashRing implementation

I throw an exception if a hash ring instance is created without at least one node. This seemed reasonable to me, since I couldn't think of a use-case where you'd want to use a hash ring without at least one node defined.

I basically have two internal data structures - a List of Positions that represent the Positions of the nodes in the hash ring, sorted from smallest Position to largest Position.

I also have a Map from Positions to a Map of key/value pairs that represent node positions to the entries located at that position.

These two data structures should support the behavior of adding and removing nodes in the hash ring.

Implementation

The HashRing interface

public interface HashRing<Key, Value> {
    class AtLeastOneNodeMustExist extends Exception {
    }

    class Position implements Comparable<Position> {
        private final int value;

        public Position(int value) {
            if (0 > value) {
                throw new IllegalArgumentException("value must be non-negative");
            }
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Position position = (Position) o;
            return value == position.value;
        }

        @Override
        public int hashCode() {
            return Objects.hash(value);
        }

        @Override
        public int compareTo(Position o) {
            return Integer.compare(this.value, o.value);
        }
    }

    void addNode(Position position);

    void removeNode(Position position) throws AtLeastOneNodeMustExist;

    Optional<Value> addEntry(Key key, Value value);

    Optional<Value> removeEntry(Key key);

    Optional<Value> getValue(Key key);
}

The SimpleHashRing implementation

public class SimpleHashRing<Key, Value> implements HashRing<Key, Value> {
    private final List<Position> nodePositions;
    private final Map<Position, Map<Key, Value>> entriesByPosition;
    private final Function<Key, Position> keyToPositionCalculator;

    public SimpleHashRing(final Set<Position> nodePositions, final Function<Key, Position> keyToPositionCalculator) throws AtLeastOneNodeMustExist {
        if (nodePositions.isEmpty()) {
            throw new AtLeastOneNodeMustExist();
        }

        this.nodePositions = nodePositions
                .stream()
                .sorted(Comparator.comparingInt(Position::getValue))
                .collect(Collectors.toList());
        this.entriesByPosition = nodePositions
                .stream()
                .collect(
                        Collectors.toMap(
                                Function.identity(),
                                (v) -> new HashMap<>()
                        )
                );
        this.keyToPositionCalculator = keyToPositionCalculator;
    }

    @Override
    public void addNode(final Position position) {
        final Map<Key, Value> positionEntries = entriesByPosition.putIfAbsent(position, new HashMap<>());
        if (null == positionEntries) {
            final int followingNodePosition = Math.abs(Collections.binarySearch(nodePositions, position) + 1);
            final int currentNodeIndex = Math.max(followingNodePosition, 0);
            nodePositions.add(currentNodeIndex, position);

            final Map<Key, Value> followingNodeEntries = entriesByPosition.get(nodePositions.get(followingNodePosition));
            final Map<Key, Value> currentNodeEntries = followingNodeEntries
                    .entrySet()
                    .stream()
                    .filter(
                            e -> 0 > this.keyToPositionCalculator.apply(e.getKey()).compareTo(position)
                    )
                    .collect(
                            Collectors.toMap(
                                    Map.Entry::getKey,
                                    Map.Entry::getValue
                            )
                    );
            entriesByPosition.put(position, currentNodeEntries);
            followingNodeEntries.keySet().removeAll(currentNodeEntries.keySet());
        }
    }

    @Override
    public void removeNode(final Position position) throws AtLeastOneNodeMustExist {
        final Map<Key, Value> entries = entriesByPosition.get(position);
        if (null != entries) {
            if (1 < entriesByPosition.size()) {
                final int currentNodeIndex = Collections.binarySearch(nodePositions, position);
                final int followingNodeIndex = (currentNodeIndex + 1) % nodePositions.size();
                this.entriesByPosition.get(this.nodePositions.get(followingNodeIndex)).putAll(entries);
                entriesByPosition.remove(position);
                nodePositions.remove(currentNodeIndex);
                return;
            }

            throw new AtLeastOneNodeMustExist();
        }
    }


    @Override
    public Optional<Value> addEntry(final Key key, final Value value) {
        return getEntriesForKey(key).map(entries -> entries.put(key, value));
    }

    @Override
    public Optional<Value> removeEntry(final Key key) {
        return getEntriesForKey(key).map(entries -> entries.remove(key));
    }

    @Override
    public Optional<Value> getValue(final Key key) {
        return getEntriesForKey(key).map(entries -> entries.get(key));
    }

    private Optional<Map<Key, Value>> getEntriesForKey(final Key key) {
        return Optional.ofNullable(
                entriesByPosition.get(
                        nodePositions.get(calculateNodePositionForKey(key))
                )
        );
    }

    private int calculateNodePositionForKey(final Key key) {
        final int nodePositionIndex;
        {
            final int searchedIndex = Collections.binarySearch(nodePositions, keyToPositionCalculator.apply(key));
            if (0 > searchedIndex) {
                nodePositionIndex = Math.abs(searchedIndex) - 1;
            } else {
                nodePositionIndex = searchedIndex;
            }
        }

        return nodePositionIndex % nodePositions.size();
    }
}
```