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

Темы, не касающиеся фреймворка, но относящиеся к программированию в целом.
Аватара пользователя
solo
Сообщения: 320
Зарегистрирован: 2013.03.08, 19:59
Откуда: Ukraine, VINNITSA

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

Сообщение solo »

Сегодня проходил тест на работу.

Древовидные комментарии - нужна большая скорость выборки из БД и не важна скорость записи. Варианты решения? уровень комментариев не ограничен.
Идеальное решение задачи, при кэшировании запроса выдает на мелком сервере около 3-4 тыс страниц в секунду при базе в 1 млн коментариев и по 1 тыс каментов в статье.
Аватара пользователя
MaxHero
Сообщения: 144
Зарегистрирован: 2011.09.12, 04:34
Откуда: Украина, Киев

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

Сообщение MaxHero »

И какой же ответ устраивает работодателя? ИМХО в любом случае будет выборка с фильтром по topic_id/post_id , соответственно для него необходимо построить индекс. Ну а скорость выборки зависит от типа движка, от того, dynamic или static row table, от кол-ва строк в таблице. При большом кол-ве строк в таблице увеличить скорость выборки поможет шардинг (несколько таблиц одинаковой структуры, где, например, comments1 будет содержать комменты для topic_id/post_id от 1 до 1000, comments2 - от 1001 до 2000 и т.д.)
Аватара пользователя
solo
Сообщения: 320
Зарегистрирован: 2013.03.08, 19:59
Откуда: Ukraine, VINNITSA

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

Сообщение solo »

Я еще немного подержу интригу может еще будут ответы.
Zeen
Сообщения: 44
Зарегистрирован: 2011.06.28, 11:50

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

Сообщение Zeen »

Шардинг таблицы комментов? зачем? Интересны вкладки
Аватара пользователя
solo
Сообщения: 320
Зарегистрирован: 2013.03.08, 19:59
Откуда: Ukraine, VINNITSA

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

Сообщение solo »

Работодатель уточнил: средний коментарий обычно не более 200 знаков, что в utf-8 + служебка = байтов 500. т.е. 1 млн комментариев - это 500 мегабайт всего - вся таблица поместится в кэш
"Мелкий сервер" Core™ Quad-Core i7-2600 processor, 32 GB DDR 3 RAM
Аватара пользователя
MaxHero
Сообщения: 144
Зарегистрирован: 2011.09.12, 04:34
Откуда: Украина, Киев

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

Сообщение MaxHero »

Еще в голову приходит вариант 2ух таблиц с одинаковой структурой: одна на движке memory, вторая - innoDB. Пишем в innoDB, читаем из memory. Пишем триггеры для innoDB таблицы, которые будут проводить аналогичные запросы (insert, update, delete) в таблицу memory (тем самым будем уверены, что данные всегда записаны на диск, но будет медленно). Ну и при рестарте сервера БД необходимо заново инициализировать memory таблицу
rak
Сообщения: 2181
Зарегистрирован: 2010.11.02, 23:40
Контактная информация:

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

Сообщение rak »

я бы хранил(точнее и так везде эту схему использую, где нужны деревья) вот так http://www.slideshare.net/billkarwin/sq ... ke-back/68
Zeen
Сообщения: 44
Зарегистрирован: 2011.06.28, 11:50

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

Сообщение Zeen »

"Еще в голову приходит вариант 2ух таблиц с одинаковой структурой:"
зачем? если мемори таблица помещается в памяти, то и inno|myisam поместится и не будет разницы между ними.
Zeen
Сообщения: 44
Зарегистрирован: 2011.06.28, 11:50

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

Сообщение Zeen »

нестедсеты/AL и т.п. кто нить сравнивал по скорости? http://habrahabr.ru/post/47280/ и http://habrahabr.ru/post/46659/ пища для размышлений

