Как поделить большую таблицу личных сообщений?

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

Это первый шаг к масштабированию, а причина почему так случилось, это к сожалению недостаточное кол-во опыта :(

Я бы сделал так:
Завел бы дополнительную структуру вида user_id: shard_id, где shard_id — идентификатор базы данных в которой хранятся данные о пользователе(в нашем случае — сообщения)
Далее у нас появится некоторое количество баз данных, например, 100, каждая из которых хранит данные о 50 пользователей, в каждой такой базе данных есть таблица messages, в которой находятся сообщения пользователей, в итоге в каждой такой таблице будет находится не более миллиона записей. Теперь нам остается только узнать к какой БД нужно подключиться чтобы считать данные, для этого надо чтобы структура user_id: shard_id была доступна из любой точки приложения. Оптимальнее всего будет закэшировать её в памяти каждого сервера.

Вопрос реализации в таком случае меня больше всего и интересует.
Например. Пользователь 104 написал пользователю 30495, они находятся на разных Шардах. Где хранить письмо, на «чьем» шарде. В какой структуре хранить сообщения? И как каждый из пользователей будет получать доступ(письма) к инбоксу и аутбоксу?
Спасибо за помощь!

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

Тоже пришла такая мысль, побоялся дублирования. С другой стороны «бекап».
Тут встает вопрос изменения флагов — прочитано отвечено, надо будет на двух шардах, плюс редактирование не прочитанного сообщения… В любом случае спасибо за помощь! Можно будет попробовать реализовать в ближайшем будущем.

Подскажите такой вопрос, как на стадии логина когда вводиться email и пароль, определить на каком шарде живет пользователь? Можно делать хеш по мылу, и уже с ним что-то решать. Вот только как тогда миграцию тогда сделать :(

Могу предложить 2 варианта:
1) Завести отдульную шарду и в ней хранить только таблицы user_id, email и password, например по миллиону таких записей в одной таблице,(таблиц может быть несколько) при логине подключаться только к этой БД, и в цикле по всем таблицам искать емайл и пароль, возвращать id пользователя и дальше уже использовать только его. Вариант костыльный и не самый лучший.
2) Придумать или найти алгоритм получения хеша email-а, чтобы формула давала идентификатор шарды, в которой хранятся данные пользователя { int(hash(«email@mail.com»)) mod количество шард }

2-й вариант нравиться больше, только пугает время когда придется увеличить кол-во шард, надо будет предпринемать какое-то действия для перераспределение инфы исходя из нового кол-ва шардов, и тут уже не ясно к чему это может привести :( во всяком случае опыта такого не было, а в теории звучит как восстановление RAID массива при падении винта. Есть идеи как этого можно избежать?

Я, например, из презентации Пинтереста не понял как они умудряются получить этот самый ID, мне очень понравилось идея, что любые структуры пользователя можно переносить между базами внутри шарда ну и между шардами соответственно. Вот только я никак не смог понять как они «добывают» эту самую адресацию :(

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

Вот нашел еще одну презентацию, посмотрите, я думаю вам пригодится Практическое создание крупного масштабируемого web 20 c нуля

Также нашел описание такого подхода в блоге instagramm-a с примерами кода. Как я понял нужно копать в сторону UUID

спасибо, сейчас буду смотреть

классная презентация, спасибо.

Можете потом огласить результаты выбранного решения?

конечно, как завершим «переезд» сделаю пост

Что именно вы имеете ввиду?
Создать например таблицу Messages_07_2012 и переместить туда все письма за июль 2012 года? Как тогда быть если у пользователя есть переписка например в январе, марте, июле и августе. Делать селект из всех таблицы за все годы архивации?
Т.е. ситуация, открывается ИНБОКС, смотрим Message, потом Message_08_2012 и т.д. а вставляем только в Message?
Или вы что-то иное имели ввиду?

Нет. Я имел ввиду разделить текущую таблицу и добавить еще одну архивную. Переносить сообщения в архивную по истечению какого-то срока (например спустя 3 месяца) + дать возможность архивации самому юзеру.

Решение временное. Однако так как к архивной таблице будет обращений меньше (+ это архив, о чем можно уведомлять юзера), то таблица может сместить в два/три раза больше чем нынешняя, до возникновения проблемы повторно.

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

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

Можно ещё извратиться в архивную таблицу помещать все сообщения которых нет на первых трёх страницах инбокса.

Используем Redis вместо memcached но суть не в этом :) уже кешируем :)
Поправьте если где-то не там понял,
Message — пишем читаем новые сообщения
Message_archive — помещаем туда все где created_date > now()-1 month
Message_month_year или Message_quart_year — более глубокие архивы

