Здравствуйте, remark, Вы писали:

R>Да, именно по сравнению с фиксацией на винте. И я абсолютно серьезно.
R>Допустим у нас стоит RAID с максимальной пропускной способностью 320 Мб/с. Т.е. если размер транзакции 4 кб, то мы в пределе можем фиксировать 90'000 т/с.
Это неправда. throughput почти никакого отношения к скорости транзакции не имеет.
Во-первых, он мерится в оптимальных условиях потоковой записи, когда винт выбирает порядок записи секторов самостоятельно. Одиночный Flush скорее всего потребует seek time, который испортит общую картину.
R>А если размер транзакции 256 байт, то — 1.5 млн т/с.
Во вторых, "размер транзакции" — это фикция. Винт оперирует блоками фиксированного размера; в современной жизни это как правило 64kb. Поэтому даже коммит 1 байта потребует flush 64 килобайт, и в самом удачном случае, когда идет только запись в журнал и на позиционирование тратиться не надо, ты получишь всего 5k транзакций в секунду. В реале — еще примерно на порядок меньше. Парни, которые получают 3 миллиона транзакций в минуту, оперируют очень далеким от потребительского железом.
R>Т.е. на 32-процессорной машине у нас есть всего 21 мкс на транзакцию. А на 4-процессорной — 2.5 мкс на транзакцию.
Welcome to the real world.

Здравствуйте, remark, Вы писали:

R>Может кто ещё приведёт пример задачи. Мне сходу в голову никакой пример-убийца не приходит. Ну если Вы тоже считаете, что таких примеров нет, то тоже выскажитесь. Может и действительно нет...

R>Суть: должно быть большое "множество" (массив, список, дерево — не важно) данных. Данные часто и регулярно изменяются. Нет возможности партицировать данные. Нет возможности сделать N копий данных. Данные меняются несколькими потоками.

Чесно говоря, я уже запутался в вашей длительной дискуссии. Но если вам нужен пример большого массива данных, то посмотрите в сторону словаря процессов в том же Erlang-е. Ведь Erlang хвастается тем, что там можно создавать сотни тысяч процессов в рамках одной VM. Получается, что если есть 100K процессов, и каждый процесс описывается хотя бы 20 байтами, то размер словаря составит ~20Mb.

Обращений к словарю будет множество -- ведь обмен сообщениями идет посредством Pid-ов процессов. Словарь будет постоянно изменяться: с одной стороны, появление и исчезновение процессов с темпом под несколько сотен в секунду, с другой -- самому планировщику процессов так же нужно будет что-нибудь обновлять (например, метку времени последней активизации процесса).

Или это пример из другой оперы?

Здравствуйте, remark, Вы писали:

R>Может кто ещё приведёт пример задачи. Мне сходу в голову никакой пример-убийца не приходит. Ну если Вы тоже считаете, что таких примеров нет, то тоже выскажитесь. Может и действительно нет...

R>Суть: должно быть большое "множество" (массив, список, дерево — не важно) данных. Данные часто и регулярно изменяются. Нет возможности партицировать данные. Нет возможности сделать N копий данных. Данные меняются несколькими потоками.
Ну, если честно, то это не задача. Ведь это не просто данные; задача — в том, чтобы выполнять некоторые модификации. Что такое "изменяются", которое часто и регулярно?
Вот для стека мы знаем O(1) реализацию без модификаций. Там, конечно же, нет никакого массива — ровно потому, что от стека нужно поведение. Которое push и pop.
Массив — это значит get[i]/set[i]. C ним так просто не получится; но есть большой риск, что на самом деле в задаче массив вовсе не нужен. Что на самом деле он используется для хранения какой-то более высокоуровневой структуры, и все эти get и set получают какие-то неслучайные i, и мы можем придумать структуру, которая поддержит все эти вещи без модификаций.

Вообще, насколько я знаю, задач, для которых есть решение на константных структурах (с приличной асимптотикой), не так уж и много. Для deque, вроде бы, решение есть, но шибко сложное. Для произвольного графа, естественно нету.

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, remark, Вы писали:

