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) и это там ничему не противоречит, но я так не хочу чё-то пока.



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

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

get 2,5,7,9 не бывает, но скажем возможна ситуация: при чатике длиной 1 млн get(1000, 1025) - например когда архив этого чатика листают постранично через веб.

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

Книжки по распределенным алгоритмам/приложениям покури.

Докажи, что там есть ответ на данный вопрос. Бугага.

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

бугога

Ты ж не читал, но осуждаешь... да еще на лор пришел ответы искать, а не в гугл :) бугога

Докажи

У нищих слуг нет.

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

но скажем возможна ситуация: при чатике длиной 1 млн

Чатик длинной 1 млн - это помойка в которой ничего не возможно найти, ну да ладно, допустим.

например когда архив

Архив - это уже другая сущность. Его можно считать массивом. Не нравится, что две реализации? Ну так в этом ничего такого нет. Что лучше подходит, то и должно использоваться.

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

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

Я достаю из базы, из ключа KeyLastChatOffsetUID1773 значение 1000 и понимаю, что у юзеру 1773 надо грузить 1000 и выше. Пока я про это думаю, там уже дропнули первые 100 мессаг. И то, что у юзера уже есть он получит ещё раз, т.к. имеющаяся у него мессага 1000 уже стала 900 или как там.

Та же проблема, без автоинкрементного индекса у чатика

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

Архив - это уже другая сущность. Его можно считать массивом. Не нравится, что две реализации? Ну так в этом ничего такого нет. Что лучше подходит, то и должно использоваться.

Конечно же 2 копии - ненужно

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

Конечно же 2 копии - ненужно

Две копии чего? У тебя на 1М записей архив или живой чатик?

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

Пока я про это думаю, там уже дропнули первые 100 мессаг

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

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

Ну так делай всё по очереди, а не так, чтобы все треды имели одну бд разом.

Сорян, не скейлится такое. Изначальная постановка - 1000 фронтенд серваков и одна СУБД (тоже распред., но однопоточная-для-каждого отдельного key/чатика)

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

Сорян, не скейлится такое.

Всех тормозить надо только в случае дропа и двигать индекс. В остальных - все работает, как работало. Так что всё норм.
Компухтер, кстати, работает последовательно, если ты не забыл.

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

Общая только эта наша примитивная СУБД

Сделай ещё общую очередь сообщений. Или уведомления клиентом сама СУБД в один поток рассылает?

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

Сделай ещё общую очередь сообщений. Или уведомления клиентом сама СУБД в один поток рассылает?

Уведомления: когда один из 1000 вебсерверов сохранил в чатик мессагу, ему атомарто от базы приходит «ты сохранил в меня месагу с индексом 7000». Далее это уходит по внутренней сети всем вебсерверам и они шлют клиентам «опа чувак, тут новая месага 7000».

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

Омг, ну и индусятина. Зачем это, если есть таймстамп?

шлют клиентам «опа чувак, тут новая месага 7000»

Вместо того, чтобы отправить само сообщение, ололо какое-то.

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

если есть таймстамп

Где ты его тут увидел… Да и тиместамп бы понадобился 64 битный nano

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

чтобы отправить само сообщение

Это и есть само сообщение:

id : 7000, msg : «ты дурак», timestamp : 7766554433, uid : 554, something : bubu

Но timestamp ни в каким индексе не находится.

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

месагу с индексом 7000 (id : 7000)

timestamp ни в каким индексе не находится

Какая-то срань с терминологией.

Первое звучит как автоинкркментный уникальный идентификатор (что крайне проблематично в распределённой системе), то ли как порядковый номер в массиве (индекс). Второе как сущность БД.

Что ты имеешь ввиду? Называй вещи своими именами.

WitcherGeralt ★★
()

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

Всё уже придумано, запрограммировано и работает:

3 Architecture

Matrix defines APIs for synchronising extensible JSON objects known as «events» between compatible clients, servers and services. Clients are typically messaging/VoIP applications or IoT devices/hubs and communicate by synchronising communication history with their «homeserver» using the «Client-Server API».

3.4 Event Graphs

Events exchanged in the context of a room are stored in a directed acyclic graph (DAG) called an «event graph». The partial ordering of this graph gives the chronological ordering of events within the room. Each event in the graph has a list of zero or more «parent» events, which refer to any preceding events which have no chronological successor from the perspective of the homeserver which created the event.

https://matrix.org/docs/spec/

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

, то ли как порядковый номер в массиве (индекс). Второе как сущность БД.

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

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

И индекс в массиве и сущность в бд «индекс» решают одну и ту же задачу. Интересует лишь данная семантика, а не физическаяреализация

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

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

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

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