NESTED SETS: Провел небольшой тест по производительности, вставка в пустое дерево по 1000 записей:
0001-1000 — 3.5275 сек.
1001-2000 — 6.2751 сек.
2001-3000 — 8.4156 сек.
3001-4000 — 9.9535 сек.
4001-5000 — 14.0197 сек.
Тест проводился на хостинге (nichost.ru тариф 301), собственная база MySQL, адаптер БД Zend_DB с включенным профилировщиком.
p0rsche
Сообщения: 192
Зарегистрирован: 2012.01.18, 08:28
Контактная информация:

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

Сообщение p0rsche »

Использовать mysql, таблица в MyISAM, R-tree индексы (SPATIAL) и работать с геометрией. Нетривиально. Интересно.
Запросы на несколько миллионов записей ложатся в отметки до 600мс.
Прекрасная статья на тему
Последний раз редактировалось p0rsche 2013.04.06, 21:10, всего редактировалось 1 раз.
Zeen
Сообщения: 44
Зарегистрирован: 2011.06.28, 11:50

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

Сообщение Zeen »

Да и простых индексов хватит
Если у каммента кроме parent пишем id статьи/обзора или что мы там комментируем, то весь запрос выходит как select * from 'comment' where id_owner=номерстатьи ну и индекс по id_owner
Аватара пользователя
solo
Сообщения: 320
Зарегистрирован: 2013.03.08, 19:59
Откуда: Ukraine, VINNITSA

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

Сообщение solo »

Zeen писал(а):нестедсеты/AL и т.п. кто нить сравнивал по скорости?.
Скорость записи в условии пофиг. Хотя потом мне сказали что нужно представить себе что еще и комментов может быть примерно в это число запросов.
Zeen
Сообщения: 44
Зарегистрирован: 2011.06.28, 11:50

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

Сообщение Zeen »

Взять к примеру Хабр. В ряде статей комментариев по 1000 и они все в 7-10 уровней уже.
Проблем с показом страниц у них нет. Общее число комментариев уже с пару сотен млн.
Аватара пользователя
MaxHero
Сообщения: 144
Зарегистрирован: 2011.09.12, 04:34
Откуда: Украина, Киев

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

Сообщение 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
на том же железе
Последний раз редактировалось MaxHero 2013.04.07, 00:36, всего редактировалось 3 раза.
Аватара пользователя
r3verser
Сообщения: 195
Зарегистрирован: 2012.04.01, 17:29
Откуда: Киев

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

Сообщение 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
Сообщения: 144
Зарегистрирован: 2011.09.12, 04:34
Откуда: Украина, Киев

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

Сообщение MaxHero »

Здесь уже вообще разницы нет как и в чем хранить дерево, тут вопрос про кэширование. Например nginx + memcached.
Насколько я понимаю, имеется ввиду кэш самого SQL-сервера. Т.е. сперва "прогреваем" выборки, а потом меряем производительность
Zeen
Сообщения: 44
Зарегистрирован: 2011.06.28, 11:50

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

Сообщение Zeen »

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

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

select * from 'comment' where id_owner=номерстатьи
и получить массив со всеми комментариями дерева и собрать его в древовидный массив, Вы городите тригеры (не всегда возможно использовать на вирт хостах), монго (на вирт хост тоже не поставить).

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

Будьте проще. Все гениальное - просто.
Аватара пользователя
MaxHero
Сообщения: 144
Зарегистрирован: 2011.09.12, 04:34
Откуда: Украина, Киев

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

Сообщение MaxHero »

Zeen писал(а):Ребят, задача простая как 5 копеек. Это еще в условии нет того, что у нас у каммента есть id_user и надо в дереве заполнять ФИО/логин пользователя вместо id. :)
Ага, в топике собрались одни junior'ы, которым нечего делать, кроме как изобретать велосипеды. Топикстартер озвучил входные данные (кол-во строк в таблице) и выходные (кол-во запросов, способных обработать сервером за секунду времени). Ради интереса затестите у себя "простое как 5 копеек решение задачи" и выложите сюда результаты. После - продолжим дискуссию.
Zeen
Сообщения: 44
Зарегистрирован: 2011.06.28, 11:50

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

Сообщение 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
Сообщения: 144
Зарегистрирован: 2011.09.12, 04:34
Откуда: Украина, Киев

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

Сообщение MaxHero »

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

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

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