Недавно мы с Глебом Науменко (Gleb Naumenko), совместно с нашим бывшим коллегой Грегом Максвеллом  (Greg Maxwell), создали Minisketch, библиотеку для снижения требований к пропускной способности при синхронизации данных между узлами распределенных систем.

Первоначально Minisketch был разработан как компонент проекта, в котором исследуется использование методов сверки наборов данных при их обмене во время транзакций между узлами Биткоин,  «Ретранслятор сверки наборов данных» (Set Reconciliation Relay или SRR). Цель SRR - значительно уменьшить расход трафика, связанного с работой полного узла Биткоин.

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

Зачем нужен Minisketch?

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

Например, один подход к синхронизации данных между узлами распределенной сети – это инвертируемые таблицы поиска Блума (Invertible Bloom Lookup Tables, IBLT). Применение IBLT создает сравнительно низкую нагрузку на CPU, но это достигается за счет сравнительно высоких требований к полосе пропускания, особенно при малом количестве различий. Minisketch использует более эффективный алгоритм, известный под названием PinSketch.

По сравнению с другими эффективными алгоритмами сверки наборов данных, такими как CPISync или оригинальная версия Pinsketch, для Minisketch требуется значительно меньше вычислительной мощности. Он работает в 20-100 раз быстрее, чем PinSketch, и в некоторых случаях более чем в 1000 раз быстрее, чем CPISync.

Каким образом достигается это улучшение эффективности?

Сверка набора данных, предусмотренная Minisketch, позволяет более эффективно использовать соединение, если сравнивать с отправкой полного набора данных, так как позволяет узлам создать математический “набросок” всего набора. После создания своего наброска, узел посылает его другим узлам для сравнения с их наборами. Размер наброска зависит только от предполагаемого количества различий между узлами, а не от общего размера набора данных. Несмотря на это, набросок позволяет узлам с точностью определять какие именно данные необходимо получить от других узлов.

Если упростить ситуацию до одного различия, принцип действия понятен: представим, что у меня есть набор {3,5,7,11}, а у вас – {3,5,7,9,11}, то есть разница - {9}. Каждый из нас суммирует собственные элементы, и я получаю 3+5+7+11=26, а вы – 3+5+7+9+11=35. Я отправляю вам мою сумму 26, вы вычитаете ее из собственной, получается 9. Этот способ работает, но он ограничен возможностью нахождения всего одного отличия. Minisketch расширяет рамки этого подхода, рассылая различные типы “сумм” данных. Результат – при наличии количества N различных сумм, можно найти количество N различий … Minisketch способен находить все различия если количество различий между наборами не превышает количество разосланных “сумм”.

Minisketch для Биткоин

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

К сожалению, большая часть трафика (в среднем от 40% до 70%), используемого узлом Биткоин, расходуется не на данные о транзакции, а на оповещение друг друга о новых транзакциях с целью обнаружения транзакций, требующих отправки. Поэтому, увеличение количества соединений между узлами пропорционально повышает требования к пропускной способности. Это приводит к ограничению количества соединений, которое может поддерживаться каждым узлом.

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

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

Протокол SRR находится еще на ранней стадии разработки и может пройти много времени, прежде чем он будет внедрен в сеть Биткоин, но достижения, такие как Minisketch, представляют собой очень важное событие в повышении доступности полного узла Биткоин и их распространении (а также оптимизации других распределенных сетей). Следите за новостями о развитии проекта здесь!

Узнать о Minisketch можно через соответствующий репозиторий на GitHub.