Ладно, срача разводить не буду, но для себя сделал вывод, что ты конкретно так плаваешь в предмете. Посоветую лишь постараться не изобретать смешных трёхколёсных велосипедов.

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

Ладно, срача разводить не буду, но для себя сделал вывод, что ты конкретно так плаваешь в предмете.

Если ты приходил поделать выводов для себя, то ты не интересен.

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

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

Да. Ну, смотря какие индексы. Индекс «номер с начала списка» проваливает, а индекс «по nanotimestamp» - норм.

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

Ну и нужен индекс по uid. А мы ещё в точке «не хочу новых индексов».

Пока что решение «не удалять, а метить deleted» выглядит рабочим. И места не жрёт нифига (если текст выпиливать при удалении нахрен) и однозначненько.

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

Приходил разобраться, что тебе нужно и подсказать по возможности. Просто ты — Д’Артаньян, подсказывать нет смысла. Все равно слушать не будешь.

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

Приходил разобраться, что тебе нужно и подсказать по возможности. Просто ты — Д’Артаньян, подсказывать нет смысла.

Называй вещи своими именами - ты обосрался на понятии «индекс», ушёл в теорию и потонул.

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

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

Вот ты якобы владеешь, а доказать этого не смог. И чё толку владеть, не умея общаться. Обоссали тебя в результате и ты обиделся.

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

Отстой какой-то. Придумывание проблем ради проблем.

Очередной сраный пятизвёздочник с мозгом мыши оценил обстановку и выдал постановление.

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

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

Вот толку упёртому дурачку что-то объяснять? Работаешь эникемм за корку хлеба а самомнение как у Торвальдса.

WitcherGeralt ★★
()

Ну вот скажи, ТС, разве это корм?

Я же предупреждал. Сплошной переход на личности, ноль по теме.

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

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

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

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

Это не суть вопроса. Это «твои мысли», которые намекают.

Чё за мысли там у меня ты увидел. Поделись с друзьями, не держи в себе.

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

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

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

Ну, и главное, в чём смысл этой распределённости, которая промелькнула? Очень высокая нагрузка? Децентрализация?

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

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

Это заслушано. Да, понятное распространённое решение. Пока отказался потому, что считаю себя хитрожопее, чем данное мейнстримовое решение по причине «наша СУБД». Причины «наша СУБД» такие:

  1. Наша СУБД уже издревле умеет очень быстрые (драматически быстрее любого INSERT в mysql/postgres) массивы, которые:
  2. Эти массивы классно ложатся на сущность «тред», который по сути всегда линейная последовательность событий. Если бы они не удалялись, то проблем вообще никаких бы не было.
  3. Эти массивы драматически быстро работают на типичных чатиковых/тредовых/форумных запросах «дай поддиапазон месагов» или «скажи длину массива» (чтобы пагинацию нарисовать).
  4. Добавлять сюда какую-то очередь выглядит немного «козе боян», который вносит миллисекунду задержек и лишнюю точку отказа. У нас этот «массив» и так почти та самая очередь. Причём мы даже в нашей СУБД можем немного подхачить «массив», научив его выкидывать спереди всё, что запросили, получив на ровном месте свою Kafka как-бы, но зачем.

Нотификации о новых месагах прекрасно работают, когда нет удалений: в конец массива в нашу СУБД сыплются объекты, СУБД возвращает на каждый такой insert ID (индекс) этого объекта и объект с индексом тупо улетает всем клиентам в виде нотификации (один веб-сервер шлёт это событие остальным, остальные тупо повторяют клиентам, если там есть клиенты в этом чатике).

Единственная хрень возникла при удалении сообщений - и то лечится не удалением сообщений из массива, а меткой «deleted». При существовании такого решения городить какие-то альтернативные БД с очередями как-то туповато.

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

Ну, и главное, в чём смысл этой распределённости, которая промелькнула? Очень высокая нагрузка? Децентрализация?

Она легко сейчас делается, отказываться от неё странно на ровном месте, когда ей уже сейчас ничего не препятствует. Желательно сохранять. Это хорошее качество системы. Ну скажем, приходят к тебе чуваки, говорят: давай из твоего сервиса сделаем мессенджер нового образца и будем впаривать корпоративные доступы, а я такой «сорян у меня не масштабируемо» и будет грустно. А так можно докинуть серваков и стать большим.

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

Эти массивы классно ложатся на сущность «тред», который по сути всегда линейная последовательность событий. Если бы они не удалялись, то проблем вообще никаких бы не было.

Ну так делай вместо удаления обнуление, и при чтении игнорируй.

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