Теперь вопрос на засыпку, как это реализовать?
На уровне контроллеров переносить в архив, а скриптами в «поздние» архивы или все скриптами?

1. только created_date < now()-1 month
2. переносить из таблицы в таблицу скриптами. раз в день.
3. в контроллере который показывает inbox сделать руками логику которая начинает читать из Message_archive, если сообщения в Messages кончились, а далее из таблиц Message_month_year (если человек упорно жмёт на pagination)

если чтото будет смущать можно сделать ещё таблицу в которой для каждого (user, month, year) будет записано кол-во сообщений.

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

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

я написал выше завести табличку (user_id, month, year, count) (только для архивных таблиц).

да-да, спасибо. предыдущий камент видимо отправил без обновления страницы.
попробуем этот вариант, видимо он самый актуальный для нас

Этот коммент, имхо, можно пометить как «решение».
Даже если у вас есть индексы, то при таких размерах они помещаются целиком в оперативке и жрут память. А может и не помещаются и ложатся на диск… (Это надо уже на месте смотреть)

Я вам рекомендую принудительно всем пользователям сделать «Архив», и переносить в него записи которым больше трех месяцев. Пользователь, залезая в папку «Архив» подсознательно ожидает некоторые подтормаживания + вам не придется переделывать существующий механизм. Лишь продублировать его на работу с другой таблицей, и сделать перемещения между табличками. В архиве я бы отключил автоинкременты, чтобы msg_id не сбивать.

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

И уже потом отрефакторил, перенеся subj в отдельную таблицу.

Индексы уже сделали для всего чего можно. Места занимают больше чем сами данные :( На такой таблице(по размеру) при постоянном r\w в нее, уже вряд ли спасут какие-то индексы.

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

P.S. Строить индекс на такой таблице значит выключить сайт на несколько часов — это неприемлемо к сожалению :(

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

vsespb прав, хочется избавиться от суммарного кол-ва записей в таблице, т.к. партиции уже просто не спасут :(

> тогда запросы будут равномерно распределены по всем партициям, это сводит выгоду от партиций на нет
Как раз наоборот. Физическая близость записей с одним id получателя в рамках одной партиции и даст прирост производительности. Партиции с точки зрения хранения суть разные таблицы — разделяя одну огромную таблицу партициями по хешу ключа наиболее частого поиска, вы по сути получаете N маленьких таблиц, над которыми ваши типичные поисковые выборки будут крутиться быстрее, в силу меньшего кол-ва записей в партиции и возможности сразу выбрать нужную партицию для поиска и ограничиться только ею (все сообщения одного пользователя локализованы в ней). Если раньше для поиска сообщений одного пользователя приходилось делать фулскан большого индекса (если он был) и access by row id к таблице либо фулскан всей таблицы (если не было индекса), то с учетом эквипартицированного индекса время скана уменьшится в N раз, где N кол-во партиций.

дело в том что пользвателей, например 10 000, а партиций будет меньше 10 000. например 100. в итоге все запросы распространятся равномерно по партициям.

не слышал что в этом случае у mysql будет выигрыш (если суммарный объём данных для просмотра точно такой же как был, но теперь есть партиции).

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

Есть запросы:
select * from message where to_id = USER_ID — инбокс
select * from message where from_id = USER_ID — аутбокс
select * from message where (to_id = USER_ID and from_id = SENDER_ID) or (to_id = SENDER_ID and from_id = USER_ID) — получить историю переписки

Поделить по партициям спасет или инбокс или аутбокс. Запросов в инбокс больше, где-то 50%, остальных по 25%

Вы не подумайте, я за партиции, просто при таком кол-ве записей и такими запросами к сожалению это не выход :(

Представьте, у вас за день миллион запросов. И каждый запрос обрабатывался в среднем за T тиков процессора, ищя по большим индексам одной таблицы. А с партициями каждый запрос работает в своей, производя поиск по меньшим индексам, что сокращает количество тиков на запрос.

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

> столько же тиков (или больше) прибавляется учитывая что mysql выбрирает нужную партицию перед запросом.
Выбор партиции — копеечная операция — нет там никаких «столько же тиков (или больше)».
@ tyzhnenko — имхо вам надо перепланировать таблицу:
user_id — принадлежность сообщения пользователю
counterparty_user_id — вторая сторона переписки
message_direction (IN/OUT) — тип сообщения относительно владельца
Да, записей будет в два раза больше, но:
1) ведь так оно и должно быть, иначе в вашем текущем раскладе получается что если пользователь удаляет сообщение из аутбокса (решил почистить), оно пропадает из инбокса его визави :)
2) все сообщения одного пользователя будут локализованы в одной партиции

> vsespb иначе бы можно было автоматически всем таблицам делать партиции и партиции партиций и всё было бы быстрее
Только не автоматически, но именно так и делают там, где оно применимо. Либо на этапе дизайна (с расчетом на будущую read capacity), либо, как сейчас, аврально, когда производительность уткнулась. Бывают ситуации, где и не применимо, тогда выбирают другие способы оптимизации — редизайн с денормализацией, введение материализованных представлений, функциональные индексы и т. п. не говоря о банальном изучении планов запросов и выбора лучших вариантов получения тех же самых данных

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

> есть пруфлинк что в таком виде партиции улучшают производительность?
[showing off]Есть 10 летний опыт работы с реляционными СУБД поддерживающими не только партицирование, равно как и понимание этого механизма :)[/showing off]
Вот вы уповаете на индекс, но кроме операции чтения из индекса следующим шагом будет чтение набора записей из большой таблицы по физическим адресам строк, полученных из индекса. А где они расположены в этой таблице? Да где угодно, скорее всего равномерно по ней рассыпаны по мере исторического поступления в нее, т.е. фрагментированы. Приходится читать много блоков с диска с разных мест, даже если в каком-то блоке всего одна интересующая запись, этот блок читается целиком — дополнительные i/o. Какие преимущества тут дает партицирование? Записи в рамках одной партиции расположены _компактно_ физически друг к другу + в некоторых субд есть еще возможность задать им специфические параметры хранения — например раскидать по разным дискам.

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

