Lock-free Round Robin

Введение

Добрый день, дорогиее.

Давно думал написать статью, но как-то не доходили руки. Да и уже много все написано, причем по несколько раз. Однажды, мне нужно было реализовать распределение нагрузки по пулу.

Алгоритм

Для этого я выбрал алгоритм round robin, как наиболее простой алгоритм подходящий для данной задачи. Для тех кто не знает, что это за алгоритм, цитата из wiki:

Round-robin (от англ. round-robin — циклический) — алгоритм распределения нагрузки распределённой вычислительной системы методом перебора и упорядочения её элементов по круговому циклу.

Немного погуглив готовой реализация я не нашел, но наткнулся на статью. Статья отличная, но я решил пойти по другому пути. Написав свою реализацию.

Реализация

Для реализации я решил сделать некое подобие linked list'a с элементами конкурентного доступа. Действовать я решил по аналогии с ConcurrentLinkedQueue и использовать замечательный класс AtomicReference. Для начала я реализовал внутреннюю структуру Node.

  private static class Node<T> {
        private T element;
        private Node<T> next;

        private Node(T element) {
            this.element = element;
        }

        public void setNext(Node<T> next) {
            this.next = next;
        }
    }

Нужно это, чтобы сделать отношение между элементами по аналогии с Linked коллекциями. В общем по сути это копипаст, но в любой момент я могу расширить этот класс для удобства.

Естественно далее мне нужно было описать поля класса. Не долго думая я решил сделать всего 4 поля first,last,current и size.

• first — первый вставленный элемент
• last — последний элемент в коллекции
• current — текущий элемент для выдачи. Изначально равен первому элементу.
• size — размер коллекции.

    private AtomicInteger size = new AtomicInteger(0);
    private AtomicReference<Node<T>> first = new AtomicReference<Node<T>>();
    private AtomicReference<Node<T>> current = first;
    private AtomicReference<Node<T>> last = new AtomicReference<Node<T>>();

Перейдем к методам. Логично, что нам нужно положить в данное «кольцо» элемент, потом его достать. Поэтому я сделал два метода put и next.

public void put(T t) {
        Node<T> currentNode = new Node<T>(t);
        Node<T> lastNode = last.getAndSet(currentNode);
        if (lastNode == null) {
            first.set(currentNode);
        } else {
            lastNode.setNext(currentNode);
        }
        currentNode.setNext(first.get());
        size.incrementAndGet();
    }

Как видно по коду, изначально мы создаем экземпляр класса Node, которая в последствии будет последней. Далее мы атомарно получаем и изменяем последний элемент и делаем в нем ссылку на только что созданный. Есть простая проверка, для обработки пустой коллекции. Если у нас нету lastNode, то мы изменяем значение поле fist на «новый» Node. Также в этом методе мы делаем инкремент переменной, отвечающей за размер.

 public T next() {
        if (size.get() > 0) {
            return current.getAndSet(current.get().next).element;
        }
        throw new RuntimeException("Empty collection.");
    }

Ну и естественно метод получения следующего элемента. Логика крайне проста, мы делаем атомарный get and set и меняем текущий элемент на «следующий». Естественно если у нас нету ничего в структуре, то мы кинем простой RuntimeException.

Послесловие

Ребята, прежде всего я решил написать этот пост, чтобы написать оптимальную структуру данных и найти сразу все возможные ошибка. В мыслях было написать полноценный CyclicBuffer (многопоточный и lock-free) со всеми методами интерфейса Collection. Буду рад ответить на вопросы, выслушать замечания и предложения.
Спасибо!)

package ru.grinder.collection;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

/**
 * Created by grinder on 01.07.2014.
 */
public class RoundRobin<T> {
    private AtomicInteger size = new AtomicInteger(0);
    private AtomicReference<Node<T>> first = new AtomicReference<Node<T>>();
    private AtomicReference<Node<T>> current = first;
    private AtomicReference<Node<T>> last = new AtomicReference<Node<T>>();

    public RoundRobin() {
    }


    public boolean put(T t) {
        Node<T> currentNode = new Node<T>(t);
        Node<T> lastNode = last.getAndSet(currentNode);
        if (lastNode == null) {
            first.set(currentNode);
        } else {
            lastNode.setNext(currentNode);
        }
        currentNode.setNext(first.get());
        size.incrementAndGet();
        return true;
    }

    public T next() {
        if (size.get() > 0) {
            return current.getAndSet(current.get().next).element;
        }
        throw new RuntimeException("Empty collection.");
    }

    private static class Node<T> {
        private T element;
        private Node<T> next;

        private Node(T element) {
            this.element = element;
        }

        public void setNext(Node<T> next) {
            this.next = next;
        }
    }
}

Автор:

Источник