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;         }     } }