В данном документе описан сетевой протокол системы обновления приложений SkyUD.
Общие принципы
Терминология
| Термин | Описание |
| Пир | Любой участник файлообмена |
| Образ | Все файлы определённой версии приложения |
| Метафайл | Файл, содержащий информацию об образе, в том числе адреса обслуживающих образ серверов, список файлов образа и хеши их частей |
| Часть | Данные всех файлов образа разбиты на части размером в 8МБ. Как только пир загружает полную часть, она становится доступной для скачивания с данного пира |
| Блок | При передаче по сети части делятся на блоки по 32КБ, что даёт возможность загружать одну часть из нескольких источников сразу |
| Сервер | Пир, всегда имеющий полный образ и являющийся базовой точкой обмена информацией об участниках файлообмена (аналогично трекерам в BitTorrent-протоколе) |
| Клиент | Пир, осуществляющий загрузку образа |
| Клиент с открытым портом | Клиент, способный не только устанавливать исходящие соединения, но и принимать входящие |
Алгоритм работы
SkyUD является гибридной системой обновления, поддерживающей скачивание как с централизованных серверов обновлений, так и загрузку блоков данных от других пользователей подобно p2p-сетям. Во многом SkyUD Protocol похож на другие p2p-протоколы (особенно BitTorrent-протокол, являющийся его прародителем), но имеет ряд серьёзных отличий от них, вытекающих из того, что протокол предназначен для загрузки обновлений в онлайн играх, а не для файлообмена:
- Если сервера могут обслуживать несколько образов, то клиенты всегда качают только какой-то один образ
- Единственными полными источниками образов выступают сервера обновлений, т.к. клиенты отключается сразу после получения полного образа (запущенный p2p-клиент во время игры это источник лагов)
Изначально информация об образе распространяется с помощью метафайлов (способы распространения метафайлов подобны способу распространения *.torrent-файлов в протоколе BitTorrent и выходят за рамки SkyUD Protocol). Каждый метафайл хранит в себе описание образа, информацию обо всех файлах образа (имена, размеры, хеши частей) и адреса всех серверов, обслуживающих данный образ.
Для скачивания образа или его части клиент вначале должен установить соединение хотя бы с одним сервером. Далее начинается скачивание образа с сервера, а кроме того у сервера запрашиваются адреса других клиентов с открытыми портами, скачивающими тот же образ. Получив адреса других клиентов, клиент устанавливает соединения с некоторым кол-вом ближайших клиентов и осуществляет с ними обмен частями образа для повышения скорости закачки и снижении нагрузки на сервер.
CSSF (Cat Structure Storage Format)
CSSF это формат для сериализации произвольных структур. Содержит 14 основных типов данных и 3 составных. Для каждого из основных типов данных поддерживаются массивы с индексом длины 1, 2 и 4 байта. Все многобайтные типы данных хранятся в порядке little-endian.
Типы данных
Простые типы:
- $0 — CSSFType_RAW
- $1 — CSSFType_Bool
- $2 — CSSFType_Int8
- $3 — CSSFType_Int16
- $4 — CSSFType_Int32
- $5 — CSSFType_Int64
- $6 — CSSFType_Word8
- $7 — CSSFType_Word16
- $8 — CSSFType_Word32
- $9 — CSSFType_Word64
- $A — CSSFType_Float32
- $B — CSSFType_Float64
- $C — CSSFType_AnsiChar
- $D — CSSFType_WideChar
Модификаторы массива для простых типов:
- $10 — CSSFTypeArray_8b
- $10 — CSSFTypeArray_16b
- $10 — CSSFTypeArray_32b
Составные типы:
- $80 — CSSFTypeComp_List
- $81 — CSSFTypeComp_Dict
- $82 — CSSFTypeComp_Table
- $FF — CSSFTypeComp_EndOfStruct (маркер конца структуры)
Примечание: Обычно тип данных CSSFType_RAW без указания массива используется как отсутствие значения (особенно актуально для таблиц)
Кодирование массивов
Массивы кодируются следующим образом: <простой тип с модификатором массива><кол-во элементов массива><данные>. Например массив из Word16[64, 128, 256] с однобайтной длиной будет выглядеть так:
$17$03$40$00$80$00$00$01
Кодирование данных в составных типах
List
Список любых других типов. Кодируется как $80<элементы списка>$FF. Например список из 3х чисел: однабайтного, двухбайтного и четырёхбайтного равных 1 будет выглядеть как:
$80$06$01$07$01$00$08$01$00$00$00$FF
Dict
Словарь: уникальный ключ и его значение. Ключи могут быть разных типов, но должны быть простыми типами или массивами простых типов. Кодируется как $81<пары ключ-значение>$FF. Например словарь с ключом типа массив char`ов и содержанием «a» => word8[16, 32, 64], «b» => «test» будет выглядеть так:
$81$1C$01’a’$16$03$10$20$40$1C$01’b’$1C$04’test’$FF
Примечание: т.к. массивы в примере короткие — везде используются массивы с однобайтной длинной
Table
Таблица — самый сложный тип данных. Таблица представляет из себя список имён столбцов (все имена — простые типы), после которого следуют записи, состоящие из кол-ва элементов, равного кол-ву столбцов в таблице. Кроме того, первый столбец считается индексом таблицы и должен всегда содержать элементы простых типов (можно массивы), и не должен содержать повторяющихся элементов.Кодируется как $82<список имён столбцов>$FF<записи таблицы>$FF. Например мы хотим закодировать следующую таблицу (имена столбцов — массив букв, ключ — Word8):
| ID | Size | Name |
| 0 | 256 | zero |
| 1 | 128 | one |
| 2 | 512 | two |
Получится вот что (пример специально записан в несколько строк для облегчения восприятия):
$82$1C$02’ID’$1C$04’Size’$1C$04’Test’$FF
$06$00$08$00$01$00$00$1C$04’zero’
$06$01$08$80$00$00$00$1C$03’one’
$06$02$08$00$02$00$00$1C$03’two’
$FF
Метафайл
Информация об образе распространяется в виде метафайла формата CSSF, содержащего один словарь со строковыми ключами и следующими секциями:
- version (информация о версии — словарь со строковыми1 ключами)
- name (имя версии — строка)
- info (описание версии — RAW-массив с 4-х байтным полем размера) [опционально]
- log (changelog — RAW-массив с 4-х байтным полем размера) [опционально]
- image (информация о файлах образа — словарь со строковыми1 ключами)
- files (информация о каждом отдельном файле образа2 — таблица ключ-значение)
- name (имя файла — строка1 с разделителем директорий в виде символа «\») [ключ таблицы]
- size (размер файла в байтах — Word64)
- pieces (массив SHA1-хешей частей3 — RAW-массив с 4-х байтным полем размера)
- files (информация о каждом отдельном файле образа2 — таблица ключ-значение)
- servers (сервера обслуживающие данный образ — список строк1)
- Адреса серверов в формате IPv6 адресов — [xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx]:<Port> (для IPv4 адресов вида [::FFFF:xxxx:xxxx]:<Port>)
Примечания:
- Строка это массив AnsiChar-ов с однобайтным полем длины.
- Образ не должен содержать более 256-ти файлов.
- Образ не должен содержать более 2 20 частей.
При генерации секции image\pieces каждый файл образа разбивается на части по 8МБ (в конце каждого файла возможны неполные части), для каждой из которых рассчитывается SHA1-хеш. Эти хеши последовательно добавляются в данную секцию. Файлы обрабатываются в порядке их следования в секции image\files. Для идентификации образа используется SHA512-хеш всего метафайла.
Протокол сети пиров
Установка соединения
Сразу после установления соединения, пиру, инициировавшему соединение, следует отправить другому пиру сообщение-рукопожатие (handshake). И ждать от него аналогичного сообщения. Если обмен рукопожатиями не произошел в течении 5-ти секунд — соединение надлежит разорвать. Обмен любыми командами возможен только после завершения процедуры рукопожатия.
| Блок | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | Строка-идентификатор протокола, должна быть равна «SkyUDProto01» | Состояние пира | Прослушиваемый пиром порт (если указан 0 — порт пира недоступен) | |||||||||||||
| 2 | Идентификатор пира — случайное число, генерируемое при начале работы клиента и используемое для избежания дублирования соединений и при проверке доступности порта клиента сервером (в ответах сервера это не его идентификатор, а IP-адрес клиента в IPv6 формате) | |||||||||||||||
| 3 | SHA512-хеш метафайла скачиваемого образа | |||||||||||||||
| 4 | ||||||||||||||||
| 5 | ||||||||||||||||
| 6 | ||||||||||||||||
| Код | Состояние | Описание |
| 0 | ConnectionTest | Проверка доступности слушающего порта пира |
| 1 | Server | Пир имеющий все части |
| 2 | Client | Пир не имеющий ни одной части |
| 3 | ClientWP | Пир имеющий некоторые части |
| -1 | UnknownImage | Запрашиваемый образ не обрабатывается пиром |
| -2 | Overload | Пир перегружен |
Процесс установки соединения клиента с сервером:
- Клиент: инициирует TCP-подключение к серверу
- Сервер: принимает TCP-подключение и, если превышен лимит соединений, пытается сразу послать рукопожатие с состоянием Overload и пустым полем Image (т.к. сервер может обслуживать множество образов и без рукопожатия клиента невозможно установить, какой из них клиент загружает), а затем закрывает соединение
- Клиент: посылает рукопожатие с состоянием Client или ClientWP
- Сервер: принимает рукопожатие, проверяет его корректность и в случае некорректного рукопожатия закрывает соединение
- Сервер: ищет запрашиваемый образ и если он недоступен посылает ответное рукопожатие с состоянием UnknownImage, а затем закрывает соединение
- Сервер: посылает ответное рукопожатие с состоянием Server и считает соединение установленным (если в рукопожатии клиента указан не нулевой порт, сервер инициирует процедуру проверки доступности порта клиента)
- Клиент: принимает рукопожатие, проверяет его корректность и в случае некорректного рукопожатия закрывает соединение
- Клиент: считает соединение установленным
Процесс установки соединения клиента с клиентом:
- Клиент А: инициирует TCP-подключение к клиенту Б
- Клиент Б: принимает TCP-подключение и, если превышен лимит соединений, пытается сразу послать рукопожатие с состоянием Overload, а затем закрывает соединение
- Клиент А: посылает рукопожатие с состоянием Client или ClientWP
- Клиент Б: принимает рукопожатие, проверяет его корректность и в случае некорректного рукопожатия закрывает соединение
- Клиент Б: проверяет идентичность хешей метафайла загружаемого им образа и образа, который желает загружать клиент А, и если они не идентичны посылает ответное рукопожатие с состоянием UnknownImage, а затем закрывает соединение
- Клиент Б: посылает ответное рукопожатие с состоянием Client или ClientWP
- Клиент Б: если в своём рукопожатии он указал своё состояние как ClientWP — посылает битовую карту частей, которые ему ещё необходимо скачать (размер карты округляется вверх до кратного 8-ми)
- Клиент А: принимает рукопожатие, проверяет его корректность и, в случае некорректного рукопожатия, закрывает соединение
- Клиент А: если в своём рукопожатии он указал своё состояние как ClientWP, то посылает битовую карту частей, которые ему ещё необходимо скачать
- Клиент А: если в рукопожатии клиент Б указал своё состояние как ClientWP — принимает битовую карту частей
- Клиент А: считает соединение установленным
- Клиент Б: если в рукопожатии клиент А указал своё состояние как ClientWP — принимает битовую карту частей
- Клиент Б: считает соединение установленным
Работа соединения
После установки соединения по нему возможен обмен командами. Команды состоят из обязательных 4-х байт и необязательных дополнительных данных, наличие и размер которых зависят от конкретной команды. Если по соединению не поступает никаких команд в течении 125 секунд, его следует считать разорванным. С целью недопущения разрывов соединений при длительном отсутствии команд по соединению посылается команда Ping если с момента отправки последней команды по нему прошло 120 секунд. Первыми командами, переданными по соединению, считаются рукопожатия.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| Команда | Номер части | Номер блока | |||||||||||||||||||||||||||||
| Код | Команда | Поля | Данные | Поддержка сервером | Описание |
| 0 | Ping | Нет | Нет | Приём Передача | Команда поддержки соединения, посылаемая раз в 2 минуты в отсутствии других команд |
| 1 | Interest | Нет | Нет | Нет | Пир заинтересован в скачивании |
| 2 | Uninterest | Нет | Нет | Нет | Пир более не заинтересован в скачивании |
| 3 | Choke | Нет | Нет | Передача | Пир более не будет обрабатывать запросы |
| 4 | Unchoke | Нет | Нет | Передача | Пир готов к обработке запросов |
| 5 | Have | Номер части | Нет | Нет | Пир информирует о наличии у него указанной части |
| 6 | Request | Номер части, Номер блока | Нет | Приём | Пир желает получить указанную часть (если такая команда пришла для пира находящегося в состоянии «удушения» следует ответить командой RequestFail) |
| 7 | RequestCancel | Номер части, Номер блока | Нет | Приём | Пир отменяет предыдущую команду Request (если в списке запросов пира такого запроса нет, следует просто проигнорировать команду, т.к. скорее всего это запрос уже выполнен) |
| 8 | RequestFail | Номер части, Номер блока | Нет | Передача | Запрос пира не может быть выполнен (обычно в следствии «удушения» пира с другой стороны) |
| 9 | RequestAnswer | Номер части, Номер блока | Данные части (размер можно получить из метафайла) | Передача | Ответ на запрос пира, содержит запрошенные пиром данные |
| 10 | RequestAnswerCF | Номер части, Номер блока | Данные части (размер можно получить из метафайла) | Передача | Ответ на запрос пира, содержит запрошенные пиром данные с дополнительной сигнализацией что пир может выполнять запросы быстрее (по сути это уведомление о возможности увеличение длины очереди запросов) |
| 11 | PeerSearch | Нет | Приём | Пир просит предоставить ему список других участников файлообмена | |
| 12 | PeerList | Номер блока | Список адресов пиров (длина указана в номере блока, но не более 100) | Передача | Запрошенные пиром адреса других участников файлообмена (данная команда может выполняться сервером вне очереди по отношению к другим командам. Это вызвано тем, что время выполнения этой команды может быть значительно выше чем всех остальных) |
Примечание: при получении неверной/недоступной команды следует немедленно разорвать соединение
Процедура проверки доступности порта клиента
- Сервер инициирует TCP-соединение по адресу с которого пришло TCP-соединение клиента на порт, указанный в рукопожатии клиента, и посылает по нему рукопожатие с состоянием ConnectionTest
- Если в течении 5-ти секунд от клиента не поступит ответное рукопожатие, проверка считается неудачной
- Если от клиента поступит неверное рукопожатие, проверка считается неудачной (допустимые состояния клиента: ConnectionTest, UnknownImage, Overload)
- Проверка считается удачной при состояниях ConnectionTest и Overload, при состоянии UnknownImage проверка считается неудачной
Описание алгоритмов
Выбор сервера
В каждом метафайле содержится список серверов, обслуживающих данный образ. В процессе парсинга метафайла клиент должен разделить сервера на две группы: имеющие адреса IPv4 и имеющие адреса IPv6. Далее сервера каждой группы перемешиваются в случайном порядке и заносятся в 2 списка.
При каждом обновлении состояния клиента следует проводить проверку на наличие соединения с сервером каждой сети (IPv4 и IPv6) и если соединения нет — пытаться установить его с первым сервером в соотв.. списке. В случае неудачи установления/разрыва соединения следует переместить адрес сервера в конец соотв.. списка и пометить его как недоступный на некоторое время (в стандартной реализации 30 секунд).
Построения сети пиров
В отличии от BitTorrent-протокола, использующего принцип установки соединений со случайными пирами (как при установке исходящих соединений, так и при подготовке списка пиров трекером), SkyUD Protocol использует принцип построения адресного кольца. Причём кольца разные для разных сетей (IPv4 и IPv6). Адрес любого клиента рассматривается как 18-ти байтное число (старшие 16 байт — это адрес в IPv6 формате, а младшие — прослушиваемый порт). Все множество возможных адресов представляет из себя кольцо (адреса [::0]:0 и [FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF]:FFFF рассматриваются как соседние). В идеале каждый клиент должен установить равное кол-во соединений со своими соседями с обеих сторон.
При формировании ответа на команду PeerSearch сервер возвращает клиенту по 50 адресов ближайших клиентов с обеих сторон (возвращаются только адреса клиентов прошедших проверку открытости порта). Клиент же просто возвращает адреса всех клиентов, с которыми он соединён в текущий момент (рассматриваются только соединения для которых получено корректное рукопожатие с другой стороны).
При необходимости увеличить кол-во соединений с клиентами (в стандартной реализации это происходит пока кол-во соединений с другими клиентами меньше 32-х) клиенту надлежит выбрать адрес, исходя из изложенного выше принципа равного кол-ва соединений в обе стороны .
Дросселирование пиров
Дросселирование (choking) сделано по трём причинам:
- Управление перегрузкой TCP ведет себя очень плохо при одновременном обмене данными по большому кол-ву соединений
- Выгоднее обеспечивать высокую скорость загрузки нескольким пирам, нежели малую всем (Пир начинает распространять полученные данные только тогда, когда вся часть готова. Поэтому если быстро отдать целую часть нескольким пирам, а затем начать обслуживание других, эти пиры смогут передать полученные данные далее.)
- Это позволяет клиентам использовать стратегию зуб-за-зуб и в первую очередь обслуживать тех клиентов, которые обслуживают данный
В качестве основного алгоритма дросселирования пиров SkyUD Protocol предполагает использование следующего алгоритма:
- Для каждого соединения с другим клиентом ведётся учёт рейтинга. Каждый раз, когда другой клиент выполняет наш запрос, его рейтинг увеличивается на 1. Каждый раз, когда мы выполняем запрос другого клиента, его рейтинг уменьшается на 1.
- Раз в 10 секунд производится обновление списка разблокированных клиентов следующим образом:
- Все разблокированные клиенты перемещаются в конец списка клиентов
- Выбираются 7 клиентов с самым высоким рейтингом из числа тех клиентов, которые заявили о желании загружать у нас
- Восьмым разблокированным клиентом выбирается первый в списке клиент, не из числа предыдущих 7-ми, который желает загружать у нас
Стратегия скачивания частей
Для каждой части образа каждый клиент ведёт учёт рейтинга (кол-ва других подключенных клиентов у которых уже есть эта часть). При выборе следующей части для загрузки рекомендуется выбирать часть с наименьшим рейтингом (при загрузке с сервера вообще крайне рекомендуется первыми загружать части, которых нет ни у одного подключённого клиента). При наличии нескольких доступных частей с одинаковым рейтингом следует выбирать часть случайных образом.
Длина очереди запросов
Очередь запросов (кол-во отправленных команд Request на которые еще не получен ответ) для соединения может варьироваться от 2-х до 256-ти команд. Длина очереди запросов увеличивается каждый раз, когда пир присылает в качестве ответа на команду Request команду RequestAnswerCF, которая показывает что при обработке этого запроса очередь запросов у пира была пуста. Уменьшение очереди запросов осуществляется крайне просто: через каждые 16 полученных ответов длина очереди уменьшается на 1. Этот простой алгоритм отлично показал себя при работе на соединениях без искусственного ограничения скорости и слегка хуже на соединениях с ним.
Режим скачивания Endgame
Когда клиенту остаётся загрузить только одну часть, он переходит в режим endgame (предусмотренный для решения проблемы падения скорости загрузки в конце скачивая образа). При переходе в этот режим у всех пиров запрашиваются все недостающие блоки (правда запрашиваются они в случайном порядке, дабы минимизировать кол-во повторных скачиваний). При получении блока в этом режиме всем остальным пирам (кроме того от которого был получен блок) посылается команда RequestCancel.