Круговой свободный от блокировок буфер
Я предполагаю, что у вас есть модель сообщения (вы используете laravel)
Ниже запрос должен дать вам то, что вы хотите.
Message::whereSenderIdAndClientId($userId1,$userId2)
->orWhere([
["sender_id", $userId2],
["client_id",$userId1]
])
->orderBy("created_at","desc")
->first()
Получать сообщения между отправителем и клиентом, упорядочивать сообщения с помощью create_at - desc, а затем принимать первое сообщение, которое является последним сообщением между собой.
9 ответов
На DDJ есть неплохая серия статей об этом . Признаком того, насколько сложным может быть этот материал, является исправление более ранней статьи , в котором все было неверно. Убедитесь, что вы понимаете ошибки, прежде чем делать свои собственные) -;
Художественный термин для того, что вы хотите, - это очередь без блокировок . Есть отличный набор заметок со ссылками на код и статьи Росс Бенсина. Парень, чьей работе я доверяю больше всего, - это Морис Херлихи (для американцев он произносит свое имя как «Моррис»).
Одним из полезных методов уменьшения конкуренции является хеширование элементов в несколько очередей и выделение каждому потребителю «темы».
Для последнего количества элементов, которые интересуют ваших потребителей - вы не хотите блокировать всю очередь и перебирать ее, чтобы найти элемент для переопределения - просто опубликуйте элементы в N-кортежах, то есть все N последних элементов , Бонусные баллы за реализацию, при которой производитель блокирует полную очередь (когда потребители не могут успевать) с тайм-аутом, обновляя свой локальный кеш кортежей - таким образом вы не оказываете противодавления на источник данных.
Требование, чтобы производители или потребители блокировали, если буфер пуст или заполнен, предполагает, что вы должны использовать обычную структуру данных блокировки с семафорами или переменными условий, чтобы производители и потребители блокировались до тех пор, пока данные не будут доступный. Код без блокировки обычно не блокируется в таких условиях - он запускает или отменяет операции, которые невозможно выполнить, вместо блокировки с использованием ОС. (Если вы можете позволить себе подождать, пока другой поток произведет или потребляет данные, тогда почему ожидание блокировки, пока другой поток завершит обновление структуры данных хуже?)
В (x86 / x64) Linux, внутрипотоковая синхронизация использование мьютексов достаточно дешево, если нет разногласий. Сосредоточьтесь на минимизации времени, которое производителям и потребителям нужно держать в руках. Учитывая, что вы Я сказал, что вас интересуют только последние N записанных точек данных, я думаю, что кольцевой буфер будет делать это достаточно хорошо. Однако я действительно не понимаю, как это согласуется с требованием блокировки и идеей потребителей, которые фактически потребляют (удаляют) данные, которые они читают. (Вы хотите, чтобы потребители смотрели только на последние N точек данных, а не удаляли их? Вы хотите, чтобы производители не заботились о том, что потребители не успевают за ними, и просто перезаписывают старые данные?)
Кроме того, как сказал Зан Линкс прокомментировал, вы можете агрегировать / буферизовать свои данные в более крупные фрагменты, когда у вас их много. Вы можете буферизовать фиксированное количество точек или все данные, полученные в течение определенного промежутка времени. Это означает, что операций синхронизации будет меньше. Тем не менее, это приводит к задержке, но если вы не используете Linux в реальном времени,
Очередь Саттера не оптимальна, и он это знает. Искусство многоядерного программирования - отличный справочник, но не доверяйте разработчикам Java в отношении моделей памяти, точка. Ссылки Росса не дадут вам однозначного ответа, потому что у них были свои библиотеки с такими проблемами и т. Д.
Выполнение программирования без блокировок порождает проблемы, если вы не хотите тратить много времени на то, что вы явно переборщили. инжиниринг перед решением проблемы (судя по его описанию, это обычное безумие «поиска совершенства» в согласованности кеша). На это уходят годы, и это часто приводит к тому, что сначала не решаются проблемы, а потом оптимизируется.
Я согласен с этой статьей и рекомендую не использовать структуры данных без блокировки. Относительно недавняя статья о безблокирующих очередях FIFO - это this , поиск дополнительных статей того же автора (авторов); есть также докторская диссертация по Чалмерсу, касающаяся структур данных без блокировок (я потерял ссылку). Однако вы не сказали, насколько велики ваши элементы - структуры данных без блокировки эффективно работают только с элементами размером в слово, поэтому вам придется динамически выделять свои элементы, если они больше машинного слова (32 или 64 биты). Если вы динамически распределяете элементы, вы переносите (предположительно, поскольку вы не профилировали свою программу и в основном выполняете преждевременную оптимизацию) узкое место в распределитель памяти, поэтому вам понадобится распределитель памяти без блокировки, например, Streamflow и интегрируйте его со своим приложением.
За последние пару лет я провел особое исследование структур данных без блокировки. Я прочитал большинство статей в этой области (их всего около сорока или около того - хотя реально можно использовать только десять или пятнадцать: -)
AFAIK, кольцевой буфер без блокировок не был изобретен. Проблема будет иметь дело со сложным состоянием, когда читатель обгоняет писателя или наоборот.
Если вы не потратили по крайней мере шесть месяцев на изучение структур данных без блокировок, не пытайтесь написать их самостоятельно. Вы ошибетесь, и вам может быть неочевидно, что ошибки существуют, пока ваш код не выйдет из строя после развертывания на новых платформах.
Я считаю, однако, что есть решение для ваших требований.
Вы должны соединить безблокировочная очередь со списком свободных от блокировок.
Свободный список предоставит вам предварительное распределение и, таким образом, устранит (с финансовой точки зрения дорогое) требование наличия безблокирующего распределителя; когда свободный список пуст, вы воспроизводите поведение кольцевого буфера, мгновенно удаляя элемент из очереди и используя его вместо этого.
(Конечно, в кольцевом буфере на основе блокировки, как только блокировка получена, получение элемента происходит очень быстро - в основном это просто разыменование указателя - но вы не получите этого ни в одном алгоритме без блокировки; им часто приходится стараться изо всех сил, чтобы делать что-то; накладные расходы, связанные с ошибкой всплывающего списка свободных с последующим удалением из очереди соответствует объему работы, который потребуется выполнить любому алгоритму без блокировки).
Майкл и Скотт разработали действительно хорошую очередь без блокировки еще в 1996 году. Ссылка ниже даст вам достаточно детали для отслеживания PDF их статьи;
Вот как я бы это сделал:
- сопоставить очередь с массивом
- сохранить состояние с индексами следующего чтения и следующей записи
- сохранить пустой полный битовый вектор около
Вставка состоит из использования CAS с приращением и пролистыванием при следующей записи. Когда у вас есть слот, добавьте свое значение, а затем установите соответствующий ему пустой / полный бит.
Удаление требует проверки бита перед проверкой недостаточного заполнения, но кроме этого, такие же, как и для записи, но с использованием читать индекс и очищать пустой / полный бит.
Будьте осторожны,
- Я не эксперт в этих вещах
- атомарные операции ASM кажутся очень медленными, когда я их использовал, поэтому, если вы в конечном итоге чем несколько из них, вы можете быстрее использовать блокировки, встроенные в функции вставки / удаления. Теория состоит в том, что одна атомарная операция по захвату блокировки, сопровождаемая (очень) несколькими неатомарными операциями ASM, может быть быстрее, чем то же самое, сделанное несколькими атомарными операциями. Но для выполнения этой работы потребуется ручное или автоматическое встраивание, так что это всего лишь один короткий блок ASM.
Просто для полноты: в OtlContainers есть хорошо протестированный круговой буфер без блокировки, но он написан на Delphi (TOmniBaseBoundedQueue - круговой буфер и TOmniBaseBoundedStack - ограниченный стек). В этом же блоке есть и неограниченная очередь (TOmniBaseQueue). Беспредельная очередь описана в Dynamic lock-free queue - doing it right. Первоначальная реализация ограниченной очереди (круговой буфер) была описана в Очередь без блокировки, наконец-то! , но с тех пор код был обновлен.