Ищем распределенную схему блокировки

10

Мне нужно придумать собственный механизм рекурсивной блокировки объектов \ шаблон для распределенной системы в C #. По сути, у меня есть многоузловая система. Каждый узел имеет эксклюзивные разрешения на запись для n-го числа состояний. Такое же состояние также доступно в форме только для чтения, по крайней мере, на одном другом узле. Некоторые записи / обновления должны быть атомарными во всех узлах, в то время как другие обновления в конечном итоге станут согласованными в процессе фоновой репликации, очередях и т. Д.

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

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

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

thing.AquireLock(LockLevel.Write);

//Do work

thing.ReleaseLock();

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

public static void AquireLock(this IThing instance, TupleLockLevel lockLevel)
{ 
    //TODO: Add aquisition wait, retry, recursion count, timeout support, etc...  
    //TODO: Disallow read lock requests if the 'thing' is already write locked
    //TODO: Throw exception when aquisition fails
    instance.Lock = lockLevel;
}

public static void ReleaseLock(this IThing instance)
{
    instance.Lock = TupleLockLevel.None;
}

Чтобы уточнить пару деталей ...

  • Все коммуникации осуществляются по протоколу TCP / IP с использованием протокола двоичного запроса / ответа.
  • Нет промежуточных технологий, таких как очереди или базы данных
  • Центрального главного узла нет. В этом случае механизм блокировки определяется инициатором блокировки и партнером, который выполнит запрос с некоторой формой тайм-аута для управления его поведением.

У кого-нибудь есть предложения?

JoeGeeky
источник
Блокировки, как правило, стандартная функция в большинстве систем. Я думаю, что это также есть для C #. (Результат поиска в Google: albahari.com/threading/part2.aspx ) Вы пытаетесь достичь чего-то большего, чем базовый мьютекс или семафор?
Дипан Мехта
2
@DipanMehta Извините, я должен был рассмотреть это более четко. В узлах я назвать машины по сети. Мое понимание Mutex и семафоров состоит в том, что они являются блокировками для всей машины ( например, кросс-процесс ), а не блокировками, которые могут распространяться между компьютерами в сети.
JoeGeeky
@JoeGeeky Ваш вопрос здесь по теме и, возможно, будет слишком теоретическим для переполнения стека . Если вы хотите переспросить его там, вы можете, но вам понадобится более выраженная в коде формулировка.
Адам Лир

Ответы:

4

Спасибо за разъяснения.

В этом случае я бы порекомендовал использовать модель публикации / подписки. Протокол распределенной блокировки Google Chubby (реализация Paxos )

Я никогда не использовал Paxos (или Chubby), но , как представляется , реализация с открытым исходным кодом здесь .

Если это не сработает, вы можете реализовать свою собственную версию Paxos, используя, например, одного из обычных подозреваемых с точки зрения библиотек сообщений: библиотеки с нулевой очередью сообщений , RabbitMQ или ActiveMQ .


Предыдущий ответ:

Большинство предложений по SO ( [A] , [B] ) касаются использования очереди сообщений для обеспечения блокировки между компьютерами.

Ваш AcquireLockметод помещает что-то, идентифицирующее объект блокировки, в очередь, проверяя предыдущие случаи блокировок до успеха. Ваш ReleaseLockметод удалит объект блокировки из очереди.

Пользователь SO Атлантис предлагает, в этой должности , должности Джефф Ключа для некоторых деталей.

Питер К.
источник
Спасибо, но эти решения не подойдут, так как у меня нет центрального мастера, базы данных или очереди. Я обновил вопрос с некоторыми дополнительными деталями, чтобы уточнить некоторые из этих деталей.
JoeGeeky
Я не смогу использовать эти продукты напрямую, поскольку уже существует четко определенный протокол, который я должен использовать для всех соединений между узлами, но у Chubby и Paxos могут быть четко определенные шаблоны, из которых я могу извлечь уроки. Я взгляну.
JoeGeeky
@JoeGeeky Да, ссылка Paxos имеет диаграммы последовательности, которые могут позволить вам реализовать ее, используя предпочитаемую линию связи.
Питер К.
Хотя это и не был прямой ответ, чтение всего материала Chubby и Paxos помогло мне определить собственное решение. Я не использовал эти инструменты, но смог определить разумную модель, основанную на некоторых из их концепций. Спасибо.
JoeGeeky
@JoeGeeky: Приятно слышать, что это была хоть какая-то помощь. Спасибо за галочку.
Питер К.
4

Мне кажется, у вас есть несколько смешанных технологий:

  • коммуникация (на которую вы в основном полагаетесь как на 100% надежную ... которая может быть фатальной)

  • блокировка / взаимное исключение

  • таймауты (с какой целью)?

Слово предупреждения: таймауты в распределенных системах могут быть чреваты опасностью и сложностью. Если они используются, их следует устанавливать и использовать очень осторожно, потому что неразборчивое использование тайм-аутов не решает проблему, оно просто откладывает катастрофу. (Если вы хотите увидеть, как следует использовать таймауты , прочитайте и поймите документацию по протоколу связи HDLC. Это хороший пример подходящего и умного использования в сочетании с умной системой кодирования битов, позволяющей обнаруживать такие вещи, как линия IDLE) ,

Некоторое время я работал в многопроцессорных распределенных системах, подключенных по каналам связи (не TCP, что-то еще). Одна из вещей, которые я узнал, заключалась в том, что в качестве грубого обобщения есть несколько опасных мест для мультипрограммирования:

  • зависимость от очередей обычно заканчивается слезами (если очередь заполняется, вы попадаете в беду. ЕСЛИ вы можете рассчитать размер очереди, который никогда не заполнится, и в этом случае вы, вероятно, могли бы использовать решение без очереди)

  • опора на блокировку - это болезненно, попробуйте и подумайте, есть ли другой способ (если вам нужно использовать блокировку, посмотрите литературу, многопроцессорная распределенная блокировка была предметом многих научных работ последних 2-3 десятилетий)