R>>Что такое "url-хешь"? Не могу нагуглить...

WH>В общем случае это считаем от запроса или его части хешь и по остатку от деления хеша на N отправляем одному из N обработчиков.
WH>В случае с HTTP считаем от url. Отсюда и пошло.
WH>В частности это позволяет очень сильно повысить кешхит.


Блин, ну надо ж было так назвать
Это ж использовалось задолго до появления урлов вообще. Я правда может не более понятным термином называю — партицирование по хэшу.

Я согласен, что это очень хороший приём и он позволяет в части случаев избавиться от "многопоточных" структур данных.
Но опять же не всегда. Во-первых, обязательное требование, что бы данные были связаны с запросами один-к-одному. Контр-пример с лицевыми счетами, который я приводил, я там специально указал операцию перевода с одного л/с на другой, которая делает невозможным партицирование по хэшу л/с. Контр-пример с игровым сервером, который я приводил, я там специально указал, что внутри "сцены" игроки произвольно взаимодействуют с моделью мира, что тоже делает партицирование внутри сцены невозможным. Второе требование — хэш должен быть равномерным, что может быть не так, если есть небольшой поток "тяжелых" запросов.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, remark, Вы писали:

R>>Да, именно по сравнению с фиксацией на винте. И я абсолютно серьезно.
R>>Допустим у нас стоит RAID с максимальной пропускной способностью 320 Мб/с. Т.е. если размер транзакции 4 кб, то мы в пределе можем фиксировать 90'000 т/с.
S>Это неправда. throughput почти никакого отношения к скорости транзакции не имеет.
S>Во-первых, он мерится в оптимальных условиях потоковой записи, когда винт выбирает порядок записи секторов самостоятельно. Одиночный Flush скорее всего потребует seek time, который испортит общую картину.
R>>А если размер транзакции 256 байт, то — 1.5 млн т/с.
S>Во вторых, "размер транзакции" — это фикция. Винт оперирует блоками фиксированного размера; в современной жизни это как правило 64kb. Поэтому даже коммит 1 байта потребует flush 64 килобайт, и в самом удачном случае, когда идет только запись в журнал и на позиционирование тратиться не надо, ты получишь всего 5k транзакций в секунду. В реале — еще примерно на порядок меньше. Парни, которые получают 3 миллиона транзакций в минуту, оперируют очень далеким от потребительского железом.
R>>Т.е. на 32-процессорной машине у нас есть всего 21 мкс на транзакцию. А на 4-процессорной — 2.5 мкс на транзакцию.
S>Welcome to the real world.


Я несколько раз проводил тесты скорости потоковой загрузки данных в БД. Компьютеры были самые обычные, "домашние", БД на отдельной машине от сервера, локалка 100Mbps частично загруженная. На Oracle и на PostgreSQL.
Скорость загрузки получалась порядка 80'000 записей в секунду. И она всегда упиралась в скорость винта на сервере БД — там стояли обычные IDE со скоростью несколько Мб/с.

Даже такую пропускную способность обеспечить далеко не просто. Что уж говорить, если 80'000 trx/s увеличить хотя бы в пару раз.

Да вообще, я не понимаю, Вы так говорите, как будто не разу не видели компа (в смысле проца) загруженного на 100%. Для чего тогда все эти SMP серверы, если всё упирается в винт. Если бы у всех всё жёстко упиралось в винт, то все бы ставили всякие RAID, SAN и не знаю там чего ещё, а компьютеры бы оставались однопроцессорными.

