Алгоритм распределения данных в кластере серверов в dCache

В продолжение статьи о dCache расскажу о некоторых деталях внутренней реализации.

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



Обычно, данные записанные вместе, вместе и будут прочитаны. Будь то фотографии с последнего отпуска или последние результаты научного эксперимента. Этот факт заставляет нас разбрасывать входящие данные по как можно большому количеству узлов, что-бы избежать скопления клиентов на одном из серверов. Легко решаемая задача, если все узлы имеют одинаковый размер и одинаковое свободное дисковое пространство. Но это редкость в реальных условиях. Новые и, с большим объёмом, сервера подсоединяются когда свободное место уже на грани.

В dCache это решено при помощи двух механизмов: взвешенное произвольное распределение с учётом свободного места (weighted random distribution) при записи и перераспределение данных (rebalancing) при добавлении новых узлов.

И так, как работает взвешенное произвольное распределение с учётом свободного места:

• каждому узлу подсчитывается вес, который равен объёму свободного пространства на узле делённому на общее свободное место в системе:
  weight = FreeN / FreeTotal
• произвольно выбирается один из узлов, причём вероятность выбора узла прямо пропорциональна его весу

В коде это выглядит примерно так:

public Pool selectWritePool(Pool[] pools)
{
    double[] weights = new double[pools.length];
    long totalFree = 0;
    for (Pool pool:pools) {
      totalFree += pool.getFree();
    }

    int i = 0;
    for (Pool pool:pools) {
      weights[i] = (double) pool.getFree() / totalFree;
      i++;
    }
    return pools[i];
}

private final Random rand = new Random();
public static int weightetRandom(double[]weights, Random r)
{
    double selection = r.nextDouble();
    double total = 0;
    int i = 0;
    for (i = 0; (i < weights.length) && (total <= selection); i++) {
      total += weights[i];
    }
    return i - 1;
}

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

Как было сказано выше, внутренняя команда re-balance использует этот-же алгоритм, что-бы выровнять загрузку серверов. Загрузка рассчитывается отношением свободного места к общему:
load = FreeN/TotalN

Данный алгоритм хорошо зарекомендовал себя в боевых условиях.