Предположим, у нас есть два равноправных узла: первый узел может отправить запрос на подключение ко второму, но также и второй может отправить запрос на соединение первому. Как избежать двойного соединения между двумя узлами? Для решения этой проблемы было бы достаточно сделать последовательными операции, выполняемые для создания входящих или исходящих соединений TCP.
Это означает, что каждый узел должен последовательно обрабатывать каждую новую операцию создания соединения, как для входящих, так и для исходящих соединений. Таким образом, для ведения списка подключенных узлов перед принятием нового входящего соединения от узла или перед отправкой запроса на соединение узлу будет достаточно проверить, присутствует ли этот узел в списке.
Для последовательного выполнения операций по созданию подключений достаточно выполнить блокировку списка подключенных узлов: фактически для каждого нового подключения в этот список добавляется идентификатор нового подключенного узла. Однако мне интересно, может ли такой подход вызвать распределенную тупиковую ситуацию :
- первый узел может отправить запрос на соединение второму;
- второй узел может отправить запрос на соединение первому;
- при условии, что два запроса на подключение не являются асинхронными, оба узла блокируют любые входящие запросы на подключение.
Как я мог решить эту проблему?
ОБНОВЛЕНИЕ: Однако мне все еще приходится блокировать список каждый раз, когда создается новое (входящее или исходящее) соединение, так как другие потоки могут получить доступ к этому списку, тогда проблема взаимоблокировки все равно останется.
ОБНОВЛЕНИЕ 2: На основании вашего совета я написал алгоритм, предотвращающий взаимное принятие запроса на вход в систему. Поскольку каждый узел является одноранговым, он может иметь клиентскую процедуру для отправки новых запросов на подключение и серверную процедуру для приема входящих подключений.
ClientSideLoginRoutine() {
for each (address in cache) {
lock (neighbors_table) {
if (neighbors_table.contains(address)) {
// there is already a neighbor with the same address
continue;
}
neighbors_table.add(address, status: CONNECTING);
} // end lock
// ...
// The node tries to establish a TCP connection with the remote address
// and perform the login procedure by sending its listening address (IP and port).
boolean login_result = // ...
// ...
if (login_result)
lock (neighbors_table)
neighbors_table.add(address, status: CONNECTED);
} // end for
}
ServerSideLoginRoutine(remoteListeningAddress) {
// ...
// initialization of data structures needed for communication (queues, etc)
// ...
lock(neighbors_table) {
if(neighbors_table.contains(remoteAddress) && its status is CONNECTING) {
// In this case, the client-side on the same node has already
// initiated the procedure of logging in to the remote node.
if (myListeningAddress < remoteListeningAddress) {
refusesLogin();
return;
}
}
neighbors_table.add(remoteListeningAddress, status: CONNECTED);
} // end lock
}
Пример: IP: порт узла A - A: 7001 - IP: порт узла B - B: 8001.
Предположим, что узел A отправил запрос на вход в систему узлу B: 8001. В этом случае узел A вызывает процедуру входа в систему, отправляя, отправляя свой собственный адрес прослушивания (A: 7001). Как следствие, таблица соседей узла A содержит адрес удаленного узла (B: 8001): этот адрес связан с состоянием CONNECTING. Узел A ожидает, пока узел B не примет или отклонит запрос на вход в систему.
Между тем, узел B также, возможно, отправил запрос соединения на адрес узла A (A: 7001), тогда узел A может обрабатывать запрос узла B. Таким образом, соседняя_таблица узла B содержит адрес удаленного узел (A: 7001): этот адрес связан с состоянием CONNECTING. Узел B ожидает, пока узел A примет или отклонит запрос на вход в систему.
Если серверная сторона узла A отклоняет запрос от B: 8001, то я должен быть уверен, что серверная сторона узла B примет запрос от A: 7001. Точно так же, если серверная сторона узла B отклоняет запрос от A: 7001, то я должен быть уверен, что серверная сторона узла A примет запрос от B: 8001.
Согласно правилу «малого адреса» , в этом случае узел A отклонит запрос на вход в систему от узла B, а узел B примет запрос от узла A.
Что ты об этом думаешь?
источник
Ответы:
Вы можете попробовать «оптимистический» подход: сначала подключиться, а затем отключиться, если вы обнаружите одновременную взаимную связь. Таким образом, вам не нужно будет пропускать запросы на подключение во время создания новых подключений: когда входящее подключение установлено, заблокируйте список и посмотрите, есть ли у вас исходящее подключение к тому же хосту. Если вы это сделаете, проверьте адрес хоста. Если он меньше вашего, отключите исходящее соединение; в противном случае отключите входящий. Ваш одноранговый хост будет делать противоположное, потому что адреса будут сравниваться по-разному, и одно из двух соединений будет разорвано. Такой подход позволяет избежать повторных попыток подключения и потенциально помогает принимать больше запросов на подключение за единицу времени.
источник
Когда один узел отправляет запрос другому, он может содержать случайное 64-разрядное целое число. Когда узел получает запрос на соединение, если он уже отправил один из своих, он сохраняет один с наибольшим номером и отбрасывает остальные. Например:
Время 1: A пытается подключиться к B, отправляет номер 123.
Время 2: B пытается подключиться к A, отправляет номер 234.
Время 3: B получает запрос A Поскольку собственный запрос B имеет большее число, он отклоняет запрос A.
Время 4: А получает запрос Б. Поскольку запрос B имеет большее число, A принимает его и отбрасывает собственный запрос.
Чтобы сгенерировать случайное число, убедитесь, что вы заполнили свой генератор случайных чисел с помощью / dev / urandom, а не с использованием заполнения по умолчанию вашего генератора случайных чисел, который часто основывается на времени настенных часов: есть неоспоримый шанс, что два узла получит то же самое семя.
Вместо случайных чисел вы также можете заранее распределить числа (т. Е. Просто нумеровать все машины от 1 до n), или использовать MAC-адрес, или каким-либо другим способом найти число, где вероятность столкновения настолько мала, что игнорируемые.
источник
Если я понимаю, проблема, которую вы пытаетесь избежать, выглядит следующим образом:
Я могу придумать пару разных способов справиться с этим.
источник