Коммитить ествественно надо не по одной транзакции. Коммитить надо пачками. Тут вариантов несколько, самые простые:
1. Собирать пачку не более N транзакций, или ждать не более M времени, далее коммитить всё пачкой и только после этого всем отвечать, что транзакции приняты.
2. Сразу отвечать клиентам, что транзакции приняты, а коммитить пачкой потом. Тут есть возможность потерять транзакции. В каких-то ситуациях это допустимо. Тем более, что можно транзакции хранить в shared-memory, тогда что-то потеряется только если компьютер накроется.
3. Сразу отвечать клиентам, что транзакции приняты, а коммитить пачкой потом. Но при этом дополнительно уведомлять клиентов, что транзакция окончательно обработана. Тогда если клиент не получает уведомления об обработке в течение времени X, то он повторно отправляет транзакцию, и уж тут можно разбираться — транзакция в обработке, отложена, или потерялась. Это тоже надежная схема, но при этом с отложенным сохранением.

Тем более, что есть сервера, которым вообще ничего не надо сохранять. Например, сетевой рутер может каждый проходящий пакет никуда и не сохранять. Или для игровых серверов может быть вполне нормально что, если он падает, то всё теряется.

Исходя из всего этого, я считаю утверждение, что всегда все обязательно сохранять в БД, и что всегда всё обязательно жестко упрется в винт, и что поэтому вопросы эффективной организации программной обработки не имеют смысла, — полностью НЕ состоятельным.

Здравствуйте, eao197, Вы писали:

E>Чесно говоря, я уже запутался в вашей длительной дискуссии. Но если вам нужен пример большого массива данных, то посмотрите в сторону словаря процессов в том же Erlang-е. Ведь Erlang хвастается тем, что там можно создавать сотни тысяч процессов в рамках одной VM. Получается, что если есть 100K процессов, и каждый процесс описывается хотя бы 20 байтами, то размер словаря составит ~20Mb.

E>Обращений к словарю будет множество -- ведь обмен сообщениями идет посредством Pid-ов процессов. Словарь будет постоянно изменяться: с одной стороны, появление и исчезновение процессов с темпом под несколько сотен в секунду, с другой -- самому планировщику процессов так же нужно будет что-нибудь обновлять (например, метку времени последней активизации процесса).

E>Или это пример из другой оперы?


По-моему, хороший пример. Я не думаю, что разработчики и в ран-тайме используют такую же стратегию, что "вот очереди, а всё остальное поверх очередей". Скорее всего они там используют именно разделяемые структуры данных для критичных подсистем, потому что это быстрее в некоторых случаях. Скорее всего там что-то типа распределенного шедулера на work-stealing lifo или fifo очередях.

Здравствуйте, WolfHound, Вы писали:

WH>>>Этих частных случаев сильно больше чем может показаться на первый взгляд.

R>>Кстати, это ведь уже не обмен сообщениями, правильно? Это уже разделяемая структура? Или я чего-то не понимаю?

WH>Неизменяемая структура данных.


А как новая голова списка распространяется до других потоков? Все потоки уведомляются с помощью сообщений?

Здравствуйте, remark, Вы писали:

R>Да вообще, я не понимаю, Вы так говорите, как будто не разу не видели компа (в смысле проца) загруженного на 100%.

Я поясню: лично я не считаю, что bottleneck во всех задачах — это именно винт. Это была точка зрения wolfhound.
Я всего лишь объяснил, почему невозможно получить полтора миллиона коммитов в секунду на винте с 320Mb/s. Потому что ваш дальнейший спор оперирует непониманием причин разницы в 3-4 десятичных порядка во временах дисковых коммитов по сравниению с RAM коммитами.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, remark, Вы писали:

R>>Может кто ещё приведёт пример задачи. Мне сходу в голову никакой пример-убийца не приходит. Ну если Вы тоже считаете, что таких примеров нет, то тоже выскажитесь. Может и действительно нет...

R>>Суть: должно быть большое "множество" (массив, список, дерево — не важно) данных. Данные часто и регулярно изменяются. Нет возможности партицировать данные. Нет возможности сделать N копий данных. Данные меняются несколькими потоками.

