kika: (Default)
[personal profile] kika
Имхо, довольно распространенная задача. Скажем у нас есть множество структур, описывающих некую жызненную ситуацию, скажем мониторинг хостов в сети. Структура содержит имя хоста, адрес, всякие прочие фактически иммутабельные параметры плюс некое количество изменяющихся параметров мониторинга, время пинга, скорость передачи данных, количество HTTP ошибок и теде и тепе. Структуры хранятся, допустим для простоты, в хеше по имени хоста. Все отлично, софтина работает, обмеряет хосты, апдейтит табличку с записями и жизнь прекрасна. Теперь нам надо сделать запросы снаружи - типа а покажи-ка мне список хостов, отсортированных по пингу. Допустим, хостов у нас ровно один газиллион, поэтому сортировать на каждый запрос накладно.
В традиционной культуре мы строим сбалансированные деревья с указателями на структуры (а в структурах указатели на деревья) и организуем синхронное плавание.
А как в функциональной культуре решается такая задача? Pointer trickery тут какбе немного недоступна.

Вкратце: есть структура -record(host, {host_id, speed = 0}). и из нее ETS таблица из одного газиллиона записей. Надо быстро отдавать список хостов, отсортированный по speed. Можно наверное положить это в Мнезию и понадеяться на ее ORDER BY, а если без Мнезии, ручками?

Date: 2009-12-21 06:52 am (UTC)
From: [identity profile] msh.livejournal.com
Эта задача называется "база данных". Сегодня ты хочешь сортировать по пингу, завтра тебе понадобится что-нибудь типа "все хосты в Гондурасе, где есть HTTP-сервер, отсортированные по пингу". Я в практически такой же задаче просто положил все в DBMS (можно и Mnesia, почему бы и нет)

Date: 2009-12-21 07:01 am (UTC)
From: [identity profile] kika.livejournal.com
Мне скорее для общего развития интересно, чем решить данную конкретную задачу.

Date: 2009-12-21 04:23 pm (UTC)
From: [identity profile] itman.livejournal.com
База данных медленно работает.

Date: 2009-12-21 07:10 pm (UTC)
From: [identity profile] 109.livejournal.com
сразу видно профессианала.

Date: 2009-12-21 08:38 pm (UTC)
From: [identity profile] kika.livejournal.com
"А Перл медленный, потому что интерпретируемый!"©

Date: 2009-12-21 09:43 pm (UTC)
From: [identity profile] itman.livejournal.com
А причем здесь Перл-то? База данных медленна по другим причинам.

Date: 2009-12-21 09:22 am (UTC)
From: [identity profile] lionet.livejournal.com
Организуем несколько деревьев. Одно — hostname → record(host). Другие — term → hostname. Джойны ручками, как и в ООП, разницы нет здесь в подходе к джойнам. В чём есть оптимизация сложности имплементации — это в возможности ленивого join'а тем же хаскелем, тобы не городить producers/consumers деревьев.

Date: 2009-12-21 09:29 am (UTC)
From: [identity profile] kika.livejournal.com
term→hostname - это в данном случае speed→hostname ? А как мне тогда проапдейтить дерево, когда я скорость пересчитал? В классической культуре у меня из ноды таблицы сразу ссылка на ноду в дереве, я ее удаляю и вставляю заново с новой скоростью.

Date: 2009-12-21 09:46 am (UTC)
From: [identity profile] lionet.livejournal.com
Псевдокод:

