Как удалить дублированные значения в распределенной системе?
Предположим, у нас есть распределенная система, и в кластере есть K машин. Каждая машина хранит несколько целых чисел. Я хотел бы удалить все повторяющиеся значения из системы. Таким образом, если целое число 123 появляется в machine1 и machine2, мы должны оставить только один 123 в системе. Как мне справиться с этим?
Моя идея состоит в том, чтобы сначала позволить каждой машине выполнить операцию removeDuplicate, используя что-то вроде сортировки по сегментам (все числа являются целочисленными), а затем позволить одной машине быть главным узлом для выполнения редукции. Есть ли идея получше?
2 ответа
Простым ответом было бы, в первую очередь, не получить неуправляемые дублированные значения на разных машинах, используя распределенное хеш-кольцо или аналогичную технологию, чтобы убедиться, что определенное значение попадает в определенный узел.
Если этого недостаточно, я бы посмотрел на эвристические оптимизации. Поскольку у вас уже есть несколько копий на разных компьютерах, я предполагаю, что вы хотите дедуплицировать эти значения для большей производительности, а не для корректности работы приложения.
Если это так, пусть каждый узел медленно проходит через свое пространство ключей (foreach для целого числа на узле) и спрашивает все другие узлы, есть ли у них копия того же значения. Если они это сделают, мы дедуплицируем это. Если кто-то не отвечает (достаточно быстро); игнорируйте их и продолжайте. Это позволяет использовать децентрализованный алгоритм дедупликации, который обрабатывает сбои узлов и может работать с любой скоростью, позволяя приоритизировать более важный трафик при необходимости.
Я предполагаю, что доступ к ключам осуществляется в соответствии с распределением степенных законов, поэтому более частый просмотр наиболее часто обновляемых ключей может быть более эффективным, но на это нет никаких гарантий.
Не уверен, какой тип системы вас интересует, но если общая память является опцией, вы можете сохранить счетчик массива. Поскольку все ваши числа являются целыми числами, вы можете пометить каждое целое число, которое появляется в этом общем массиве. Кроме того, если это целое число уже помечено, удалите его. Это приведет к o(k) операциям для каждого полученного целого числа и не будет дубликатов.