Яндекс Лабс в Palo Alto набирает С++ developers

[owld]

не разику не программист, я бы предложил такое решение -

1) По приходу запроса ( строки лога ) - делать над ним какой нить md5 , и если он уникален вставлять его в таблицу хешей
query_num| md5 | query string
Где query_num - это его серийный номер
2) Так же обновлять частоту этих запросов так что бы она была уже отсортирована по полю fqncy
query_num | fqncy


В любой момент времени можно вытащить топ 100 запросов

[crypto5]

не разику не программист, я бы предложил такое решение -

1) По приходу запроса ( строки лога ) - делать над ним какой нить md5 , и если он уникален вставлять его в таблицу хешей
query_num| md5 | query string
Где query_num - это его серийный номер
2) Так же обновлять частоту этих запросов так что бы она была уже отсортирована по полю fqncy
query_num | fqncy


В любой момент времени можно вытащить топ 100 запросов

Основная проблема с вашим подходом в том что возможно ваш хештейбл не поместится в памяти.

[owld]

Основная проблема с вашим подходом в том что возможно ваш хештейбл не поместится в памяти.

тогда query strings ( как основной сжиратель памяти ) хранить на диске в виде другой таблицы, а в хэштейбле на нее ссылаться.
Для быстрого поиска по хэшам должно работать, не ?

[Леонид Ильич Брежнев]

А что наука (computer science) говорит про скорость записи в такие вот hash tables при многопоточной обработке? Ну т.е. процедуру << (поискать) ? нашел, увеличить счетчик : не нашел, создать >> делать из нескольких threads? Насколько скорость обработки упадет при увеличении количества threads в пределах разумного, скажем не более 20.
Я так понимаю, изменение существующей записи можно довольно не сложно локать кааким-нибудь мьютексом, а вот как поступать с записями, которых нету, и их надо создать? Их имхо надо в одну очередь пустить: причем даже в этой очереди надо проверять не создан ли он еще (два среда могли одновременно засунуть в очередь два одинаковых URL, поскольку ни один из них не нашел этой записи в hash table), и если создан то локать на update. При этом наше многосредовое приложение на начальном этапе превратится в односредовое. Да и потом еще долго эта очередь будет обрабатываться.

[major Major Major Major]

не разику не программист, я бы предложил такое решение -

1) По приходу запроса ( строки лога ) - делать над ним какой нить md5 , и если он уникален вставлять его в таблицу хешей
query_num| md5 | query string
Где query_num - это его серийный номер
2) Так же обновлять частоту этих запросов так что бы она была уже отсортирована по полю fqncy
query_num | fqncy


В любой момент времени можно вытащить топ 100 запросов

Основная проблема с вашим подходом в том что возможно ваш хештейбл не поместится в памяти.

Я бы попробовал поиграться с хранением поколения запроса в добавление к их количеству и выкидывать старые - то есть когда количество запросов достигает 100k к примеру (цифра с потолка) выкидывать редковстречающиеся - тех что мало и добавлены давно. Типа generation based сборки мусора. Вообще задачка интересная. На интервью на эту тему хорошо можно поговорить.

[Интеррапт]

Я бы попробовал поиграться с хранением поколения запроса в добавление к их количеству и выкидывать старые - то есть когда количество запросов достигает 100k к примеру (цифра с потолка) выкидывать редковстречающиеся - тех что мало и добавлены давно. Типа generation based сборки мусора. Вообще задачка интересная. На интервью на эту тему хорошо можно поговорить.

Так я уже это предлагал несколько страниц назад. Такой алгоритм уже давно используется и называется Lossy Counting. Он не дает 100% точность, но на большом кол-ве запросов даст очень и очень приемлемую точность.

[Интеррапт]

Основная проблема с вашим подходом в том что возможно ваш хештейбл не поместится в памяти.

тогда query strings ( как основной сжиратель памяти ) хранить на диске в виде другой таблицы, а в хэштейбле на нее ссылаться.
Для быстрого поиска по хэшам должно работать, не ?

Предложенный вами md5 - это уже 16 байт. Плюс указатель на value (8 байт на указатель структуры для счетчика/4 байта и какого-то идентификатора для указания ну "ту другую таблицу" напр 8 байт). Это 36 байт на запись. Возьмите какие-нибудь 4 млрд записей. Это уже будет 114 гигабайта. Ну понятное дело, что это в худшем случае (типа все записи - уникальные), т.е. в результате будет затребовано меньше памяти, но мы еще и нагладные расходы не учитываем. Но тут еще надо принять во внимание, что хеш таблица должна идти непрерывным куском, что нереально, т.е. нужно имплементировать с multiple buckets (т.е. уже фактически trie создавать для multiple buckets). Ес-но вариант с хештейбл первым приходит в голову, но хеш таблица может тупо не поместиться в память.