S>Ну, если честно, то это не задача. Ведь это не просто данные; задача — в том, чтобы выполнять некоторые модификации. Что такое "изменяются", которое часто и регулярно?
S>Вот для стека мы знаем O(1) реализацию без модификаций. Там, конечно же, нет никакого массива — ровно потому, что от стека нужно поведение. Которое push и pop.
S>Массив — это значит get[i]/set[i]. C ним так просто не получится; но есть большой риск, что на самом деле в задаче массив вовсе не нужен. Что на самом деле он используется для хранения какой-то более высокоуровневой структуры, и все эти get и set получают какие-то неслучайные i, и мы можем придумать структуру, которая поддержит все эти вещи без модификаций.


Так я и не говорю, что это задача. Задачу я как раз прошу привести. Поэтому все эти моменты, о которых, ты говоришь должен доопределить тот, кто приведёт конкретную задачу.
И массив я не говорил, я специально написал — "множество" (массив, список, дерево — не важно)". Что угодно, любая структура данных.


S>Вообще, насколько я знаю, задач, для которых есть решение на константных структурах (с приличной асимптотикой), не так уж и много. Для deque, вроде бы, решение есть, но шибко сложное. Для произвольного графа, естественно нету.


Тут дело не только в константных структурах данных. Суть — задача, на которой подход на передаче сообщений ведёт себя не лучшим образом, и где можно более эффективно реализовать с помощью разделяемой структуры данных (даже если речь идёт просто об атомарном регистре — позволяющем атомарную подмену одного объекта другим).
Например, возможность т.н. партицирования по хэшу (url-хэшь) так же может сыграть в пользу обмена сообщениями. Например есть множество лицевых счетов, но все транзакции относятся исключительно к одному л/с. В таком случае мы можем разделить множество л/с на части по кол-ву потоков, и каждый поток будет "однопоточно" работать со своей частью. А управляющий поток будет считать хэш от номера л/с и раскидывать транзакции соотв. рабочим потокам. Такая архитектура хорошо подходит для обмена сообщениями, и как мы можем реализовать существенно лучше на основе разделяемых структур не видится.
Однако стоит ввести операцию перевода денег м одного л/с на другой, как возможность партицирования исчезает. Этот пример я приводил, но WolfHound постоянно уводит разговор в стороны — то на диск, то на то, что это — абстрактная недоопределенная задача...

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, remark, Вы писали:

R>>Да вообще, я не понимаю, Вы так говорите, как будто не разу не видели компа (в смысле проца) загруженного на 100%.

S>Я поясню: лично я не считаю, что bottleneck во всех задачах — это именно винт. Это была точка зрения wolfhound.
S>Я всего лишь объяснил, почему невозможно получить полтора миллиона коммитов в секунду на винте с 320Mb/s.

Конкретными цифрами я готов поступиться. Можно их уменьшить на порядок. Я лишь хотел показать, что я не вижу прям ничего такого явного, что бы говорило, что диск — это гарантированный боттлнек с перевесом в несколько порядков, и что поэтому типа вообще не имеет смысла рассматривать вопросы эффективной организации программной обработки.

S>Потому что ваш дальнейший спор оперирует непониманием причин разницы в 3-4 десятичных порядка во временах дисковых коммитов по сравниению с RAM коммитами.

По-моему, как таковое время коммита ни на диск, ни в память не имеет значения. Имеет значение, сколько времени у нас в итоге остается на программную обработку одной транзакции, что бы держать диск загруженным. Если взять даже 100'000 транзакций/сек (это я лично получал на "домашнем" компьютере и одном IDE диске), то получается время на одну транзакцию — 10 мкс. Ну не знаю, мне такое время пока не удавалось получить, максимум, что я получал — 50 мкс, да и то в немного упрощенной ситуации. Соотв. диск работал на 1/5 "мощности".

Не говоря уж о том, что в некоторых ситуациях вообще не надо сохранять на диск.

Здравствуйте, remark, Вы писали:

R>По-моему, хороший пример. Я не думаю, что разработчики и в ран-тайме используют такую же стратегию, что "вот очереди, а всё остальное поверх очередей". Скорее всего они там используют именно разделяемые структуры данных для критичных подсистем, потому что это быстрее в некоторых случаях. Скорее всего там что-то типа распределенного шедулера на work-stealing lifo или fifo очередях.

Тогда можно пойти дальше. В Erlang-е возникают сотни тысяч процессов потому, что там принято выделять отдельные операции в виде процессов со своими собственными данными. Но Erlang даже в том же телекоме не единственный востребованный инструмент. Другие компании, вроде Alkatel, используют в реализации своего софта C++. Т.е. для тех же самых задач на C++ мы будем иметь не сотни тысяч процессов, а сотни тысяч C++ных объектов, которые нужно как-то обрабатывать. Например, есть несколько потоков, общающихся между собой посредством сообщений и оперирующих этой сотней тысяч C++ных объектов (содержащих, например, данные о текущих звонках, транспортных сессиях, текущих закачках и пр.).

Здравствуйте, eao197, Вы писали:

E>Здравствуйте, remark, Вы писали:

R>>По-моему, хороший пример. Я не думаю, что разработчики и в ран-тайме используют такую же стратегию, что "вот очереди, а всё остальное поверх очередей". Скорее всего они там используют именно разделяемые структуры данных для критичных подсистем, потому что это быстрее в некоторых случаях. Скорее всего там что-то типа распределенного шедулера на work-stealing lifo или fifo очередях.

E>Тогда можно пойти дальше. В Erlang-е возникают сотни тысяч процессов потому, что там принято выделять отдельные операции в виде процессов со своими собственными данными. Но Erlang даже в том же телекоме не единственный востребованный инструмент. Другие компании, вроде Alkatel, используют в реализации своего софта C++. Т.е. для тех же самых задач на C++ мы будем иметь не сотни тысяч процессов, а сотни тысяч C++ных объектов, которые нужно как-то обрабатывать. Например, есть несколько потоков, общающихся между собой посредством сообщений и оперирующих этой сотней тысяч C++ных объектов (содержащих, например, данные о текущих звонках, транспортных сессиях, текущих закачках и пр.).

Я думаю, что WolfHound скажет, что тут слишком не детализировано. А если детализировать, то будет видно где какие углы можно срезать, что бы эффективно реализовать на основе сообщений.
Для маленьких объектов делать полную обновленную копию, и потом рассылать всем новую версию объекта.
Для больших делать частичное обновление, и опять же рассылать всем новую версию объекта.
Плюс использовать url-хэшь (партицирование данных по хэшу), что бы сделать оставшиеся данные вообще "однопоточными".

Здравствуйте, Sinclair, Вы писали:

S>Я поясню: лично я не считаю, что bottleneck во всех задачах — это именно винт. Это была точка зрения wolfhound.
И где я это сказал?

Здравствуйте, remark, Вы писали:
R>А как новая голова списка распространяется до других потоков? Все потоки уведомляются с помощью сообщений?
Что значит "все"? Те, кому нужно, получают структуру как сообщение от потока.

R>

Здравствуйте, remark, Вы писали:

R>Конкретными цифрами я готов поступиться. Можно их уменьшить на порядок. Я лишь хотел показать, что я не вижу прям ничего такого явного, что бы говорило, что диск — это гарантированный боттлнек с перевесом в несколько порядков, и что поэтому типа вообще не имеет смысла рассматривать вопросы эффективной организации программной обработки.
Я тебе показал. Неужели ты не видишь разницы между 1.5M и 5k? По мне так это 300 раз. Два с половиной десятичных порядка.

R>По-моему, как таковое время коммита ни на диск, ни в память не имеет значения. Имеет значение, сколько времени у нас в итоге остается на программную обработку одной транзакции, что бы держать диск загруженным. Если взять даже 100'000 транзакций/сек (это я лично получал на "домашнем" компьютере и одном IDE диске),
Это ты называешь транзакцией что-то не то, что называют транзакцией все остальные. Еше раз: нельзя делить скорость линейной записи на объем данных коммита.
R>то получается время на одну транзакцию — 10 мкс. Ну не знаю, мне такое время пока не удавалось получить, максимум, что я получал — 50 мкс, да и то в немного упрощенной ситуации. Соотв. диск работал на 1/5 "мощности".

R>Не говоря уж о том, что в некоторых ситуациях вообще не надо сохранять на диск.

R>

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, remark, Вы писали:

R>>Конкретными цифрами я готов поступиться. Можно их уменьшить на порядок. Я лишь хотел показать, что я не вижу прям ничего такого явного, что бы говорило, что диск — это гарантированный боттлнек с перевесом в несколько порядков, и что поэтому типа вообще не имеет смысла рассматривать вопросы эффективной организации программной обработки.

S>Я тебе показал. Неужели ты не видишь разницы между 1.5M и 5k? По мне так это 300 раз. Два с половиной десятичных порядка.

Ну 80k я получал на обычном IDE диске... 5k это уж слишком!


R>>По-моему, как таковое время коммита ни на диск, ни в память не имеет значения. Имеет значение, сколько времени у нас в итоге остается на программную обработку одной транзакции, что бы держать диск загруженным. Если взять даже 100'000 транзакций/сек (это я лично получал на "домашнем" компьютере и одном IDE диске),

S>Это ты называешь транзакцией что-то не то, что называют транзакцией все остальные. Еше раз: нельзя делить скорость линейной записи на объем данных коммита.

Я называю сохранением транзакции — сохрание записи в таблице в реляционной БД или добавление записи в локальный файл.
А остальные что называют сохранением транзакции?

Здравствуйте, remark, Вы писали:
R>Я называю сохранением транзакции — сохрание записи в таблице в реляционной БД или добавление записи в локальный файл.
R>А остальные что называют сохранением транзакции?
Для СУБД коммитом называют выполнение команды COMMIT, для локального файла — flush буфера, который гарантирует write-through.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, remark, Вы писали:
R>>Я называю сохранением транзакции — сохрание записи в таблице в реляционной БД или добавление записи в локальный файл.
R>>А остальные что называют сохранением транзакции?

S>Для СУБД коммитом называют выполнение команды COMMIT, для локального файла — flush буфера, который гарантирует write-through.

Сохранение в БД, естественно, подразумевает COMMIT. Я просто думал, что это очевидно. Извиняюсь за возникшие недоразумения.
Я имел в виду — c COMMIT'ом 80k trx/s.

Здравствуйте, remark, Вы писали:

E>>Тогда можно пойти дальше. В Erlang-е возникают сотни тысяч процессов потому, что там принято выделять отдельные операции в виде процессов со своими собственными данными. Но Erlang даже в том же телекоме не единственный востребованный инструмент. Другие компании, вроде Alkatel, используют в реализации своего софта C++. Т.е. для тех же самых задач на C++ мы будем иметь не сотни тысяч процессов, а сотни тысяч C++ных объектов, которые нужно как-то обрабатывать. Например, есть несколько потоков, общающихся между собой посредством сообщений и оперирующих этой сотней тысяч C++ных объектов (содержащих, например, данные о текущих звонках, транспортных сессиях, текущих закачках и пр.).


В общем случае (хотя наверное как раз в частном, но тем не менее) все эти сотни тысяч объектов можно "партицировать" между потоками. Т.е. создаем по потоку на процессор, и далее распределяем все звонки/сессии между этими потоками используя хэш от идентификатора звонка/сессии. Т.е. надо как-то заставить все эти сотни тысяч объектов "смешаться в единое целое", дабы их нельзя было разделить на слабосвязанные множества.

Вот ещё пример. Будем бить по святому — сборщик мусора
Допустим в ядре ОС, виртуальной машине, или просто ран-тайме языка надо реализовать подсистему управления памятью — аллокация, освобождение, сборка мусора и всё, связанное с этим. Я не думаю, что хорошая идея реализовывать это на обмене сообщениями. Уж слишком он "ленивый" и "неспешливый" для этого.
Допустим поток выдаёт запрос на аллокацию блока памяти, и допустим локальный кэш потока закончился, потоку надо получить блок из какого "центрального" хранилища, или от другого потока. Имхо, посылать сообщение кому-то и ждать ответа тут не самый лучший выход.