Purely functional data something
Dec. 21st, 2009 09:29 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
Имхо, довольно распространенная задача. Скажем у нас есть множество структур, описывающих некую жызненную ситуацию, скажем мониторинг хостов в сети. Структура содержит имя хоста, адрес, всякие прочие фактически иммутабельные параметры плюс некое количество изменяющихся параметров мониторинга, время пинга, скорость передачи данных, количество HTTP ошибок и теде и тепе. Структуры хранятся, допустим для простоты, в хеше по имени хоста. Все отлично, софтина работает, обмеряет хосты, апдейтит табличку с записями и жизнь прекрасна. Теперь нам надо сделать запросы снаружи - типа а покажи-ка мне список хостов, отсортированных по пингу. Допустим, хостов у нас ровно один газиллион, поэтому сортировать на каждый запрос накладно.
В традиционной культуре мы строим сбалансированные деревья с указателями на структуры (а в структурах указатели на деревья) и организуем синхронное плавание.
А как в функциональной культуре решается такая задача? Pointer trickery тут какбе немного недоступна.
Вкратце: есть структура -record(host, {host_id, speed = 0}). и из нее ETS таблица из одного газиллиона записей. Надо быстро отдавать список хостов, отсортированный по speed. Можно наверное положить это в Мнезию и понадеяться на ее ORDER BY, а если без Мнезии, ручками?
В традиционной культуре мы строим сбалансированные деревья с указателями на структуры (а в структурах указатели на деревья) и организуем синхронное плавание.
А как в функциональной культуре решается такая задача? Pointer trickery тут какбе немного недоступна.
Вкратце: есть структура -record(host, {host_id, speed = 0}). и из нее ETS таблица из одного газиллиона записей. Надо быстро отдавать список хостов, отсортированный по speed. Можно наверное положить это в Мнезию и понадеяться на ее ORDER BY, а если без Мнезии, ручками?
no subject
Date: 2009-12-21 06:52 am (UTC)no subject
Date: 2009-12-21 07:01 am (UTC)no subject
Date: 2009-12-21 04:23 pm (UTC)no subject
Date: 2009-12-21 07:10 pm (UTC)no subject
Date: 2009-12-21 08:38 pm (UTC)no subject
Date: 2009-12-21 09:43 pm (UTC)no subject
Date: 2009-12-21 09:22 am (UTC)no subject
Date: 2009-12-21 09:29 am (UTC)no subject
Date: 2009-12-21 09:46 am (UTC)no subject
Date: 2009-12-21 12:46 pm (UTC)no subject
Date: 2009-12-21 12:50 pm (UTC)no subject
Date: 2009-12-21 02:17 pm (UTC)no subject
Date: 2009-12-21 02:34 pm (UTC)А если значения флуктуируют в очень небольшом промежутке, тогда всё зависит от способа организации этого bag'а: есть ли в нём возможность указать secondary key. В простейшем случае можно сделать двухуровневый set: на первом уровне ключём является скорость, на втором - хост. Экстраполируя, получаем API для бэгов произвольной глубины:
Пример:
no subject
Date: 2009-12-21 03:22 pm (UTC)no subject
Date: 2009-12-21 03:26 pm (UTC)Фигню сморозил, конечно, очередной раз. Флуктуировать они могут как угодно, тут от степени флуктуации ничего не зависит.
no subject
Date: 2009-12-21 03:54 pm (UTC)no subject
Date: 2009-12-21 03:59 pm (UTC)no subject
Date: 2009-12-21 04:02 pm (UTC)no subject
Date: 2009-12-21 10:12 am (UTC)В случае показанного выше решения — сложность O(logN) на апдейтах.
no subject
Date: 2009-12-21 09:27 am (UTC)no subject
Date: 2009-12-21 09:31 am (UTC)no subject
Date: 2009-12-21 09:42 am (UTC)no subject
Date: 2009-12-21 02:18 pm (UTC)no subject
Date: 2009-12-21 02:33 pm (UTC)no subject
Date: 2009-12-21 07:35 pm (UTC)no subject
Date: 2009-12-21 02:36 pm (UTC)no subject
Date: 2009-12-21 08:32 pm (UTC)мне кажется, ты чего-то не договариваешь. потому что если тебе надо отдать весь газиллион сразу, то сортировка является наименьшей из твоих проблем. а если тебе надо отдать top N, или устроить paging какой-нибудь, то это две разные задачи, которые оптимально могут решаться по-разному.
сбалансированные деревья тебе по-всякому пригодятся, если их ещё нет (зачем в структурах держать указатели на деревья, непонятно). но есть вопросы, которые могут усложнить рукописное. например, годится ли выдача с phantom rows? missing rows? duplicate rows? (я предполагаю, что данные у тебя апдейтятся параллельно с выполнением аналитических запросов, а не через global lock, который либо то, либо сё).
короче, если подобные вопросы не продуманы, или продуманы и есть подозрение, что будут проблемы, которые придётся решать, то лучше использовать rdbms, где их продумали и решили за тебя.
скорость/производительность: описанная задача, что в виде top N, что в виде paging, выполняется нормальной базой суб-миллисекундно, десяток тысяч раз в секунду.
no subject
Date: 2009-12-21 08:36 pm (UTC)no subject
Date: 2009-12-22 01:19 am (UTC)вообще, sql server (нормальный, а не компакт) может нормально жить в довольно-таки тесных помещениях - например, 100 мегабайт памяти на всё про всё. зависит от задачи, конечно. rule of thumb is - если all non-leaf index pages влезают в память, то всё в порядке. сравни с самописным решением: в памяти надо держать индексы целиком, а не только их non-leaf части.
также: обязательно ли сервер базы должен бежать на том же самом ящике? round trip через один хоп - это тоже sub-millisecond.
no subject
Date: 2009-12-22 06:21 am (UTC)no subject
Date: 2009-12-22 10:39 am (UTC)вообще, конечно, если доступаться до базы должен только один процесс с одной машины, то embedded engines лучше.
no subject
Date: 2009-12-22 11:43 am (UTC)Один процесс, да.