Сегодня проходил тест на работу. Задача на мышление

[Zeen]

Да и простых индексов хватит
Если у каммента кроме parent пишем id статьи/обзора или что мы там комментируем, то весь запрос выходит как select * from 'comment' where id_owner=номерстатьи ну и индекс по id_owner

[solo]

нестедсеты/AL и т.п. кто нить сравнивал по скорости?.

Скорость записи в условии пофиг. Хотя потом мне сказали что нужно представить себе что еще и комментов может быть примерно в это число запросов.

[Zeen]

Взять к примеру Хабр. В ряде статей комментариев по 1000 и они все в 7-10 уровней уже.
Проблем с показом страниц у них нет. Общее число комментариев уже с пару сотен млн.

[MaxHero]

Решение в лоб: создание таблицы типа memory со структурой

Код: Выделить всё

id => pk,
post_id => INT NOT NULL,
parent_id => INT DEFAULT NULL,
text => CHAR(255)

+ hash индекс на поле post_id
заполненной на 1.000.000 строк по 1.000 строк на каждый post_id дает 2.4 - 2.6с. на 1000 запросов

Код: Выделить всё

SELECT * FROM comments WHERE post_id=SOME_RANDOM_ID

к БД на моей конфигурации железа.

Если пораскинуть мозгами, то можно реализовать следующее:

Код: Выделить всё

post(
    id => pk,
    comments => LONG TEXT,
)

comments(
    id => pk,
    post_id => INT NOT NULL,
    parent_id => INT DEFAULT NULL,
    text => TEXT,
) 

И навесить приблизительно следующий триггер на comment.afterInsert:

Код: Выделить всё

BEGIN
  UPDATE post
SET
  comments = concat(comments, "{'id':", new.id, ",'parent_id':", new.parent_id, ",'text':'", new.`text`, "'},")
WHERE
  id = new.post_id;
END

Т.е. делаем денормализацию данных и храним комментарии вместе с постом в сериализованном виде, а на стороне web-приложения проводим десериализацию при select'е.

Правда, триггеры comment.afterUpdate и comment.afterDelete уже будут не столь тривиальными, но все же и эта задача решаема.

Понятно, что скорость добавления/обновления/удаления комментариев будет ниже, зато скорость выборки очень мала и составляет 0.25 - 0.30с на 1000 запросов

Код: Выделить всё

SELECT * FROM post WHERE id=SOME_RANDOM_ID

на том же железе

[r3verser]

как насчет nosql? например mongodb

Код: Выделить всё

{
    _id: ObjectId(...),
    discussion_id: ObjectId(...),
    parent_id: ObjectId(...),
    slug: '34db/8bda'
    full_slug: '2012.02.08.12.21.08:34db/2012.02.09.22.19.16:8bda',
    posted: ISODateTime(...),
    author: {
              id: ObjectId(...),
              name: 'Rick'
             },
    text: 'This is so bogus ... '
}

http://docs.mongodb.org/manual/use-case ... -comments/

И еще

Идеальное решение задачи, при кэшировании запроса выдает на мелком сервере около 3-4 тыс страниц в секунду при базе в 1 млн коментариев и по 1 тыс каментов в статье.

Здесь уже вообще разницы нет как и в чем хранить дерево, тут вопрос про кэширование. Например nginx + memcached.

[MaxHero]

Здесь уже вообще разницы нет как и в чем хранить дерево, тут вопрос про кэширование. Например nginx + memcached.

Насколько я понимаю, имеется ввиду кэш самого SQL-сервера. Т.е. сперва "прогреваем" выборки, а потом меряем производительность

[Zeen]

Что-то всех понесло не туда.
Вместо того, что бы использовать

Код: Выделить всё

select * from 'comment' where id_owner=номерстатьи

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

Ребят, задача простая как 5 копеек. Это еще в условии нет того, что у нас у каммента есть id_user и надо в дереве заполнять ФИО/логин пользователя вместо id.

Будьте проще. Все гениальное - просто.

[MaxHero]

Ребят, задача простая как 5 копеек. Это еще в условии нет того, что у нас у каммента есть id_user и надо в дереве заполнять ФИО/логин пользователя вместо id.

Ага, в топике собрались одни junior'ы, которым нечего делать, кроме как изобретать велосипеды. Топикстартер озвучил входные данные (кол-во строк в таблице) и выходные (кол-во запросов, способных обработать сервером за секунду времени). Ради интереса затестите у себя "простое как 5 копеек решение задачи" и выложите сюда результаты. После - продолжим дискуссию.

[Zeen]

Тестили. ~ 3200 запросов в секунду на серваке вышеприведенном при ответе в json.

Еще раз продублирую входные данные:
1 млн записей, средний размер которой по 500 байт (500 мегабайт в памяти на всю таблицу)
Важность быстрой выборки и быстрого ответа.

