11 January 2011

Реализация потокобезопастного алгоритма round-robin на Java

Java
Sandbox
Доброго времени суток, уважаемый хабрачитатель.
В один прекрасный рабочий день начальство поставило задачу добавить в разрабатываемую нами систему возможность использовать несколько серверов для повышения производительности. Разворачивать кластер и осуществлять балансировку за счет специализированных средств возможности не было. Поэтому пришлось придумывать свою реализацию, используя алгоритм round-robin.

Алгоритм


Исходя из архитектуры приложения было принято решение, что балансировку нужно осуществить проходя по списку серверов, которые задаются в конфигурации, и выдавать на новый запрос адрес следующего сервера.

Этот принцип лежит в основе алгоритма round-robin.

Реализация


Проведя поиск в интернете, я нашел много вариантов реализации данного алгоритма, которые сводились к следующему коду:
    public synchronized Entity getNext_Iterator(){
        if (!it.hasNext()) {
            it = objectList.iterator();
        }
        return it.next();
    }


Здесь objectList — это список доступных серверов.

В данной реализации мне не понравилось использование synchronized метода, поэтому мной была предложена следующая реализация:
  1. При инициализации создается список доступных серверов и сохраняется длина этого списка. Создается глобальный счетчик с типом данных AtomicInteger и начальным значением 0
  2. При запросе адреса сервера счетчик увеличивается на 1. Если получившееся значение превышает длину списка, то обнуляем счетчик. Значение этого счетчика используем, как индекс в списке.


Теперь непосредственно получившийся код (спасибо за совет relgames):

    private final AtomicInteger position = new AtomicInteger(0);
    private volatile int listSize;
    ...
    public synchronized void init(List<Entity> objects) {
            ...
            listSize = objectList.size();
            ...
        }
    }

    public Entity getNext() {
         return objectList.get(getNextPosition());
    }

    public final int getNextPosition() {
        for (;;) {
            int current = position.get();
            int next = current + 1;
            if(next >= listSize){
                next = 0;
            }
            if (position.compareAndSet(current, next))
                return current;
        }
    }



Для проверки работоспособности данной реализации под нагрузкой была написана небольшая программка.
Методика тестирования заключалась в том, что выполнялось 1 000 000 запросов на получения адреса сервера при разном количестве потоков (от 1 до 991) и измерялось среднее время получения адреса.

Результаты представлены в виде графика и их можно посмотреть тут.
Исходники для экспериментов тут.
Данные, на основе которых построены графики, тут.

Спасибо за внимание.

P.S. Предложенный вариант реализации работает одинаково стабильно как при работе в однопоточной системе, так и при работе в многопоточной системе, что хорошо видно на графике. Это и есть основное преимущество данной реализации.

UPD:
Старый график тут. Исследования тогда проводились на более медленном компе.
Tags:javaround-robinthread savebalancer
Hubs: Java
0
5.1k 12
Comments 16