Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Начинаем трудиться с графовой базой данных Neo4j

Anna | 29.05.2014 | нет комментариев

В нашем плане появилась дальнейшая задача — есть база с огромным числом товаров, на ярусе сотен тысяч. У всякого товара есть сотни динамически создаваемых колляций. Нужно обеспечить стремительную фильтрацию по товарам по комплекту разных колляций. Время образования результата должно быть не больше 0.3 секунды, необходимо поддерживать трудную логику в жанре.

(характеристика1 = true AND (характеристика2 < 100)) OR (характеристика1 = false AND (характеристика3 > 17)) ... дальше традиционно мешанина из ANDOR

Классический пример сходственного функционала — hotline.ua/computer/myshi-klaviatury/

Пример функционала

У нас все реализовано в рамках MySQL Symfony2/Doctrine, скорость неудовлетворительная — результаты формируются в течении 1-10 секунд. Мои попытки оптимизировать все это хозяйство — под катом.

Терминология задачи по фильтрации товаров (в упрощенном виде)

 

  • колляция — определенное качество товара. Скажем, объем памяти.
  • образец товара — комплект всех допустимых колляций однотипных товаров, скажем — перечень допустимых колляций компьютерных мышек. При добавлении нового товара менеджер может выбирать колляции в рамках образца. Добавить новую колляцию для одного товара нереально — необходимо добавить колляцию в образец для этого товара. Единовременно эта колляция будет доступна для всех товаров, использующих данный образец
  • группа товаров — товары на основе одного образца. Скажем, компьютерные мышки. Фильтрация делается только для товаров из одной группы
  • критерий — логическое правило, которое состоит из комплекта формальных требований к колляциям товара. Скажем, «геймерская мышка» — это комплект требований к колляциям (размер не крохотный) AND (сенсор лазерный) AND (разрешение сенсора не менее 1500)
  • фильтр — группа критериев для однотипных товаров. В зависимости от критериев, они могут комбинироваться через AND либо OR

У hotline реализован больше продвинутый вариант — с подсказкой, сколько товаров останется позже активизации критерия. Скажем, если предпочесть фильтр «Bluetooth», то позже загрузки страницы вблизи фильтра «Тип сенсора мыши — оптический» будет цифра 17. Реально, для такой реализации необходимо не легко делать выборку по критериям, но и заранее для всякого оставшегося фильтра подсчитывать число товаров при его активизации.

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