[major Major Major Major]

Я бы попробовал поиграться с хранением поколения запроса в добавление к их количеству и выкидывать старые - то есть когда количество запросов достигает 100k к примеру (цифра с потолка) выкидывать редковстречающиеся - тех что мало и добавлены давно. Типа generation based сборки мусора. Вообще задачка интересная. На интервью на эту тему хорошо можно поговорить.

Так я уже это предлагал несколько страниц назад. Такой алгоритм уже давно используется и называется Lossy Counting. Он не дает 100% точность, но на большом кол-ве запросов даст очень и очень приемлемую точность.

Много страниц - не осилил. Все уже придумано до нас

[Интеррапт]

Я бы попробовал поиграться с хранением поколения запроса в добавление к их количеству и выкидывать старые - то есть когда количество запросов достигает 100k к примеру (цифра с потолка) выкидывать редковстречающиеся - тех что мало и добавлены давно. Типа generation based сборки мусора. Вообще задачка интересная. На интервью на эту тему хорошо можно поговорить.

Так я уже это предлагал несколько страниц назад. Такой алгоритм уже давно используется и называется Lossy Counting. Он не дает 100% точность, но на большом кол-ве запросов даст очень и очень приемлемую точность.

Много страниц - не осилил. Все уже придумано до нас

Страниц много, а код получается довольно короткий

[crypto5]

Я бы попробовал поиграться с хранением поколения запроса в добавление к их количеству и выкидывать старые - то есть когда количество запросов достигает 100k к примеру (цифра с потолка) выкидывать редковстречающиеся - тех что мало и добавлены давно. Типа generation based сборки мусора. Вообще задачка интересная. На интервью на эту тему хорошо можно поговорить.

Так я уже это предлагал несколько страниц назад. Такой алгоритм уже давно используется и называется Lossy Counting. Он не дает 100% точность, но на большом кол-ве запросов даст очень и очень приемлемую точность.

А еще несколько страниц перед этим этот вариант проходил как LFU кеш

[Boriskin]

А что наука (computer science) говорит про скорость записи в такие вот hash tables при многопоточной обработке? Ну т.е. процедуру << (поискать) ? нашел, увеличить счетчик : не нашел, создать >> делать из нескольких threads? Насколько скорость обработки упадет при увеличении количества threads в пределах разумного, скажем не более 20.

Насколько я помню, все конейнеры С++ STL являются thread safe при чтении, но не при записи, так что для одновременного write доступа придется лочить. Насколько изза этого может упасть производительность - сказать трудно, бо запись будет идти постоянно.

[Medium-rare]

Насколько я помню, все конейнеры С++ STL являются thread safe при чтении, но не при записи, так что для одновременного write доступа придется лочить. Насколько изза этого может упасть производительность - сказать трудно, бо запись будет идти постоянно.

Ну, полно альтернатив, как: http://msdn.microsoft.com/en-us/library/hh750089.aspx
И у Intel, и у Apple подобное есть.

[Boriskin]

Те же яйца, вид сбоку, бо внутри доступ все равно лочится. Или там применяется некий принципиально иной лучший способ гарантировать синхронизацию и целостность данных?

[Medium-rare]

Те же яйца, вид сбоку, бо внутри доступ все равно лочится. Или там применяется некий принципиально иной лучший способ гарантировать синхронизацию и целостность данных?

Пытаются лочить коллекцию более гранулярно. В примитивном случае с хэш-мапом это ещё как работает. Даже частично с бинарно-деревным мапом.

[Леонид Ильич Брежнев]

Те же яйца, вид сбоку, бо внутри доступ все равно лочится. Или там применяется некий принципиально иной лучший способ гарантировать синхронизацию и целостность данных?

Пытаются лочить коллекцию более гранулярно. В примитивном случае с хэш-мапом это ещё как работает.

Я никогда не писал, что лочить надо все. Речь шла о локе отдельного рекорде при апдейте.

[crypto5]

Те же яйца, вид сбоку, бо внутри доступ все равно лочится. Или там применяется некий принципиально иной лучший способ гарантировать синхронизацию и целостность данных?

Пытаются лочить коллекцию более гранулярно. В примитивном случае с хэш-мапом это ещё как работает.

Я никогда не писал, что лочить надо все. Речь шла о локе отдельного рекорде при апдейте.

Одного рекорда может быть недостаточно, может быть рейс кондишн когда вы в бакет хештаблицы вставляете например новый элемент.

[Леонид Ильич Брежнев]