updateDerivedTree(DerivedTree, Hostname, Speed, Speed) -> ok;
updateDerivedTree(DerivedTree, Hostname, OldSpeed, NewSpeed) ->
    transform(DerivedTree, fun(
      {Speed, Host, Counter} when Speed == OldSpeed, Counter == 1 -> remove;
      {Speed, Host, Counter} when Speed == OldSpeed -> {replace, {Speed, Host, Counter-1}};
      _ -> ignore
    end),
    TransformResult = transform(DerivedTree, fun(
      {Speed, Host, Counter} when Speed == NewSpeed -> {Speed, Host, Counter+1}
      _ -> ignore
    end),
    case TransformResult of
      found -> ok;
      notfound -> add(DerivedTree, {Speed, Host, 1})
    end).

Date: 2009-12-21 12:46 pm (UTC)
From: [identity profile] kika.livejournal.com
что делает transform/2 ? Обходит все дерево и прикладывает к каждой ноде fun?

Date: 2009-12-21 12:50 pm (UTC)
From: [identity profile] lionet.livejournal.com
Вызывает двоичный поиск по ключу (ключ забыл явно вторым аргументом указать). O(logN). Когда найдёт ключ, то вызывает функцию, и осуществляет операцию, которая этой функцией была подсказана, и либо оставляет дерево в покое, либо трансформирует текущую ноду.

Date: 2009-12-21 02:17 pm (UTC)
From: [identity profile] kika.livejournal.com
А ключом у тебя в дереве является скорость? А то что половина хостов имеют скорость 0, никому не помешает?

Date: 2009-12-21 02:34 pm (UTC)
From: [identity profile] lionet.livejournal.com
А в чём дело? Если они просто её "имеют" — то дерево не перестраивается и даже не читается, так как срабатывает short-cirquit в псевдокоде, первой же строчкой.

А если значения флуктуируют в очень небольшом промежутке, тогда всё зависит от способа организации этого bag'а: есть ли в нём возможность указать secondary key. В простейшем случае можно сделать двухуровневый set: на первом уровне ключём является скорость, на втором - хост. Экстраполируя, получаем API для бэгов произвольной глубины:
transform(MultiBag, Keys, TransF) -> Result
Types   MultiBag = gb_trees()
       Keys = [term()]
       TransF = fun(Entry) -> retain | {replace, Entry} | delete


Пример:
transform(…, [0, "localhost"], fun({0, "localhost", _Key}) -> retain end).

Date: 2009-12-21 03:22 pm (UTC)
From: [identity profile] kika.livejournal.com
Флуктуируют они в адском промежутке, конкретно скорость может колебаться от нуля до wire speed. Но идею я понял, спасибо.

Date: 2009-12-21 03:26 pm (UTC)
From: [identity profile] lionet.livejournal.com
А если значения флуктуируют в очень небольшом промежутке

Фигню сморозил, конечно, очередной раз. Флуктуировать они могут как угодно, тут от степени флуктуации ничего не зависит.

Date: 2009-12-21 03:54 pm (UTC)
From: [identity profile] kika.livejournal.com
Тут на самом деле неприятнее то, что надо знать OldSpeed, который можно выудить только еще одним лукапом. Но это терпимый оверхед.

Date: 2009-12-21 03:59 pm (UTC)
From: [identity profile] lionet.livejournal.com
O(logN), он и в африке O(logN), даже с большой константой. А учитывая то, что при использовании эрланга ты уже получаешь фактор ~3-10x от скорости C, плюс-минус два в середине очень короткого цикла не должно волновать ;)

Date: 2009-12-21 04:02 pm (UTC)
From: [identity profile] kika.livejournal.com
Ктоб ерлангу хороший компилятор написал...

Date: 2009-12-21 10:12 am (UTC)
From: [identity profile] lionet.livejournal.com
В случае решения на императивщине, сложность O(logN) на апдейтах.
В случае показанного выше решения — сложность O(logN) на апдейтах.

Date: 2009-12-21 09:27 am (UTC)
From: [identity profile] jsn.livejournal.com
я, может, не понимаю чего. а что мешает тебе точно так же держать, я не знаю, какое-нибудь purely functional tree? ну апдейты чуть подороже, там, O(log N), небось, вместо O(1) до ребалансировки; вроде бы не ужас-ужас?

Date: 2009-12-21 09:31 am (UTC)
From: [identity profile] kika.livejournal.com
Да ничего не мешает, кроме O(logN) :-) Да и логарифм это, ключом в дереве же является скорость, а не имя, и чтобы выбросить старую скорость из дерева мне надо обежать его всё и найти в нем нужную ноду.

Date: 2009-12-21 09:42 am (UTC)
From: [identity profile] jsn.livejournal.com
ну не прям всё, ты же знаешь предыдущую скорость. but yeah, i get the idea.

Date: 2009-12-21 02:18 pm (UTC)
From: [identity profile] kika.livejournal.com
Ну да знаю. Раскручиваемся с нуля, у всех предыдущая скорость - ноль.