Если вам нужно использовать блокировку, то:

Я ПРИЗНАЮ, что вы будете использовать тайм-ауты только в качестве средства восстановления последней инстанции - т.е. для обнаружения сбоя базовой коммуникационной системы. Далее я предполагаю, что ваша система связи TCP / IP имеет высокую пропускную способность и может рассматриваться как низкая задержка (в идеале ноль, но этого никогда не происходит).

Я хотел бы предложить, чтобы каждый узел имел список подключений других узлов, к которым он может подключиться. (Узлам было бы все равно, откуда происходит соединение.) Заполнение таблиц, к каким узлам может подключиться узел, оставляется как отдельная вещь для сортировки, вы не сказали, будет ли это статически установлено или нет. Также удобно игнорировать такие вещи, как распределение номеров IP-портов, где соединения будут приходить на узел - могут быть веские причины для приема запросов только на один порт или на несколько портов. Это должно быть тщательно продумано. Факторы будут включать неявную организацию очередей, порядок, использование ресурсов, тип операционной системы и возможности.

Как только узлы узнают, к кому они подключаются, они могут отправить этому узлу запрос на блокировку и должны получить ответ от ответа на блокировку от этого удаленного узла. Вы можете упаковать эти две операции в оболочку, чтобы она выглядела атомарно. Результатом этого является то, что узлы, желающие получить блокировку, сделают вызов примерно таким:

if (get_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

/* Lock is now acquired - do work here */

if (release_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

вызовы get_lock и release_lock должны быть примерно такими (в принципе):

send_to_remote_node(lock_request)
get_from_remote_node_or_timeout(lock_reply, time)
if (result was timeout) then
  return timeout
else
  return ok

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

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


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

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

quickly_now
источник
1
Семантика тайм-аута в основном используется для работы с узлами, которые исчезают из сети, или для работы с большими задержками в стеках блокировки ... Это ограничит время, затраченное на блокировку в ожидании получения блокировки, и предоставит возможность тем, кто запрашивает блокировку. запускать другие процессы в условиях неожиданных задержек, сбоев и т. д. Кроме того, это предотвратит вечную блокировку чего-либо в случае сбоя. Я ценю ваши опасения, хотя на данный момент я не вижу альтернатив, учитывая, что в конечном итоге что-то не
получится
Чтобы поговорить с некоторыми другими вашими комментариями, я не использую очереди как таковые (в смысле асинхронного взаимодействия), хотя я ожидаю, что блокировки стэкируются и освобождаются на основе шаблона FIFO. Я не совсем смирился с тем, как это будет работать с точки зрения требуемого шаблона запроса / ответа, кроме того, что он должен будет каким-то образом блокироваться и быть частью большего рукопожатия. В данный момент я работаю с механизмом стекированной блокировки внутри одного узла, а затем с тем, как он будет работать в распределенном сценарии. Я сделаю немного больше чтения, как вы предложили. Спасибо
JoeGeeky
@JoeGeeky - FIFO - это очередь. Остерегайтесь очередей. Продумайте эту сторону очень тщательно. Это звучит так, будто вы не собираетесь просто получить что-то «с полки», а должны будете тщательно продумать свою проблему и решение.
fast_now
Я понимаю ... Я пытался выяснить разницу между очередью FIFO, используемой в асинхронных процессах ( например, один процесс ставит в очередь, а затем другой удаляет ). В этом случае нужно будет управлять всем по порядку, но процесс, входящий в очередь, не уйдет до тех пор, пока (а) они не получат блокировку, (б) не будет отказано в блокировке или (в) не произойдет таймаут и не покинут линию. Больше похоже на стояние в очереди у банкомата. В случае успеха это ведет себя как шаблон FIFO, но процессы могут выйти из строя до того, как достигнуть начала строки. Что касается готовых? Нет, но это не новая проблема
JoeGeeky
0

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

Посмотрите на следующий код;

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

// Instance of the object used to lock and unlock cache items in NCache
LockHandle lockHandle = new LockHandle();

// Specify time span of 10 sec for which the item remains locked
// NCache will auto release the lock after 10 seconds.
TimeSpan lockSpan = new TimeSpan(0, 0, 10); 

try
{
    // If item fetch is successful, lockHandle object will be populated
    // The lockHandle object will be used to unlock the cache item
    // acquireLock should be true if you want to acquire to the lock.
    // If item does not exists, account will be null
    BankAccount account = cache.Get(key, lockSpan, 
    ref lockHandle, acquireLock) as BankAccount;
    // Lock acquired otherwise it will throw LockingException exception

    if(account != null && account.IsActive)
    {
        // Withdraw money or Deposit
        account.Balance += withdrawAmount;
        // account.Balance -= depositAmount;

        // Insert the data in the cache and release the lock simultaneously 
        // LockHandle initially used to lock the item must be provided
        // releaseLock should be true to release the lock, otherwise false
        cache.Insert("Key", account, lockHandle, releaseLock); 
        //For your case you should use cache.Unlock("Key", lockHandle);
    }
    else
    {
        // Either does not exist or unable to cast
        // Explicitly release the lock in case of errors
        cache.Unlock("Key", lockHandle);
    } 
}
catch(LockingException lockException)
{
    // Lock couldn't be acquired
    // Wait and try again
}

Взято по ссылке: http://blogs.alachisoft.com/ncache/distributed-locking/

Базит Анвер
источник