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

[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-телефонии балансер трафика гоняли с агрегатными функциями. И без кластера все бегало, не смотря на прорву транзакций и хитрую таблицу весов с ценами на разные регионы.
Так же видел, как народ клепал кучу потоков с коммитами в каждом и аккуратно загибал гору железа в позу "зю". Потому как на джаве писать научились, а базам их никто научить не успел