bugman
Спасибо, хорошая идея как перепланировать таблицу. Понравилась очень. Пришла следующая идея как реализовать, интересно ваше мнение.

Message
msg_id — ID сообщения
owner_user_id — владелец сообщения
partner_user_id — собеседник
date — дата сообщения
direction — направления сообщения

Message_status
msg_id — ID сообщения
status {new, read, replied} — статус сообщения

Message_body
msg_id — ID сообщения
body — тело сообщения

Message шардиться по owner_user_id.
Message_status и Message_body по msg_id

Имеем у каждого свои письма, при этом общие для всех писем тело письма и статусы. Вот только есть вопрос, оставлять date в Message или перенести в Status. С одной стороны он полезнее в Message можно сделать order с другой стороны это общее для двух пользователей информация которая может жить в Message_status.

P.S. Кстати, записи из таблиц не удаляются ставиться флаг удаления. быстрее т.к. индексы не переписываются

Вопрос, что будет быстрее — каждый раз джойнить Message с Message_Status чтобы показать статусы сообщений, или все-таки продублировать статусы в обоих записях (что дает дополнительную гибкость) и поддерживать синхронизацию статусов двух связных сообщений например триггером.

bugman
да и join подойдет только в рамках одного шарда, если учитывать развитие на будущие, то join'ов все равно придется отказываться :/
тригер тоже выход если оставаться в рамках только одной базы, а если случится так что данные будут разнесены на разные шарды и разные базы. например какой шард вышел из строя и его данные перенесли в другие базы из бекапа.

*сорри, 100м прочиталось как 100мб.
Недоумение по поводу тормозов ушло.
Совет попилить таблицу на 2 части — auto_id, from_id, to_id и «остальное» — в силе. Это СИЛЬНО уменьшит основную таблицу по которой идут выборки, как следствие даст прирост скорости, и выборки и вставки и перестроение индексов — все будет резвее на малом объеме.

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

Это СИЛЬНО уменьшит основную таблицу по которой идут выборки, как следствие даст прирост скорости, и выборки и вставки и перестроение индексов — все будет резвее на малом объеме.

Глупости. Размер индекса (количество сообщений) не меняется — скорость перестроения индекса тоже. Отчасти это может помочь в случае кластерного индекса, но не в данной ситуации (обновлений индексного поля нет, данные на диске не перемещаются). Уменьшение таблицы даст толк либо при fullscan, либо при малом размере таблицы, чтоб она полностью помещалась в кэш. Ни то, ни другое, в данном случае не верно. Разделение таблицы увеличит в два раза количество random seek для извлечения данных — отличная анти-оптимизация.
Если сообщения хранятся как TEXT — их нет смысла хранить в другой таблице, они и так будут лежать отдельно от основных данных.

