[Из песочницы] Lock-free Round Robin04.07.2014 09:49

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

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

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

Реализация Для реализации я решил сделать некое подобие linked list’a с элементами конкурентного доступа. Действовать я решил по аналогии с ConcurrentLinkedQueue и использовать замечательный класс AtomicReference. Для начала я реализовал внутреннюю структуру Node. private static class Node { private T element; private Node next;

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

public void setNext (Node next) { this.next = next; } } Нужно это, чтобы сделать отношение между элементами по аналогии с Linked коллекциями. В общем по сути это копипаст, но в любой момент я могу расширить этот класс для удобства.

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

first — первый вставленный элемент last — последний элемент в коллекции current — текущий элемент для выдачи. Изначально равен первому элементу. size — размер коллекции. private AtomicInteger size = new AtomicInteger (0); private AtomicReference> first = new AtomicReference>(); private AtomicReference> current = first; private AtomicReference> last = new AtomicReference>(); Перейдем к методам. Логично, что нам нужно положить в данное «кольцо» элемент, потом его достать. Поэтому я сделал два метода put и next.

public void put (T t) { Node currentNode = new Node(t); Node 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. Буду рад ответить на вопросы, выслушать замечания и предложения.Спасибо!)Full Code 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 { private AtomicInteger size = new AtomicInteger (0); private AtomicReference> first = new AtomicReference>(); private AtomicReference> current = first; private AtomicReference> last = new AtomicReference>();

public RoundRobin () { }

public boolean put (T t) { Node currentNode = new Node(t); Node 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 { private T element; private Node next;

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

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