Одного рекорда может быть недостаточно, может быть рейс кондишн когда вы в бакет хештаблицы вставляете например новый элемент.

Партия об этом тоже подумала. Предлагалось все инсерты (т.е. поискали по ключу и не нашли) делать в отдельной очереди. Другое дело, что даже в этой очереди надо перед инсертом все равно проверять, поскольку два среда могли не найти, и засунуть в очередь одно и тоже, тогда первый таки вставит, а второй должен уже update. Unless есть какой-нибудь hash table с инкрементальным инсертом. И проблема с этой очередью состоит в том, что даже при гаусовом распределении, слишком много будет новых элементов, которые вставляются один раз, т.е. очередь будет длиннной: среды апдейтов уже закончили давно работу, а сред очереди до сих пор их вставляет (причем для многих записей это будет апдейт в один сред)

[crypto5]

Значит есть шанс что мы с Партией на одной странице - нужно лочить не запись а бакет

[Сабина]

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

дорогое решение, даже если в процессе сортировки повторения убирать и счетчик увеличивать. имхо лучше сначала кластеризовать по некот. признаку подобия. потом отсортировать только кластер с наименьшей дисперсией, если там в итоге окажется < 10 запросов, отсортировать следуюший. Так же подход будет хорош, если соответствие 2-х (одинаковых) запросов не 100%

Это решение подходит только для хадупа?

[Леонид Ильич Брежнев]

Значит есть шанс что мы с Партией на одной странице - нужно лочить не запись а бакет

Нет, ну т.е. да лочить нужно бакет. Мне концептуально интересно. Я совершенно не уверен, что предложенный мною алгоритм будет сильно оптимальным, и даст какую-то существенную выгоду по сравнению с обработкой этого в один сред на 20 машинах (и созданием 20 почти одинаковых hash tables, там) и потом склейкой.

[crypto5]

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

дорогое решение, даже если в процессе сортировки повторения убирать и счетчик увеличивать. имхо лучше сначала кластеризовать по некот. признаку подобия. потом отсортировать только кластер с наименьшей дисперсией, если там в итоге окажется < 10 запросов, отсортировать следуюший. Так же подход будет хорош, если соответствие 2-х (одинаковых) запросов не 100%

Это решение подходит только для хадупа?

На хадуп оно отлично ложится, но думаю и на ноутбуке можно за разумное время посчитать.
Ну т.е. под хадуп там некоторые изменения целесообразно сделать. Собственно первая часть - посчитать каунты - это классический map reduce - первый пример во всех книжках - word count

[Сабина]

Как уже Berlaga намекнул, Yandex хотел увидеть какой-нибудь разумный вариант down sampling-га. И как Дорогой Леонид Ильич заметил, можно обрабатывать log файлы параллельно, поскольку вставка в хранилище в памяти будет значительно быстрее, чем чтение файлов, особенно если файлы где-нибудь на сети (HDFS).

Причем парсить их надо сразу в базу данных и потом на оракловском rac-е в PL/SQL аналитическими функциями кранчить

[mynameiszb]

Причем парсить их надо сразу в базу данных и потом на оракловском rac-е в PL/SQL аналитическими функциями кранчить

Oracle RAC вам ничего не даст. RAC - это бесперебойность сервиса в первую очередь, производительность новые узлы там не сильно-таки поднимают.

PS. Или сдается мне, что это был сарказм? (с) почти "Человек с бульвара Капуцинов"

[Сабина]

Причем парсить их надо сразу в базу данных и потом на оракловском rac-е в PL/SQL аналитическими функциями кранчить

Oracle RAC вам ничего не даст. RAC - это бесперебойность сервиса в первую очередь, производительность новые узлы там не сильно-таки поднимают.

PS. Или сдается мне, что это был сарказм? (с) почти "Человек с бульвара Капуцинов"

Это был сарказм о мощи распаралеливания, конечно всерьез не предлагала. Плюс видела своими глазами rac на 80 CPU который кранчил internet traffic в реальном времени и потом отлаженными аналитическими кверями считал распределение запросов, быстренько так знаете ли

[mynameiszb]

Плюс видела своими глазами rac на 80 CPU который кранчил internet traffic в реальном времени и потом отлаженными аналитическими кверями считал распределение запросов, быстренько так знаете ли

Мы еще в 2003 в ip-телефонии балансер трафика гоняли с агрегатными функциями. И без кластера все бегало, не смотря на прорву транзакций и хитрую таблицу весов с ценами на разные регионы.
Так же видел, как народ клепал кучу потоков с коммитами в каждом и аккуратно загибал гору железа в позу "зю". Потому как на джаве писать научились, а базам их никто научить не успел