Статьи

О масштабировании графических баз данных

Декабрь 21, 2018

Вчера я говорил о графовых базах данных , обрисовывая их в общих чертах и ​​как они работают. Одна из интересных особенностей этой серии заключается в том, что во многих случаях я задаю вопрос (для себя), пытаюсь ответить на него, а затем иду и узнаю, что делают другие люди.

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

образ

Почему это важно?

Одно-машинное решение, очевидно, является барьером для масштабирования (и безопасности, но это еще одна проблема. В базе данных графа наличие отношений между узлом — это точка , которая делает сегментирование немного более сложным, потому что, если вы не сохраните весь граф на На одной машине вы вынуждены выполнять запросы через границы машин, и вы не можете хранить график на одной машине, по той простой причине, что маловероятно, что вы можете ограничить график настолько маленьким. Подумайте о последствиях Шесть градусов разделения для графовых баз данных, и станет понятно, в чем проблема. В реальных графах каждый связан со всеми.

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

new GraphDatabaseQuery
{
   SourceNode = ayende,
   MaxDepth = 3,
   RelationsToFollow = new[]{"As Known As", "Family", "Friend", "Romantic", "Ex"},
   Where = node => node.Location == ayende.Location,
   SearchOrder = SearchOrder.BreadthFirst
}.Execute();

Теперь нужно трогать 3 разных машины. Хуже того, на это влияет не количество машин, а распределение узлов графа по машинам в системе.

Потратив некоторое время на размышления, я пришел к выводу, что не могу представить какой-либо общий способ решения проблемы. О, я могу придумать несколько способов уменьшить проблему:

  • Пакетные кросс-машинные запросы, поэтому мы выполняем их только в конце каждого первого шага.
  • Хранение нескольких уровней ассоциаций (таким образом, «пользователи / ayende» будут хранить свои отношения, а также отношения «пользователи / ayende» и отношения «пользователи / arik»).

Наиболее вероятным решением будет ограничение глубины поиска узлов между машинами. Я думаю, что во многих случаях это приемлемо. Если мы установим ограничение глубины на 3, мы все равно сможем дать довольно хорошие ответы в разумные сроки. Но единственный способ добиться этого — хорошая поддержка пакетной обработки.

Алгоритм может выглядеть так:

public IEnumerable<Node> DistributedTraverse(Node sourceNode, int depth, string relationToFollow, Func<Node, filter> predicate)
{
    if(depth == 0) // feeling defensive
        yield break;
        
    var related = GetRelatedNodes(sourceNode.ShardName, relationToFollow, predicate);
    
    foreach(var result in related)
            yield return result;
        
    if(depth == 1) // don't even bother asking down the line
    {
        yield break;
    }
    
    foreach(var relationsByShard in related.GroupBy(x=>x.ShardName))
    {
        var shard = GetShardProxy(relationsByShard.Key);
        var results = shard.BatchedQuery(sourceNodes: relationsByShard.ToArray(), depth - 1,relationToFollow, predicate);
        foreach(var result in results)
            yield return result;
    }
}

Это дает нам максимальное количество (deep * number_of_machines_in_cluster) — глубинных удаленных вызовов: при глубине 3 и 3 машины в кластере у нас будет максимум 6 вызовов.

Не задумываясь над этой теорией, давайте рассмотрим, как реальные графические БД пытались решить эту проблему …

Neo4j (который, по-видимому, в значительной степени используется по умолчанию для графических БД) в настоящее время не справляется с этим, есть некоторые намеки на то, что они намерены предлагать репликацию на уровне кластера, но ничего о деталях проектирования или реализации. Neo4j предлагает подход «запись-мастер / чтение-ведомый» для масштабирования, что действительно хорошо, но даже этот подход ограничен в одной точке, и в этом посте я сосредоточусь на том, что происходит, когда вы выходите за рамки этой точки.

FlockDB (который используется в твиттере) включает в свои цели разработки: «горизонтальное масштабирование, включая репликацию». Тем не менее, FlockDB не пытается решить проблему, описанную выше, действительно, обход графика не является целью для него. FlockDB — это скорее поиск одного уровня отношений очень быстро, чем что-либо еще.

Таким образом, я считаю, что, хотя вы можете ограждать базу данных графов, она накладывает очень большие ограничения на тип запросов на обход графов, которые вы можете сделать. Теперь, просто чтобы дать вам представление, например, Neo4j, по-видимому, способен регулярно обрабатывать миллиарды узлов на отдельных машинах, поэтому вам может не потребоваться масштабирование выше этого.

 

 

 

 

34
Share: