LINUX.ORG.RU

Помогите придумать алгоритм нотификации об изменениях в чатике/треде

 


1

4

В СУБД хранится тред/чатик. Физически хранится ПОЧТИ как массив языка Си (побитый на блоки, возможно, а блоки, возможно, лежат в других дата-центрах, но реализация не меняет сути). Логически как std::vector или как [] в js/python, скажем. Список не сортирован дополнительно никак, кроме порядка добавления в его конец. Там нет поля timestamp_nanosec и какого-то индекса по нему: кого раньше добавили в массив, тот и раньше. В объекте «сообщение» может быть конечно timestamp, но на него всем похрен и нужно оно только чтобы клиент видел какое-то время сообщения.

Из СУБД сообщения треда можно доставать по индексу (номеру от начала списка с нуля). Причём, индекс совершенно честный - как в тупом массиве на Си: если в треде было 1 млн сообщений, а потом модератор дропнул 100 с начала (0…99), то все индексы съехали на 100 вниз - называвшийся ранее 500 стал называться 400.

Данная СУБД отлично всех устраивает, особенно экономически, поддерживая сотни тысяч запросов/сек на самой дешёвой бомжатской виртуалке. Главное, чем она интересна, это как раз экономика и дубовая простота.

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

Клиент залогинился в чатик, СУБД отдала ему 10 сообщений с конца. Причём, на каждом сообщении, при передаче на клиент, наклеен его индекс в массиве/списке - чтобы клиент знал в каком месте треда находится. Предположим, в треде было 1000 сообщений. На клиенте окажутся сообщения с индексами [989…999]. Клиент крутит чатик вверх, упирается в конец простыни и хочет подгрузить ещё штук 10 сверху. Шлёт серверу запрос R1: «дай [978…988]».

И тут наступает жепь-ебрилло:

Пока запрос R1 летел на сервер по сети, на сервере было дропнуто первых 2 сообщения и все индексы съехали. Клиент получит дубли пары сообщений (те, что у него уже были на сервере попадут в интервал R1 в результате съезда индексов). Это пережить можно - получил дубль - выкинул. Жепь-ебрилло похлеще: пока летел R1 на сервере дропнули сразу первых 100 сообщений. На клиент придёт ответ: «not found» вообще. Уже потом конечно до клиента долетит нотифайка про «drop 0…99» и клиент всё поймёт, но инфаркт в клиенте уже произошёл и всё умерло.

В общем, сгенерите какую-нибудь идею о борьбе с данным рассинхроном.

Если посмотреть на такую чатиковую систему как Slack, то там у каждой сообщеньки однозначный ID = «timestamp.timestamp_microsec» и дропание сообщений где-то в начале треда никак не затрагивает ID остальных сообщенек в этом треде. Я даже могу подумать, что у них в базе вообще все сообщеньки всех тредов лежат в одной таблице с этим адским primary_key (timestamp.timestamp_microsec) и это там ничему не противоречит, но я так не хочу чё-то пока.

Ответ на: комментарий от nikolnik

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

А ещё ничего и не сделано. Это только проекты/мысли. Непонятно что имеется ввиду конкретно под «событийной моделью».

igloev ()
Ответ на: комментарий от igloev

Да в принципе вся коммуникация должна выглядеть как обмен событиями через очередь. Например пользователь отправляет пост в тред. Ты кладешь сообщение в очередь, что пользователь совершил такое-то действие. Сервис ответственный за хранение реагирует на это сообщение и записывает его в бд. Дальше сервис ответственный за еще что-то выполняет еще какое-то действие. Я бы диаграмму нарисовал бы если бы мне за такие консультации платили :D

nikolnik ★★★ ()
Ответ на: комментарий от nikolnik

Забей. У него с понятиями ноль, а понту…
Посмотри его треды.

А ТСу - иди в гугл, читай и смотри видосы. Но ты же не умеешь в English, а то бы не спрашивал.

Тем более - это мысли. Херли с тобой говорить, когда ты неуч?

shleemypants ()

ну и говнокод...

индексы должны быть автоинкрементными.

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

запрос «дай из истории» должен быть вида «от этого айди и старше, только не отмеченные удаленными, лимит такой-то».

твой вектор должен содержать структуры с полем айди, где индекс этого элемента в векторе никак не связан с его айди.

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

ну и говнокод… индексы должны быть автоинкрементными.

Ты чё-то тред не осилил. Кода нет, индексов нет, реляционок нет.

но айдишник нужен автоинкрементный и уникальный.

Мы не в реляционке, а в самодельном тупом как бревно велосипеде. Розовые удобные и пушистые понятия из мира реляционок не прокатывают немножко.