Была мысль вынести некоторые поля в другую таблицу

В смысле и архивацию и денормализацию(кажется это так называется)

Это как раз процесс обратный денормализации. Вместо прироста производительности получите дополнительный JOIN и, как следствие, дополнительный random seek.
Что касается архивации — вы для начала выясните откуда берутся тормоза. Архивация поможет только при полных выборках, (вместо них делайте постраничный вывод), либо при неиспользуемых индексах (explain делали?).

в первом случае можно использовать построчные выборки, вместо join'a. тем более если в дальнейшем планировать шардинг, от join'а в любом случае придется избавляться.

select msg_ids from message where owner_id = USER_ID
select * from message_status where id in ( foreach(msg_ids) )

про explain написал в комментарии к вашему ответу.

Запрос например такой

select * from message where to_id = user_id and status = 'new'
или такой
select count(*) from message where to_id = user_id and status = 'new'

индекс сделан по to_id и status. чем еще может помочь explain в таком случае?
скорость выполнения запроса по разному, в зависимости от нагрузки. от 0.2 секунды до 1-2 секунд, это без ожидания локов. Смотря сколько сообщений у пользователя.

Таблица myisam.

> explain select * from msg where to_id = USER_ID and status='new';

select_type | table    | type | possible_keys   | key             | key_len | ref   | rows | Extra      
------------+----------+------+-----------------+-----------------+---------+-------+------+------------
SIMPLE      | msg      | ref  | idx_toid_status | idx_toid_status | 3       | const |  893 | Using where


> explain select count(*) from msg where to_id = USER_ID and status='new';


select_type | table    | type | possible_keys   | key             | key_len | ref   | rows | Extra      
------------+----------+------+-----------------+-----------------+---------+-------+------+-------------------------
SIMPLE      | msg      | ref  | idx_toid_status | idx_toid_status | 3       | const |  893 | Using where; Using index

> select count(*) from msg where to_id = USER_ID and status='new'; 

count(*) 
---------
    1133

Что-то еще интересует. Спасибо за то что откликнулись.

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

из того, что вижу — кол-ва сообщений с разными статусами у юзера (10 прочитанных 5 непрочитанных) можно сделать аттрибутами юзера, сопровождая их на триггерах. Но перед тем, надо посмотреть на отношение (кол-во и тяжесть) между запросами «посчитай мне кол-во непрочитанных» и апдейтами «пометь как прочитанное»

MyISAM для таких объемов выбрасывайте нафиг. Во-первых блокировки, во-вторых надежность. Внезапно упадёт сервер — и наслаждайтесь REPAIR TABLE на ваших 100М записей. Планируйте миграцию на InnoDB. Ругани в сторону MyISAM в хайлоаде всегда хватало, вот, почитайте.

select * from msg where to_id = USER_ID and status='new';
Нужен ли вам вывод всех сообщений за раз? Сделайте постраничную навигацию, как минимум с LIMIT x,y. А по возможности — кнопки вперед/назад и выборки по индексу. Идею можете почерпнуть отсюда.

Выбрать несколько сотен строк по индексу — не такая уж большая проблема для любой БД. Вы упираетесь либо в блокировки, либо в винт. Так или иначе, скорость должна меняться под нагрузкой. Включите профайлинг, посмотрите как меняется скорость выполнения запросов днем/ночью.
С блокировками поможет InnoDB, с винтом — масштабирование, как вертикальное, так и горизонтальное. С горизонтальным в mysql сложнее, чем во многих nosql, можете начинать посматривать на них.
Если хоститесь в облаке — можете для сравнения попробовать реальное железо. У большинства облачных провайдеров, винты — узкое место.

Ну и status лучше хранить как tinyint, чуток уменьшит размеры индекса (хотя может у вас там enum, тогда не обязательно).

как раз от такого REPAIR TABLE и хотим избавиться. Переход на InnoDB будет скорее всего во время дробления таблицы.
limit используем для пейджинга, count(*) для того чтобы показать счетчик :)

скорее всего вы таки правы про блокировки, надеюсь прорвемся когда будет InnoDB.
status = emum — вы правы.

bugman
У этого пользователя было 1133 новых сообщения на момент селекта. Всего больше.
Кол-во запросов count — много :(