On 3/7/12, Ruslan Zakirov <[email protected]> wrote: > Мы мапим ключи на несколько нод, допустим это пользовательские > акаунты. Нужно решить вопрос добавления нод. > > Ключей много, нод мало, то есть нужна карта соответствия. Можно по хэш > функции, а можно и другим способом, например: массив граничных > значений. Бинарным поиском можно найти ноду за O(lg(n)). Из > преимуществ - можно вычленить один ключ в отдельную записьв карте. > Пользуясь преимуществом можно переносить ключи между нодами по одному. > > Возникает задача блокировки отдельных записей в карте, что может > повысить общую нагрузку. Блоки ключей в карте блокируются, только > когда меняется нода блока, а проверяется блок только при записи. > Алгоритм переноса следующий: > > 1) Блокируем саму карту > 2) Отщепляем определенные ключи в отдельную запись карты. > 3) Снимаем блок > 4) Блокируем отщепленную запись > 5) Копируем данные > 6) Меняем запись в карте > 7) Снимаем блок > 8) Удаляем данные из старой ноды (тут нужно быть уверенным, что никто > уже не читает эти данные и не произойдет обратной миграции) > 9) При необходимости повторяем первые три пункта с объединением блоков в > карте > > Если объем данных для ключа небольшой, то миграция займет разумное время. > > Разумное решение? Не знаю. Возможно есть еще интереснее и полезней.
Не очень. Похоже на идеи из Chord/DHash, но это для p2p систем, не для датацентров. Хотя с блокированием ни для чего не подойдет. Мы не можем себе позволить копировать пол базы из ноды по одной записи в датацентре, это будет слишком большая нагрузка на дисковое IO. Но это приемлемо в p2p, где дисковое IO вообще не проблема, и даже наоборот, там важнее уменьшить трафик. Шардинг же мапит ключи на шарды (куски), а шарды на ноды, причем количество шард заранее известно и задается один раз. Это позволяет как перемещать шарды между нодами с небольшими затратами, так и избавиться от сложных алгоритмов перераспределения данных, соответственно повысив надежность. > Вопрос репликации не рассматривается. Он решается отдельно и никак не > противоречит с приведенным вариантом решения. Как его решить отдельно? Допустим, что делать если отпал мастер для какой-то группы ключей? Или если там все равноправны и одна нода упала, то как узнать, на какой из реплик для какого-то ключа данные правильные, а на какой нет? Это уже не тривиально, нужно иметь какой-то порядок в системе (lamport timestamp, vector/matrix clock), чтобы четко знать, на какой ноде запись самая свежая. Или как-то выбирать мастера (paxos). В общем все очень тесно связано. -- Moscow.pm mailing list [email protected] | http://moscow.pm.org