Все кто предложил с мемори таблицами работать - в топку, таблица и так уже в память легко влезла.
Нестед сеты|MP|AL - классические решения для студентов, все они были придуманы давно и у каждого есть свои плюсы и минусы. Для комментариев ни одного плюса нет.
SQL достаточный тормоз, когда дело касается JOIN. Напомню, что i5|i7 какой нить имеет пропускную способность копирования с помощью использования памяти DDR3 частотой 1066 МГц в трёхканальном режиме, в 12,0 ГБ/с. Часть Join делаться будут долго тупо по тому, что sql по таблице будет делать выборки чуть ли не фулсканом (грубо говоря). Т.е. 12 Гб/500Мб - уже 24 - число раз, которое sql может по базе пробежаться фулсканом (про блокировку страниц памяти я умолчу, так как на деле не фулскан полный будет, но и блокировки сделают свое дело + наполнение кэша 3/2 уровня идет избыточными блоками). Нестедсет даст максимум 100 запросов в секунду. AL чуть быстрее. MP как и AL если только руки не из ног и like ни кто использовать не будет в "велосипеде".

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

Код: Выделить всё

$listIdParent = array(
  1 => array('parent' => 0),
  2 => array('parent' => 1),
  3 => array('parent' => 1),
  4 => array('parent' => 2),
  5 => array('parent' => 4)
); 

исходный массив полученный от sql

Код: Выделить всё

 /**
 * Построение дерева из списка ID-Parent.
 * 
 * @param array Исходный список.
 * @return array Дерево.
 */
function buildTree(array $listIdParent) {
  // Подготовка ID корневого узла.
  $rootId = 0;
  
  // Обход списка и обработка узлов.
  foreach ($listIdParent as $id => $node) {
    if ($node['parent']) {
      // Сохранение в родительском узле ссылки на текущий.
      $listIdParent[$node['parent']]['sub'][$id] =& $listIdParent[$id];
    } else {
      // Сохранение ссылки на корневой элемент.
      $rootId = $id;
    }
  }

  
  // Возврат корневого узла, содержащего всё построенное дерево.
  return array($rootId => $listIdParent[$rootId]);
}
 

Получили

Код: Выделить всё

 array(
  1 => array(
    'parent' => 0,
    'sub' => array(
      2 => array(
        'parent' => 1,
        'sub' => array(
          4 => array(
            'parent' => 2,
            'sub' => array(
              5 => array('parent' => 4)
            )
          )
        )
      ),
      3 => array(
        'parent' => 1
      )
    )
  )
) 

Это дерево можно присунуть в мемкэш/редис/тарантул, главное не забыть обновить при вставке нового комментария.
nginx дерево может выбрать напрямую из мемкэша/редиса наш json

[MaxHero]

Касательно memory таблицы - было мое предложение. Но не из-за того, что таблица "ложится" в память, а потому что движок memory таблиц поддерживает hash индексы (немного быстрее, чем btree). Но даже данный подход достаточно медленный (я привел выше мои замеры производительности) и кроме этого имеет ограничение на строку текста комментария, т.к. memory не поддерживает BLOB и TEXT.

Касательно "Нестед сеты|MP|AL" - тут солидарен с Вами, считаю, что для задачи древовидных комментариев данные решения излишни.

Очень странно, что у Вас производительность столь высока. Я тестировал на core i3-2100 8Gb 1333 DDR3 и мои цифры очень далеки от Ваших. Есть еще другой более мощный конфиг, проверю на нем чуть позже.

[Zeen]

У вас на компьютере во что упирается? ИМХО не в проц, а в память или IO общий

[solo]

У меня проц на 6 ядер по 3.9ГГц, ОЗУ 16Гб. Включен APC все логи отключены.

Код: Выделить всё

public function actionIndex()
{
    echo 'hello';
}

ab -n 10000 -c 5 http://yii.loc/
Requests per second: 1644.31 [#/sec] (mean)

ab -n 10000 -c 100 http://yii.loc/
Requests per second: 2063.53 [#/sec] (mean)

При тесте надеюсь понятно все ядра 100%.

Здесь нужно обходиться без фреймворка уже.
Кэшированые комменты отдавать ajax-ом.
Можно еще отдавать например по 20 комментов.
И не нужно полагаться на кэш мускула, а кэшировать тем же APC.
Вот что я думаю по этому поводу.

[r3verser]

Что-то всех понесло не туда.
Вместо того, что бы использовать

Код: Выделить всё

select * from 'comment' where id_owner=номерстатьи

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

В условиях задачи нету ни слова про виртуальный хост или mysql only. Мне нравиться монгодб.

Ребят, задача простая как 5 копеек. Это еще в условии нет того, что у нас у каммента есть id_user и надо в дереве заполнять ФИО/логин пользователя вместо id.

Здесь вообще никакой проблемы нету, в приведенной мной схеме для монго, уже храниться имя пользователя.

[Zeen]

в приведенной мной схеме для монго, уже храниться имя пользователя.

Пользователь переименуется и лажа выйдет или надо по монге пробегаться и менять.

Хранение ключа "id пользователя" - "ФИО" удобно делать в мемкэше/редиске и пользоваться мультигетом с отсевом тех, кого нет в кэше (стух или что нить еще) и обращение к БД уже с оставшимися.

[Vasko]

Если не важна скорость записи, а только скорость получения и комментарии древовидные, то можно сделать красно-черное дерево , слышал где-то, что вроде на Хабре так сделано. http://ru.wikipedia.org/wiki/%CA%F0%E0% ... 0%E5%E2%EE