Сраные у тебя штаны.
А ты чаты-треды кидаешь туда, где ими трудно управлять. Не потому, что это сверхзадача, а потому, что твоя СУБД не для них.

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

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

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

Как я понял, у тебя поблема с БД, потому и спросил, что конкретно ты подразумеваешь под индексом.

Ну не в БД, а в архитектуре всего. Индекс в БД понятно что - структура данных рядом с какой-то хранилкой (таблицей, спейсом документов и т.п.), ускоряющая поиск в этой хранилке по каким-то параметрам/ключам и т.п. Но как ни странно, слово индекс как номер массива в языке СИ и слово индекс как «структура данных B+Tree в InnoDB, с кортежем (gender, age) в качестве ключа» означают совершенно одно и то же - «средство быстрого доступа к элементу», поэтому в том разговоре семантическо было всё корректно. Да, у меня «проблемы с БД», где у БД «такой индекс, что он сцуко едет, когда что-то удаляют». Зато в остальных случаях он сцуко такой быстрый, что переедь я на PostgreSQL я проиграю в 10-100 раз по скорости доступа к данным. А фичу «нас очень дорого ДДОСить» терять не хочется.

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

Ну так делай вместо удаления обнуление, и при чтении игнорируй.

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

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

Сраные у тебя штаны. А ты чаты-треды кидаешь туда, где ими трудно управлять. Не потому, что это сверхзадача, а потому, что твоя СУБД не для них.

Да вроде нормально и естественно управлять ими как тем, чем они и являются - массивом мессагов.

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

призёры олимпиад по матану

...используют более удобные для этой задачи СУБД.

И, кстати, INSERT используется очень ограничено - все пацаны используют в худшем случае BULK INSERT, в лучшем случае - формируют буфер с csv и грузят его с локом таблицы.

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

…превращающимся в список со случайным порядком…

Зачем. Обижаешь. Порядок добавления. Написал месагу - запушилась в конец массива.

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

городить какие-то альтернативные БД с очередями как-то туповато

Универсальность — всегда плюс. Шаг вправо, шаг влево, твою замечательную БД придётся конкретно так дорабатывать, а скорее всего и выбросить рано или поздно.

Насчёт очередей ты в корне не прав. Они являются не точкой отказа, а точкой масштабирования, причём они как правило — самая надёжная часть системы, так как умеют в кластер из коробки. Шардинг, балансировка, подтверждение доставки… Из своего велосипеда ты в такую вундервафлю никогда в жизни не сделаешь.

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

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

И, кстати, INSERT используется очень ограничено - все пацаны используют в худшем случае BULK INSERT, в лучшем случае - формируют буфер с csv и грузят его с локом таблицы.

Не, это грустно. Даже MySQL InnoDB умеет за 500 микросекунд заинсертить строку. Зато в бинлоге останется сразу. Можно конечно пушить месаги в персистентную очередь, а потом из неё флашить в мускуль булк-инсертами, но это ведь всё оттого, что у тебя нет INSERT-сразу-в-базу за 1 микросекунду. А если он есть, зачем мне очередь.

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

Универсальность — всегда плюс. Шаг вправо, шаг влево, твою замечательную БД придётся конкретно так дорабатывать, а скорее всего и выбросить рано или поздно

Да у меня типичное key=value, где value может быть массивом, который не надо переписывать целиком при инсерте в любое его место. На обычном key=value делается что угодно. Могу запихнуть в value кортеж из нескольких колонок - и вуаля, у меня уже реляционка. Ну не совсем, т.к. я не умею JOIN/foreign key, но такой кал обычно в высоконагруженных проектах не применяется. Распределённые транзакции на key=value я делать умею, бабки со счёта A на счёт Б переводить без проблем.

Насчёт очередей ты в корне не прав. Они являются не точкой отказа, а точкой масштабирования, причём они как правило — самая надёжная часть системы, так как умеют в кластер из коробки. Шардинг, балансировка, подтверждение доставки… Из своего велосипеда ты в такую вундервафлю никогда в жизни не сделаешь.

Есть опыт делания таких вафлей, ничего сложного в использованных словах не увидел. Персистентный хеш и шардинг и я умею… Что за подтверждение доставки? Кому? Зачем оно мне. Я и так знаю, что я записал в свою БД или не записал. Если записал - отправляю клиенту delivered(true) и все счастливы. Без посредников/очередей. Репликацию я умею тоже, журнал тоже.

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

Ну на практике играет. Иначе бы всякие гуглы не жили на своих странных решениях, написанных на сишечке. При 100 серверах сэкономить два - уже очень круто. А что говорить про тысячи их. Опять же, утверждается, что всё что угодно хранится в key=value.

igloev
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.