Да и ещё у нас всё сильно распределено по сотням серваков и один чатик может физически лежать много где, это вообще отдельная жепь.

igloev ()
Ответ на: комментарий от shleemypants

А ТСу - иди в гугл, читай и смотри видосы. Но ты же не умеешь в English, а то бы не спрашивал. Тем более - это мысли. Херли с тобой говорить, когда ты неуч?

Норм бомбануло с ТС у тебя.

igloev ()

Пока запрос R1 летел на сервер по сети, на сервере было дропнуто первых 2 сообщения и все индексы съехали

что значит дропнуто? удалено из базы?

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

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

alysnix ()
Ответ на: комментарий от nikolnik

Да в принципе вся коммуникация должна выглядеть как обмен событиями через очередь. Например пользователь отправляет пост в тред. Ты кладешь сообщение в очередь, что пользователь совершил такое-то действие. Сервис ответственный за хранение реагирует на это сообщение и записывает его в бд. Дальше сервис ответственный за еще что-то выполняет еще какое-то действие. Я бы диаграмму нарисовал бы если бы мне за такие консультации платили :D

Известный подход, но модно и молодёжно. Это надо ещё серваков под эти перди городить. Наша СУБД в каком-то смысле уже и есть такая очередь. Плюс тут какбэ одна точка синхронизации и это грустновато немного. Нет, как решение - да, зачёт. Может занимать место в галерее РАБОЧИХ решений)

igloev ()
Ответ на: комментарий от alysnix

что значит дропнуто? удалено из базы? если «удалено» - не удаляй физически, а меть как удаленное.

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

другой вариант - мессага имеет уникальный в пределах чата uid, что делается инкерментом счетчика.

Да, но у нас физически не реализуемо. Распределённая СУБД ещё как-то нормально отрабатывает любые манипуляции с одним списком, но у этого списка нет никакого header, в котором можно было бы держать какой-то uid. Да, спасибо за идею, она годная, а реализуемость - проблемы нашего кактуса.

igloev ()
Ответ на: комментарий от igloev

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

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

ну и вы так делайте. это если так приспичило обращаться по индексу.

а потом проводите «сжатие чата», как база это делает.

alysnix ()

как [] в js/python

это назвается связный список, вполне четкая структура данных. Я бы начал с изучения этого

Из СУБД сообщения треда можно доставать по индексу (номеру от начала списка с нуля). Причём, индекс совершенно честный - как в тупом массиве на Си: если в треде было 1 млн сообщений, а потом модератор дропнул 100 с начала (0…99), то все индексы съехали на 100 вниз - называвшийся ранее 500 стал называться 400.

Офигенный план(нет), при удалении одной записи - апдейтить все что выше. Это хреново скалируется, тестируется, поддерживается. А накладных расходов - просто закачаешься,

дай [978…988]

зачем клиенту знать точные индексы? Ох а что будет когда окажется, что из отрезка нужны не все индексы? Эти камни даже не подводные…

какую-нибудь идею о борьбе с данным рассинхроном

генерирую - стоит начать с изучения базовых стуктур данных и алгоритмов.

Dred ★★★★★ ()
Ответ на: комментарий от igloev

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

Меня это печалит.

shleemypants ()
Ответ на: комментарий от shleemypants

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

С кем не бывает.

igloev ()
Ответ на: комментарий от Dred

то назвается связный список, вполне четкая структура данных. Я бы начал с изучения этого

Ну нет, это массив. У связного списка нет индексации никогда. Но на самом деле как это реализовано внутри js/python мы заранее знать не можем. На малом числе элементов оно может нам создать массив, который потом на лету переобуется в связанный-список-массивов и т.п.

Офигенный план(нет), при удалении одной записи - апдейтить все что выше. Это хреново скалируется, тестируется, поддерживается. А накладных расходов - просто закачаешься,

Никто не апдейтит всё что выше. У нас нет UPDATE, у нас нет реляционок, не стоит мыслить в этой парадигме. Уже всё давно поддержано и оттестировано. Изначально делалось как реализация массивов длины миллиард, в которые можно БЫСТРО втыкать в середину без сдвигов всей памяти, с чем и справилось. Использовалось для хранения логов. Теперь мы это пытались припахать в чатиках, но встретились с некоторыми вышеописанными приколами.

зачем клиенту знать точные индексы? Ох а что будет когда окажется, что из отрезка нужны не все индексы? Эти камни даже не подводные…

Написано выше - чтобы знать дошёл клиент до начала чатика или есть ещё что сверху запросить. Да и просто нарисовать позицию красиво в интерфейсе или номер страницы (если тред отображать как на форуме, а не как в чатике). Из отрезка нужны не все индексы - запроси их отдельно, хоть по одной штуке.

генерирую - стоит начать с изучения базовых стуктур данных и алгоритмов.

Тебя взбороли на примере [] уже, так что мы умнее тебя в этом.

igloev ()
Ответ на: комментарий от alysnix

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

ну и вы так делайте. это если так приспичило обращаться по индексу.

Ну в общем да. Метить в нашем случае выгодно. Ну, правда, не все НОРМАЛЬНЫЕ реляционки делают метку, многие и тупо сразу удаляют. Есть способы делать это суперпросто и дёшево, даже проще чем метку. Postgres из-за своей реализации MVCC решил копировать строки на каждое их изменение или удаление, а потом он их чистит в ходе VACUUM. В InnoDB такого нет, там всё inplace апдейтится/делитится, а старое пишется в какой-то redo-log ещё. Короче тысячи их (реализаций), не все метят.

Но всё ещё непонятно, что в нашем мире списко-массиво-велосипедов придётся делать, когда клиент зашёл в чатик, где первая половина чатика помечена «удалено» и в этот момент оно решило почистить удалённые, дропнув их физически со съездом индексов.

igloev ()
Ответ на: комментарий от igloev

знать не можем

или можем посмотреть в спеку, но кому оно надо, верно?

Теперь мы это пытались припахать в чатиках, но встретились с некоторыми вышеописанными приколами.

тоесть вас там больше одного кто это придумал? Ужас.

Написано выше - чтобы знать дошёл клиент до начала чатика или есть ещё что сверху запросить

странно что вы для такой великой задачи всю БД клиенту не реплицируете.

Тебя взбороли на примере [] уже

забавно это видеть от чувака который не может решить задачу уровня лабороторной второго курса…

Dred ★★★★★ ()
Ответ на: комментарий от igloev

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

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

В качестве альтернативы могу предложить хранить число дропнутых сообщений и пригенеривать их вначале когда отдаешь данные.

ya-betmen ★★★★★ ()
Ответ на: комментарий от Dred

или можем посмотреть в спеку, но кому оно надо, верно?

Спека дело такое - сегодня одна, а завтра гениальная новая версия и всё иначе. Вон раньше JS интерпретировался, а теперь в бинарный код на лету транслируется!

забавно это видеть от чувака который не может решить задачу уровня лабороторной второго курса…

Почему забавно. Если тебя взбороли второкурсники, то грустно тебе должно быть по идее. Хотя поддерживаю любые нестандартные эмоциональные реакции!

igloev ()
Ответ на: комментарий от igloev

Почему забавно. Если тебя взбороли второкурсники, то грустно тебе должно быть по идее. Хотя поддерживаю любые нестандартные эмоциональные реакции!

окей окей, чел, выдыхай.

Вон раньше JS интерпретировался, а теперь в бинарный код на лету транслируется!

и, собственно, что?

Dred ★★★★★ ()
Ответ на: комментарий от Dred

и, собственно, что?

Спеки в маня-языках сосут немного. Но тебя взбороли ещё раньше: ты сказал, что структура данных с доступом по индексу реализуется «связным списком». Можно конечно, но работать будет за O(n), а это печалькой может быть.

igloev ()
Ответ на: комментарий от igloev

ты сказал

пруфанешь?

что структура данных с доступом по индексу реализуется «связным списком»

так это ты питон в оп-пост запихал, ктож тебя тянул за язык

Спеки в маня-языках сосут немного.

все книги сосут когда читать не умеешь

Dred ★★★★★ ()
Последнее исправление: Dred (всего исправлений: 1)

Вариант 1)

На сервере держать логи дропов (точнее суммарный сдвиг) и вычислять сдвиг от индексов клиента (от момента логина клиента).

Вариант 2)

Блокировка. От клиента первое сообщение получает последние изменения и блокирует удаление/вставку. Второе сообщение – реальный запрос, по нему отдаются данные и разблокируются изменения.

Вариант 3)

Добавь-таки реальный ID (а не позицию в массиве). Если по запросу прилетели не все ID, идёт повторный запрос (возможно с небольшим запасом по количеству, если единичные удаления ожидаются часто).

monk ★★★★★ ()
Ответ на: комментарий от monk

Вариант 1)

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

Вариант 2)

Блокировки не вариант совершенно, т.к. данные лежат в СУБД, которая плевала на логику работы клиентов и их существование вообще. Оверусложнение опять же. Тем более, мы сдохнем, если в каком-то чатике кто-то устроит активность по входу-выходу - изменения начнут быть заблокированы основную часть времени. А если между «првым» и «вторым» запросом 200 мсек, т.к. клиент в жопе мира, то вообще жесть.

Вариант 3)

Ну самый логичный вариант, но мы не хотим ещё одно поле + ещё один индекс держать. Уж проще не удалять сообщения, а менить deleted как предлагалось выше. Тогда ничего не съезжает. Раз в неделю делать уборку мусора на особо загаженных чатиках и рассылать клиентам: «тут жопа, просьба переинициализироваться».

igloev ()
Ответ на: комментарий от igloev

Блокировки не вариант совершенно,

тут наверно optimistic locking надо.

делаешь у треда generation поле = 0, и гоняешь его туда-сюда с сервера на клиент, с клиента на сервер.

если кто-то что-то удалил увеличиваешь generation треда.

после чего все запросы клиентов с generation меньше текущего отбрасываешь с ошибкой - нужен рефреш.

я так в JWT смену пароля пользователем отрабатываю.

drsm ★★ ()
Ответ на: комментарий от drsm

Слишком жестоко. Ну и ещё у нас тупая KEY=value СУБД и хранить некое состояние чатика пришлось бы в отдельном key. И это разъедется с тем key, который хранит тот массив с чатиком…

igloev ()

Что-то вы дяденька по-моему заливаете. Вот пользователь заходит и берёт последние какие-то там как-то там непрочитанные. Вот и как он их берёт? И почем он их вообще находит – каков там процесс вообще?

kostyarin_ ★★ ()
Ответ на: комментарий от t184256

А, тогда все отлично. Теперь просто найми архитектора, знакомого с основами проектирования БД.

Не хочу Вас огорчать, но ТС – это тот деревянный чувак, который хотел себе майнер вместо капчи прикрутить. «Чтобы доказать, что Вы не робот, намайните мне биток. Осталось 2 года и 10 месяцев».

Какие-то примитивные подходы типа БД, индексов, DHT, event-driven, map reduce, архитектура, планирование и прочий хлам (ни в какое сравнение не идущий с массивами Си++) он вообще не считает даже за пыль.

Так что Вы потратили свой коммент зря. Мне очень жаль.

anonymous ()
Ответ на: комментарий от igloev

Ты в своем репертуаре. Сам изобрёл проблему, сам же и решаешь. А проблемы, меж тем, нет и не было.

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

WitcherGeralt ★★ ()

Индексы не нужны, делай без индексов. Тебе надо вычитывать 10 с конца? Вот и вычитывай. Делай tac, считай разделители. Впрочем дрочить на диске чатик тебе вообще не нужно, он весь влезет в память и всё, что надо, это иногда его скидывать. Хранить в виде linked list и держать для подключения ссыкли на то, докуда он там домотал.

crutch_master ★★★★★ ()
Последнее исправление: crutch_master (всего исправлений: 4)

На клиент придёт ответ: «not found» вообще. Уже потом конечно до клиента долетит нотифайка про «drop 0…99» и клиент всё поймёт

Объедини в протоколе уведомления с ответами на запрос.

Клиент на запрос всегда получает все сдвиги, которые произошли с предыдущего запроса. Если сдвиги влияют на результат, повторяет запрос.

monk ★★★★★ ()
Ответ на: комментарий от kostyarin_
out: subscribe chat name
in: ok current chat size 1000
out: get 989-999
in: notify new msg 1000 «First message after subscribe»
in: notify new msg 999 «Last message existed before subscribe»
in: notify new msg 998 «im doing good»
in: notify new msg 997 «how are you»
...
in: notify new msg 989 «The oldest msg of requestes messages»
igloev ()
Ответ на: комментарий от monk

Это надо помнить про клиента что-то. А там где пытаются плмнить - на фронтенд http-сервере такая же ситуация: нет полной картины, т.к. половина клиентов сидит через другой сервер http. Общая только эта наша примитивная СУБД, в которой о текущих коннектах что-то хранить конечно не хочется.

igloev ()
Ответ на: комментарий от anonymous

Не хочу Вас огорчать, но ТС – это тот деревянный чувак, который хотел себе майнер вместо капчи прикрутить. «Чтобы доказать, что Вы не робот, намайните мне биток. Осталось 2 года и 10 месяцев».

Ты наврал.

igloev ()
Ответ на: комментарий от igloev

Нет.

Вот именно. Значит тебе не нужен get n-m. Нужен get first(last), get next 10 (20,50,100). И у тебя уже не массив, а связанный список, не id, а ссылки.

crutch_master ★★★★★ ()
Последнее исправление: crutch_master (всего исправлений: 1)
Ответ на: комментарий от igloev

А откуда серверу знать, что там для меня next?

Оттуда же, откуда он помнит твои куки.

Зачем ему это помнить

Затем, что при чистке вилкой половины чата индекс съедет. Забыл уже?

если проще помнить клиенту

Нет, не проще.

crutch_master ★★★★★ ()