Date: 2009-12-21 02:33 pm (UTC)
From: [identity profile] jsn.livejournal.com
это же всё никакого отношения не имеет к pure functional, те же проблемы с любым balanced tree у тебя? ну держи нули в отдельном листе, я не знаю? :) или, там, compound key придумай какой?

Date: 2009-12-21 07:35 pm (UTC)
From: [identity profile] 109.livejournal.com
да, правильное решение - composite key (speed, host_id). неуникальные индексы у всех нормальных баз так и устроены (clustered key неявно хранится не только в листьях, но и ветках).

Date: 2009-12-21 02:36 pm (UTC)
From: [identity profile] jsn.livejournal.com
...а, ну да, no reverse link. ну не знаю.

Date: 2009-12-21 08:32 pm (UTC)
From: [identity profile] 109.livejournal.com
> запросы снаружи - типа а покажи-ка мне список хостов, отсортированных по пингу. Допустим, хостов у нас ровно один газиллион, поэтому сортировать на каждый запрос накладно.

мне кажется, ты чего-то не договариваешь. потому что если тебе надо отдать весь газиллион сразу, то сортировка является наименьшей из твоих проблем. а если тебе надо отдать top N, или устроить paging какой-нибудь, то это две разные задачи, которые оптимально могут решаться по-разному.

сбалансированные деревья тебе по-всякому пригодятся, если их ещё нет (зачем в структурах держать указатели на деревья, непонятно). но есть вопросы, которые могут усложнить рукописное. например, годится ли выдача с phantom rows? missing rows? duplicate rows? (я предполагаю, что данные у тебя апдейтятся параллельно с выполнением аналитических запросов, а не через global lock, который либо то, либо сё).

короче, если подобные вопросы не продуманы, или продуманы и есть подозрение, что будут проблемы, которые придётся решать, то лучше использовать rdbms, где их продумали и решили за тебя.

скорость/производительность: описанная задача, что в виде top N, что в виде paging, выполняется нормальной базой суб-миллисекундно, десяток тысяч раз в секунду.

Date: 2009-12-21 08:36 pm (UTC)
From: [identity profile] kika.livejournal.com
Да, реально задача отдать topN, где N произвольное, но заранее заданное число. С "нормальной базой" есть одна проблема - на нее нет вычислительного ресурса. Предмет обсуждения - это телеком appliance, живущий в 2U корпусе и чисто конкретно нагруженный своей работой, за которую ему денег платят. Если с процессором там более-менее (пока) свободно, то с памятью полный швах, хотя технически ее от 12Гб в entry level.

Date: 2009-12-22 01:19 am (UTC)
From: [identity profile] 109.livejournal.com
define "полный швах" :)

вообще, sql server (нормальный, а не компакт) может нормально жить в довольно-таки тесных помещениях - например, 100 мегабайт памяти на всё про всё. зависит от задачи, конечно. rule of thumb is - если all non-leaf index pages влезают в память, то всё в порядке. сравни с самописным решением: в памяти надо держать индексы целиком, а не только их non-leaf части.

также: обязательно ли сервер базы должен бежать на том же самом ящике? round trip через один хоп - это тоже sub-millisecond.

Date: 2009-12-22 06:21 am (UTC)
From: [identity profile] kika.livejournal.com
второй ящик - это минимум 2000 долларов на железо, плюс support costs. А полный швах - это буквально, вся доступная память занята приложением, которое готово съесть сколько дадуд. Плюс еще есть проблема с диском - дисковая подсистема заметно busy трафиком от приложения, часто iowait в районе 40-60%. В общем плохо там будет любому сиквелу, кроме разве что sqlite :-)

Date: 2009-12-22 10:39 am (UTC)
From: [identity profile] 109.livejournal.com
а чем sqlite такой волшебный?

вообще, конечно, если доступаться до базы должен только один процесс с одной машины, то embedded engines лучше.

Date: 2009-12-22 11:43 am (UTC)
From: [identity profile] kika.livejournal.com
скулайт очень маленький и для своих размеров достаточно быстр, если не требовать от него слишком многого.
Один процесс, да.

Profile

kika: (Default)
kika

January 2017

S M T W T F S
1234567
89 1011121314
151617181920 21
22232425262728
293031    

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 11th, 2025 01:09 am
Powered by Dreamwidth Studios