Терминология Neo4j и графовых баз данных в целом.

 

  • graph databaseграфовая база данных — база данных построенная на графах — узлах и связях между ними
  • Cypher — язык для написания запросов к базе данных Neo4j (приблизительно, как SQL в MYSQL)
  • nodeнода — объект в базе данных, узел графа. число узлов ограниченно 2 в степени 35 ~ 34 биллиона
  • node labelметка ноды — применяется как воображаемый «тип ноды». Скажем, ноды типа movie могут быть связанны с нодами типа actor. Метки нод — регистрозависимые, причем Cypher не выдает ошибок, если набрать не в том регистре наименование.
  • relationсвязь — связь между двумя нодами, ребро графа. число связей ограниченно 2 в степени 35 ~ 34 биллиона
  • relation identirfierqvmk!a rel=”nofollow” href=”http://stackoverflow.com/questions/20533781/neo4j-browser-paste-multiple-commands”>Здесь говорят, что ветхий заказчик это может, но я не обнаружил такой вероятности. Следственно, необходимо копировать по 1 строке.

    Дозволено исполнить создание множества нод со связями одной командой, необходимо давать различные имена нодам, связям дозволено не давать имя

    CREATE (w1:Ware{wareId:1})-[:SUIT]->(c1:Criteria{criteriaId:1}), (w2:Ware{wareId:2})-[:SUIT]->(c2:Criteria{criteriaId:2}),  (w3:Ware{wareId:3})-[:SUIT]->(c3:Criteria{criteriaId:3}), (w4:Ware{wareId:4})-[:SUIT]->(c1), (w5:Ware{wareId:5})-[:SUIT]->(c1),  (w4)-[:SUIT]->(c2), (w5)-[:SUIT]->(c3);
    


    Получится такая конструкция. Если у вас выглядит менее ясно — дозволено переставить мышкой ноды.

    Тестовая структура

    Промежуточные тесты скорости Neo4j


    Пришло время протестировать скорость заполнения базы и примитивных выборок из огромный базой.

    Для этого клонируем neo4jphp

    git clone https://github.com/jadell/neo4jphp.git


    Базовое изложение этой библиотеки есть в этом посте, следственно я сразу выложу код для заполнения тестовой базы еxamples/test_fill_1.php

    <?php
    use EverymanNeo4jClient,
    	EverymanNeo4jIndexNodeIndex,
    	EverymanNeo4jRelationship,
    	EverymanNeo4jNode,
    	EverymanNeo4jCypher;
    
    require_once 'example_bootstrap.php';
    
    $neoClient = new Client();
    $neoWares = new NodeIndex($neoClient, 'Ware');
    $neoCriterias = new NodeIndex($neoClient, 'Criteria');
    $neoWareLabel = $neoClient->makeLabel('Ware');
    $neoCriteriaLabel = $neoClient->makeLabel('Criteria');
    
    $wareTemplatesCount = 200;
    $criteriasCount = 500;
    $waresCount = 10000;
    $commitWares = 100;
    $minRelations = 200;
    $maxRelations = 400;
    
    $time = time();
    for($wareTemplateId = 0;$wareTemplateId<$wareTemplatesCount;$wareTemplateId  ) {
    	$neoClient->startBatch();
    	print $wareTemplateId." (".$criteriasCount." criterias, ".$waresCount." wares with rand(".$minRelations.",".$maxRelations.") ...";
    	$criterias = array();
    	for($criteriaId = 1;$criteriaId <=$criteriasCount;$criteriaId  ) {
    		$c = $neoClient->makeNode()->setProperty('criteriaId', $wareTemplateId * $criteriasCount   $criteriaId)->save(); // ->addLabels(array($neoCriteriaLabel)) - не работает с commitBatch
    		$neoCriterias->add($c, 'criteriaId', $wareTemplateId * $wareTemplatesCount   $criteriaId); // ->save() такого способа нет
    		$criterias[] = $c;
    	}
    
    	for($wareId = 1;$wareId <=$waresCount;$wareId  ) {
    		$w = $neoClient->makeNode()->setProperty('wareId', $wareTemplateId * $waresCount   $wareId)->save(); // ->addLabels(array($neoWareLabel)) - не работает с commitBatch
    		$neoWares->add($c, 'wareId', $wareTemplateId * $waresCount   $criteriaId);
    
    		for($i = 1;$i<=rand($minRelations,$maxRelations);$i  ) {
    			$w->relateTo($criterias[array_rand($criterias)], "SUIT")->save();
    		}
    		if(($wareId % $commitWares) == 0) {
    			$neoClient->commitBatch();
    		        print " [commit ".$commitWares." ".(time() - $time)." sec]";
    			$time = time();
    			$neoClient->startBatch();
    		}
    	}
    	$neoClient->commitBatch();
            print " done in ".(time() - $time)." secondsn";
    	$time = time();
    
    }
    

    Скрипт заполнения базы я оставил на ночь. Приблизительно через 4 часа скрипт перестал добавлять данные и сервис Neo4j начал грузить сервер на 100%. Утром по результату работы было вставлено 78300 товаров из 8 категорий товаров.
    Итоги тестового заполнения базы — приблизительно 20 товаров в секунду с 200-400 связями. Не дюже высокий итог — Mysql и Cassandra выдавали около 10-20 тысяч вставок в секунду (10 полей, 1 primary index, 1 индекс). Но скорость вставки для нас не критична — мы можем обновлять граф данных в фоновом режиме позже редактирования товара. А вот скорость выборки данных — критична.

    Размер тестовой базы данных на диске — 1781 мегабайт. В ней храниться 78300 товаров, 4000 критериев, 15660000-31320000 связей. Всеобщее число объектов (нодов и связей) менее 32 миллионов — в среднем по 55 байт на сущность. Многовато, как по мне, но основное требование все же скорость выборок, а не размер базы.

    Первая попытка протестировать скорость выборки провалилась — сервер Neo4j вновь «ушел» в режим 100% загрузки процессора и за несколько минут так и не выдал результат на запрос.

    MATCH (c {criteriaId: 1})<--(a)-->(b {criteriaId: 3}) RETURN a.wareId;


    Дабы двигаться дальше необходимо разобраться, как оптимизировать запрос в Neo4j. Сначала я хотел ограничить стартовый комплект нод в выборке с поддержкой инструкции START

    START n=node:nodeIndexName(key={value}) MATCH (c)<--(a)-->(b) RETURN a.wareId;
    


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

    :schema


    Добавить индексы дозволено командой

    CREATE INDEX ON :Criteria(criteriaId)


    Неповторимый индекс дозволено сделать командой

    CREATE CONSTRAINT ON (n:Criteria) ASSERT n.criteriaId IS UNIQUE;


    Индексы, добавленные командами выше, невозможно применять в START директиве. Здесьутверждают, что их дозволено применять только в where

    The indexes created via Cypher are called Schema indexes, and are not to be used in the START clause. The START clause index lookups are reserved for the legacy indexes that you create via autoindexing or through the non-Cypher APIs.

    In order to use the :user index you’ve created, you can do this:

    match n:user
    where n.name=«aapo»
    return n;


    Если я верно осознал документацию, дозволено отважно применять WHERE взамен START

    START is optional. If you do not specify explicit starting points, Cypher will try and infer starting points from your query. This is done based on node labels and predicates contained in your query. See Chapter 14, Schema for more information. In general, the START clause is only really needed when using legacy indexes.


    Так родился 1-й рабочий запрос

    MATCH (a:Ware)-->(c1:Criteria {criteriaId: 3}),(c2:Criteria {criteriaId: 1}),(c3:Criteria {criteriaId: 2}) WHERE (a)-->(c2) AND (a)-->(c3) RETURN a;
    


    В нашей тестовой базе индексов не найдено, следственно мы сотворим еще одну базу для теста иным методом. Вероятности сделать самостоятельные комплекты данных (аналог базы данных в MySQL) в Neo4j я не обнаружил. Следственно для тестирования я легко менял путь к хранилищу данных в настройках Neo4j Community (Database location)

    Use в Neo4j делается сменой пути к хранилищу

    Внимательные читатели допустимо нашли пару комментариев в коде test_fill_1.php, а именно

    		$c = $neoClient->makeNode()->setProperty('criteriaId', $wareTemplateId * $criteriasCount   $criteriaId)->save(); // ->addLabels(array($neoCriteriaLabel)) - не работает с commitBatch
    		$neoCriterias->add($c, 'criteriaId', $wareTemplateId * $wareTemplatesCount   $criteriaId); // ->save() такого способа нет
    


    В batch режиме в Neo4jphp у меня не получилось добавить метки к нодам, а индексы отчего то не сохранились. Рассматривая, что Cypher перестал для меня быть китайской грамотой, я решил заполнять базу хардкорно — на чистом Cypher. Так получился test_fill_2.php

    <?php
    use EverymanNeo4jClient,
    	EverymanNeo4jIndexNodeIndex,
    	EverymanNeo4jRelationship,
    	EverymanNeo4jNode,
    	EverymanNeo4jCypher;
    
    require_once 'example_bootstrap.php';
    
    $neoClient = new Client();
    
    $wareTemplatesCount = 100;
    $criteriasCount = 50;
    $waresCount = 250;
    $minRelations = 20;
    $maxRelations = 40;
    
    if($maxRelations > $criteriasCount) {
        throw new Exception("maxRelations[".$maxRelations."] should be bigger, that criteriasCount[".$criteriasCount."]");
    
    }
    $query = new CypherQuery($neoClient, "CREATE CONSTRAINT ON (n:Criteria) ASSERT n.criteriaId IS UNIQUE;", array());
    $result = $query->getResultSet();
    $query = new CypherQuery($neoClient, "CREATE CONSTRAINT ON (n:Ware) ASSERT n.wareId IS UNIQUE;", array());
    $result = $query->getResultSet();
    
    for($wareTemplateId = 0;$wareTemplateId<$wareTemplatesCount;$wareTemplateId  ) {
        $time = time();
    	$queryTemplate = "CREATE ";
    	print $wareTemplateId." (".$criteriasCount." criterias, ".$waresCount." wares with rand(".$minRelations.",".$maxRelations.") ...";
    	$criterias = array();
    	for($criteriaId = 1;$criteriaId <=$criteriasCount;$criteriaId  ) {
    		$cId = $criteriaId   $criteriasCount*$wareTemplateId;
    		$queryTemplate .= "(c".$cId.":Criteria{criteriaId:".$cId."}), ";
    		$criterias[] = $cId;
    	}
    
    	for($wareId = 1;$wareId <=$waresCount;$wareId  ) {
    		$wId = $wareId   $waresCount*$wareTemplateId;
    		$queryTemplate .= "(w".$wId.":Ware{wareId:".$wId."}), ";
    
    		$possibleLinks = array_merge(array(), $criterias); // clone $criterias не работает
    		for($i = 1;$i<=rand($minRelations,$maxRelations);$i  ) {
    			$linkId = $possibleLinks[array_rand($possibleLinks)];
    			unset($possibleLinks[$linkId]);
    			$queryTemplate .= "w".$wId."-[:SUIT]->c".$linkId.", ";
    		}
    	}
        $queryTemplate = substr($queryTemplate,0,-2); // удаляем конечный ", "
    
        $build = time();
    	$query = new CypherQuery($neoClient, $queryTemplate, array()); // $queryTemplate будет в районе 42 мегабайт для 10000 товаров, 500 критериев, 200-400 связей между товаром-критерием
    	$result = $query->getResultSet();
            print " Query build in ".($build - $time)." seconds, executed in ".(time() - $build)." secondsn";
    //	die();
    }
    


    Скорость добавления данных оказалась предсказуемо большей, чем в первом варианте.
    Тестовый скрипт с добавлением 30000 нодов и 500000 — 1000000 связей на cypher отработал за 140 секунд, база заняла на диске 62 мегабайта. При попытке запустить скрипт c $waresCount=1000 (не говоря теснее о 10000 товаров) я получил ошибку «Stack overflow error». Я переписал скрипт c применением.

    MATCH (a {wareId: 1}),
          (b {criteriaId: 2})
    MERGE (a)-[r:SUIT]->(b)
    


    Это привело к катастрофическому падению скорости работы, преобразованный скрипт работал приблизительно около часа. Я решил протестировать скорость выборки по нескольким критериям и возвратиться к вопросу стремительной вставки данных позднее.

    <?php
    use EverymanNeo4jClient,
    	EverymanNeo4jIndexNodeIndex,
    	EverymanNeo4jRelationship,
    	EverymanNeo4jNode,
    	EverymanNeo4jCypher;
    
    require_once 'example_bootstrap.php';
    
    $neoClient = new Client();
    $time = microtime();
    $query = new CypherQuery($neoClient, "MATCH (a:Ware)-->(b:Criteria {criteriaId: 3}),(c:Criteria {criteriaId: 1}),(c2:Criteria {criteriaId: 2}) WHERE (a)-->(c) AND (a)-->(c2) RETURN a;", array());
    $result = $query->getResultSet();
    print "Done in ".(microtime() - $time)." secondsn";
    


    Скрипт выше отработал за 0.02 секунды. В целом — это абсолютно терпимо, но задача как стремительно сберегать огромное число связей между нодами при апдейте свойств товара — осталась.

    Альтернативное решение


    Я решил «для чистки совести» опробовать MySQL в качестве хранилища. Связи между нодами будут храниться в отдельной таблице без дополнительной информации.

    CREATE TABLE IF NOT EXISTS `edges` (
      `criteriaId` int(11) NOT NULL,
      `wareId` int(11) NOT NULL,
      UNIQUE KEY `criteriaId` (`criteriaId`,`wareId`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
    


    Тестовый скрипт для заполнения базы ниже

    <?php
    mysql_connect("localhost", "root", "");
    mysql_select_db("test_nodes");
    
    $wareTemplatesCount = 100;
    $criteriasCount = 50;
    $waresCount = 250;
    $minRelations = 20;
    $maxRelations = 40;
    
    $time = time();
    for($wareTemplateId = 0;$wareTemplateId<$wareTemplatesCount;$wareTemplateId  ) {
    	$criterias = array();
    	for($criteriaId = 1;$criteriaId <=$criteriasCount;$criteriaId  ) {
    		$criterias[] = $wareTemplateId * $criteriasCount   $criteriaId;
    	}
    
    	for($wareId = 1;$wareId <=$waresCount;$wareId  ) {
            $edges = array();
    		$wId = $wareTemplateId * $waresCount   $wareId;
            $links = array_rand($criterias,rand($minRelations,$maxRelations));
    		foreach($links as $linkId) {
    			$edges[] = "(".$criterias[$linkId].",".$wareId.")";
    		}
    		mysql_query("INSERT INTO edges VALUES ".implode(",",$edges));
    	}
    	print ".";
    }
    print " [added ".$wareTemplatesCount." templates in ".(time() - $time)." sec]";
    $time = time();
    
    


    Заполнение базы заняло 12 секунд. Размер таблицы — 37 мегабайт. Поиск по 2 критериям занимает 0.0007 секунд

    SELECT e1.wareId
    FROM  `edges` AS e1
    JOIN edges AS e2 ON e1.wareId = e2.wareId
    WHERE e1.criteriaId =17
    AND e2.criteriaId =31
    

    Еще один вариант


    Под mysql есть полновесное графовое хранилище данных — но я его не тестировал. Судя по документации, он значительно примитивнее Neo4j.

    Итоги


    Neo4j — дюже крутая штука. Запрос подобно «Предпочесть контакты пользователей, которые лайкнули киноактерам, которые снялись в фильмах, в которых звучали саунтдтреки, которые были написаны музыкантами, которым я поставил лайк» в Neo4j решается банально. Для SQL это значительно больше хлопотное занятие.

    Сопоставлять полновесную графовую базу с голой таблицей индексов в MySQL — некорректно, но в рамках решения моей задачи — применение Neo4j никаких плюсов не дало.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB