Как общая память и передача сообщений обрабатывают большие структуры данных?
глядя на подход Go и Erlang к параллелизму, я заметил, что они оба полагаются на передачу сообщений.
этот подход, очевидно, облегчает необходимость сложных блокировок, потому что нет общего состояния.
однако рассмотрим случай, когда многим клиентам требуется параллельный доступ только для чтения к одной большой структуре данных в памяти-например, массив суффиксов.
мои вопросы:
будет ли использование общего состояния быстрее и использовать меньше памяти, чем передача сообщений, поскольку блокировки в основном будут ненужными, потому что данные доступны только для чтения и должны существовать только в одном месте?
Как бы эта проблема была решена в контексте передачи сообщений? Будет ли один процесс с доступом к структуре данных, и клиенты просто должны будут последовательно запрашивать данные из нее? Или, если возможно, данные будут разделены для создания нескольких процессов, которые удерживают куски?
учитывая архитектуру современных процессоров и памяти, существует ли большая разница между двумя решениями-т. е. Может ли общая память считываться параллельно несколькими ядрами-это означает, что нет аппаратного узкого места, которое в противном случае сделало бы обе реализации примерно одинаковыми?
10 ответов:
да, общее состояние может быть быстрее в этом случае. Но только если вы можете отказаться от замков, и это возможно только в том случае, если это абсолютно только для чтения. если это "в основном только для чтения", то вам нужна блокировка (Если вам не удастся написать структуры без блокировки, имейте в виду, что они еще сложнее, чем блокировки), и тогда вам будет трудно заставить его работать так же быстро, как хорошая архитектура передачи сообщений.
Да, вы можете написать "серверный процесс", чтобы поделиться им. С действительно легкими процессами это не более тяжело, чем писать небольшой API для доступа к данным. Думайте как объект (в смысле ООП), который "владеет" данными. Разделение данных на куски для повышения параллелизма (так называемый "сегмент" в кругах БД) помогает в больших случаях (или если данные находятся на медленном хранении).
даже если NUMA становится мейнстримом, у вас все еще есть все больше и больше ядер на ячейку NUMA. И большая разница в том, что сообщение может быть передано только между двумя ядрами, в то время как блокировка должна быть сброшена из кэша на всех ядрах, ограничивая ее задержкой между ячейками шины (даже медленнее, чем доступ к ОЗУ). Во всяком случае, shared-state/locks становится все более и более невозможным.
короче.... привыкайте к передаче сообщений и серверных процессов, это все ярость.
Edit: возвращаясь к этому ответу, я хочу добавить о фразе, найденной в документации Go:
поделиться памятью, общаясь, не общайтесь, разделяя память.
идея такова: когда у вас есть блок памяти, разделяемый между потоками, типичный способ избежать параллельного доступа-использовать блокировку для арбитража. Стиль Go заключается в передаче сообщения со ссылкой, поток обращается к памяти только при получении сообщения. Он опирается на некоторую меру дисциплины программиста; но приводит к очень чистому коду, который можно легко корректировать, поэтому относительно легко отлаживать.
преимущество заключается в том, что вам не нужно копировать большие блоки данных на каждое сообщение и не нужно эффективно очищать кэши, как в некоторых реализациях блокировки. Еще несколько рано говорить, приводит ли стиль к более высокой производительности или нет. (особенно, поскольку текущая среда выполнения Go несколько наивна при планировании потоков)
одна вещь, чтобы понять, что модель параллелизма Erlang делает не действительно укажите, что данные в сообщениях должны быть скопированы между процессами, в нем говорится, что отправка сообщений является единственным способом связи и что нет общего состояния. Поскольку все данные неизменны, которые и фундаментальный, то реализация может очень хорошо не копировать данные, а просто отправить ссылку на него. Или может использовать комбинацию обоих методов. Как всегда, нет лучшие решение и компромиссы при выборе, как это сделать.
луч использует копирование, за исключением больших двоичных файлов, куда он отправляет ссылку.
в Erlang все значения неизменяемы - поэтому нет необходимости копировать сообщение, когда оно отправляется между процессами, так как оно не может быть изменено в любом случае.
в Go передача сообщений осуществляется по соглашению-нет ничего, что помешало бы вам отправить кому-то указатель на канал, а затем изменить указанные данные, только соглашение, поэтому снова нет необходимости копировать сообщение.
большинство современных процессоров используют варианты протокол МЭСИ. Из-за общего состояния передача данных только для чтения между различными потоками очень дешева. Однако измененные общие данные очень дороги, потому что все другие кэши, хранящие эту строку кэша, должны сделать ее недействительной.
Так что если у вас есть только для чтения данных, это очень дешево, чтобы разделить его между потоками вместо копирования с сообщениями. Если Вы читаете в основном данные, это может быть дорого для обмена между потоками, частично из-за необходимости синхронизации доступа, а частично из-за того, что записи разрушают кэш дружественного поведения общих данных.
неизменяемые структуры данных может быть полезным здесь. Вместо изменения фактической структуры данных вы просто создаете новую, которая разделяет большую часть старых данных, но с изменениями, которые вам нужно изменить. Совместное использование одной версии это дешево, так как все данные неизменяемы, но вы все равно можете обновить до новой версии эффективно.
обратите внимание, что ваши вопросы технически бессмысленны, потому что передача сообщений может использовать общее состояние, поэтому я предположу, что вы имеете в виду передачу сообщений с глубоким копированием, чтобы избежать общего состояния (как это делает Erlang в настоящее время).
будет ли использование общего состояния быстрее и использовать меньше памяти, чем передача сообщений, поскольку блокировки в основном будут ненужными, потому что данные доступны только для чтения и должны существовать только в одном месте?
использование общего состояния будет a много быстрее.
Как бы эта проблема была решена в контексте передачи сообщений? Будет ли один процесс с доступом к структуре данных, и клиенты просто должны будут последовательно запрашивать данные из нее? Или, если это возможно, данные будут разделены на несколько процессов, которые содержат куски?
можно использовать любой подход.
учитывая архитектуру современных процессоров и памяти, есть ли много разница между двумя решениями-т. е. Может ли общая память считываться параллельно несколькими ядрами-означает, что нет аппаратного узкого места, которое в противном случае сделало бы обе реализации примерно одинаковыми?
копирование является недружественным кешем и, следовательно, разрушает масштабируемость на многоядерных системах, поскольку это ухудшает конкуренцию за общий ресурс, который является основной памятью.
в конечном счете, передача сообщений в стиле Erlang предназначена для параллельного программирования в то время как ваши вопросы о производительности пропускной способности действительно направлены на параллельное программирование. Это два совершенно разных предмета, и перекрытие между ними на практике невелико. В частности, задержка обычно так же важна, как и пропускная способность в контексте параллельного программирования, а передача сообщений в стиле Erlang-отличный способ достичь желаемых профилей задержки (т. е. стабильно низких задержек). Проблема с общей памятью тогда заключается не столько в синхронизации между читателями и писатели, но управление памятью с низкой задержкой.
одно решение, которое не было представлено здесь, является репликацией master-slave. Если у вас есть большая структура данных, вы можете реплицировать изменения в нее на все ведомые устройства, которые выполняют обновление своей копии.
Это особенно интересно, если вы хотите масштабировать до нескольких машин, которые даже не имеют возможности обмениваться памятью без очень искусственных настроек (mmap блочного устройства, которое читает/записывает из памяти удаленного компьютера?)
вариант это есть менеджер транзакций, который просит красиво обновить реплицированную структуру данных, и он будет уверен, что он обслуживает один и только запрос на обновление одновременно. Это скорее модель mnesia для master-master репликации табличных данных mnesia, которые квалифицируются как "большая структура данных".
Что это большой структура данных?
один человек большой-это другой человек маленький.
на прошлой неделе я разговаривал с двумя людьми - один человек делал встроенные устройства он использовал слово "большой" - я спросил его, что это значит - он сказал более 256 Кбайт - позже на той же неделе в парень говорил о распространении СМИ-он использовал слово "большой" я спросил его, что он значит-он подумал немного и сказал" Не поместится на одной машине " скажем 20-100 Тбайт
в терминах Erlang "большой" может означать "не поместится в ОЗУ" - так что с 4 Гбайт ОЗУ структуры данных > 100 Мбайт можно считать большим-копирование структуры данных 500 Мбайт может быть проблема. Копирование небольших структур данных (скажем,
очень большие структуры данных (т. е. те, которые не помещаются на одной машине) должны быть скопировал и" полоснул " по нескольким машинам.
Так что я думаю у вас есть следующее:
небольшие структуры данных не проблема - так как они небольшие времена обработки данных являются быстро, копирование быстро и так далее (только потому, что они малы)
большие структуры данных являются проблемой-потому что они не помещаются на одной машине - так что копирование имеет важное значение.
проблема на данный момент действительно заключается в том, что блокировка и когерентность кэш-линии могут быть такими же дорогими, как копирование более простой структуры данных (например, несколько сотен байт).
большую часть времени умный написанный новый многопоточный алгоритм, который пытается устранить большую часть блокировки, всегда будет быстрее-и намного быстрее с современными структурами данных без блокировки. Особенно, когда у вас есть хорошо разработанные системы кэширования, такие как sun'S Niagara chip level multi-threading.
Если ваша система / проблема не легко разбивается на несколько и простых доступов к данным, то у вас есть проблема. И не все проблемы могут быть решены путем передачи сообщений. Вот почему до сих пор продаются некоторые суперкомпьютеры на базе Itanium, потому что у них есть терабайт общей оперативной памяти и до 128 процессоров, работающих на одной и той же общей памяти. Они на порядок дороже, чем основной кластер x86 с той же мощностью процессора, но вам не нужно разбивать свои данные.
другой причина, не упомянутая до сих пор, заключается в том, что программы могут стать намного легче писать и поддерживать при использовании многопоточности. Передача сообщений и общий подход ничего делает его еще более ремонтопригодным.
например, Erlang никогда не был разработан, чтобы сделать вещи быстрее, но вместо этого использовать большое количество потоков для структурирования сложных потоков данных и событий.
Я думаю, это был один из главных моментов в дизайне. В веб-мире google вам обычно все равно производительность-до тех пор, пока он может работать параллельно в облаке. И с передачей сообщений вы в идеале можете просто добавить больше компьютеров без изменения исходного кода.
обычно языки передачи сообщений (это особенно легко в erlang, так как у него есть неизменяемые переменные) оптимизируют фактическое копирование данных между процессами (конечно, только локальные процессы: вы захотите разумно подумать о своем сетевом распределении), поэтому это не так уж и важно.
другая параллельная парадигма-STM, программная транзакционная память. Рефери Clojure получают много внимания. Тим Брэй имеет хорошую серию изучить Erlang и параллельных механизмов в Clojure
http://www.tbray.org/ongoing/When/200x/2009/09/27/Concur-dot-next
http://www.tbray.org/ongoing/When/200x/2009/12/01/Clojure-Theses
Comments