Китайска торент система

Задача #3 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2011/2012

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

Китайска торент система – архитектура

Ето как работи китайската торент системата: потребители и автори, които обслужват създаването,  стопанисването и разпространението на съдържание (например статии, документи и видео) се разделят на два вида: четни и нечетни. Четните потребители (сървъри) съхраняват само четните битове от споделеното съдържание (кодирани с парола), а нечетните – само нечетните битове (отново кодирани с парола). Така никой потребител на китайската торент мрежа на практика не съхранява при себе си споделеното съдържание, а само някаква поредица от битове, която не е ясно част от какво е. Докато даден потребител, стопанисващ на своя твърд диск половината от някакъв документ или филм, не изтегли и втората половина битове, какво точно е съдържанието не може да бъде установено. Така, ако китайските власти изземат сървърите на даден потребител или участник в системата, няма да могат да разберат какво съдържание съдържат те, защото един сървър съдържа или само четните, или само нечетните битове от данните.

Всеки файл в торент системата е защитен с парола (ключ). Системата показва на даден потребител само файловете, за които той е въвел правилната парола (ключ) за достъп, а останалите файлове са невидими за него. Така различни потребители могат да качват файлове с различни пароли и да виждат само файловете, за които имат правилната парола.

Потребителите, които използват системата, могат да теглят от нея на свой собствен риск публикуваното съдържание, като за целта се свързват едновременно към един от четните и един от нечетните сървъри (подавайки правилните пароли за достъп). Например, за да гледа 700 мегабайтов филм, качен в китайската торент система, даден потребител може да се закачи едновременно за един четен и един нечетен сървър, които разполагат със съответните части на дадения филм, след което може да тегли филма на порции (четна + нечетна порция, примерно по 200-300 KB), да ги съединява и да ги възпроизвежда (play). Така системата позволява на крайния потребител също да не съхранява при себе съдържанието, а само да го възпроизвежда и той е уязвим само през краткия интервал от време, през който гледа въпросния филм или ползва съединените четни и нечетни битове на изтегленото съдържание или част от съдържание.

При качване на файл, неговите нечетни битове се подреждат в байтове от ляво надясно, започвайки от най-левия нечетен бит на първия байт от файла (бит 7), следват битове 5, 3 и 1 на първия байт, следват битове 7, 5, 3 и 1 на втория байт и т.н. Четните байтове се образуват от ляво надясно чрез долепяне на битовете от файла от най-левия към най-десния: започвайки от най-левия четен бит на първия байт от файла (бит 6), следват битове 4, 2 и 0 на първия байт, следват битове 6, 4, 2 и 0 на втория байт и т.н. Например, ако първите 16 байта на даден файл са шестнайсетичните стойности 00-00-00-20-66-74-79-70-69-73-6F-6D-00-00-02-00, то съответните им четни байтове след разделянето са 00-00-AE-DC-9D-BB-00-00, а нечетните – 00-04-54-64-65-76-00-10.

Сървърна функционалност на китайската торент система

Алгоритмичната част от поставения проблем изисква да се разработи и имплементира софтуерът за сървърната част на китайската торент система на базата на REST услуги, достъпни чрез стандартна HTTP заявка.

Комуникация между клиента и сървъра

Препоръчително е комуникацията между клиента и сървъра да се извършва в REST стил чрез HTTP GET и HTTP POST команди, на които сървърът отговаря с JSON-сериализиран резултат. При успех сървърът връща HTTP статус код 200, а при грешка връща трицифрен HTTP статус код за грешка. Форматът на всяка REST заявка е различен и е описан по-долу, като URL адресът на REST услугата е условно означен по следния начин:

http://service-url

Задължителна сървърна функционалност

Задължителната сървърна функционалност на китайската торент системата позволява на потребителите да извършват следните действия:

  • Извличане на актуален списък със сървърите на системата.
  • Извличане на споделените видео файлове по дадена парола (ключ).
  • Изтегляне на част от видео файл.
  • Качване на четна / нечетна половина от видео файл с определена парола.

За простота се приема, че всички файлове в системата представляват стандартни MP4 streamable видео файлове с видео кодек avc1 (H.264/MPEG-4 AVC) и аудио кодек mp4a (MPEG-4 AAC). Също за простота при качване на файл, ако той е с нечетна дължина в края му се добавя една нула, за да стане с четна (нулата накрая не пречи при възпроизвеждане на видео съдържанието).

Извличане сървърите на системата

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

Клиентите на системата пазят локално списък от сървърите на системата и го обновяват при всяко влизане в нея. Ако някой от сървърите спре да работи по някаква причина, клиентите се прехвърлят към останалите.

Извличането на актуален списък със сървърите на системата става чрез изпращане на следната заявка към кой да е от сървърите:

URL

http://service-url/list-servers

Method: GET

При успех услугата връща HTTP статус код 200 и резултат в следния формат:

Body

{„servers“:[{„name“:“Beijing01″,“type“:“odd“,“url“:“http:\/\/chengdu.cn\/huiwei“},{„name“:“Changchun2″,“type“:“even“,“url“:“https:\/\/ncic.ac.cn\/daihui\/chao“},

{„name“:“Hangzhou02″,“type“:“even“,“url“:“https:\/\/ncfck.cn:8080\/yahui\/hu“},

{„name“:“Qingdao33″,“type“:“odd“,“url“:“http:\/\/zjgsu.edu.cn:443\/baihui“}]}

Актуалният списък от сървъри на системата се връща като списък от уникални имена на сървъри (съставени от латински букви и цифри)  + URL адреси. За всеки сървър е указано дали е четен или нечетен. Типът на даден сървър може да е единствено „odd“ или „even„.

Резултатът по-горе е примерен и не съответства на някакви реални сървъри в Интернет.

При грешка услугата връща трицифрен HTTP статус код за грешка (различен от 200).

Извличане на списък от споделени файлове по дадена парола

Всеки споделен в мрежата файл може да е кодиран с парола за достъп. Паролата за достъп е произволен текст до 100 символа (малки и главни латински букви, цифри и следните специални знаци „;:,.!$*[]()_-„). Паролата за достъп може да е празна и това прави файла публично достъпен от всички потребители.

След свързване към системата клиентите могат да изпратят парола (ключ) и да получат файловете, които са достъпни по тази парола. Извличането на достъпните файлове се извършва чрез заявка към някой от сървърите в следния формат:

URL

http://service-url/list-files/s0me!p@ssw0rd

Method: GET

При успех услугата връща HTTP статус код 200 и резултат в следния формат:

Body

{„files“:[{„file“:“Xiao-wang.mp4″,“servers“:[„Beijing01″,“Hangzhou02″],“size“:18345212},{„file“:“baohui.mp4″,“servers“:[„Qingdao33″,“Changchun2″,“Hangzhou02“,

„Beijing01″],“size“:845268},

{„file“:“He Yi Hui Dai.mp4″,“servers“:[„Changchun2″],“size“:196356},

{„file“:“hongcun.mp4″,“servers“:[„Changchun2″,“Qingdao33″],“size“:196356}]}

Имената на файловете са уникални за цялата торент система. Дължината на файловете се задава в байтове (сумарно четни + нечетни). Идентификаторите на сървърите съответстват на върнатите от командата за извличане на списъка от сървъри на системата. Всички файлове са във формат MP4 видео. Ако в списъка от сървъри за даден файл липсва поне един четен и поне един нечетен сървър, той временно не може да се възпроизвежда.

Резултатът по-горе е примерен и не съответства на никакви реални файлове в Интернет.

При грешка услугата връща трицифрен HTTP статус код за грешка (различен от 200).

Изтегляне на част от видео файл

За да възпроизвеждат видео (play video) клиентите теглят от два различни сървъра (четен и нечетен) части от даден файл, съединяват ги и възпроизвеждат фрагмент от видеото. За да изтеглят четна или нечетна част от съдържанието на даден видео файл те подават заявка към сървъра, стопанисващ съответната част от файла, в следния формат:

URL

http://service-url/get-chunk

Method: POST

Body

{„file“:“honghui.mp4″,“password“:“An0therp@ssw0rd“,“offset“:16384,“size“:25}

В заявката се посочват уникалното име на файла, паролата за достъп до него (или празен низ, ако файлът е достъпен без парола), началната позиция, от която да започне четенето и брой байтове, които да бъдат прочетени. Обръщаме внимание, че началната позиция и дължината се задават в байтове спрямо дължината на четната част от битовете на файла. Така ако даден файл е 2001 байта и бъде разделен на четна и нечетна част (съответно с по 1001 байта след закръгляне), валидните начални позиции (offset) ще са в интервала 0…1000, а броят поискани байтове (size) ще е число в интервала 1..1000.

При успех услугата връща HTTP статус код 200 и резултат в следния формат:

Body

{bytes:“QmVzdCByZWdhcmRzIGZyb20gTmFrb3Yh“}

Върнатите байтове са кодирани по стандарта BASE64 и след декодиране трябва да са точно толкова, колкото са били поискани при извикване на заявката (в случая 25).

При грешка услугата връща трицифрен HTTP статус код за грешка и резултат в следния формат:

Body

{„erorrCode“:“ERR_INVALID_FILE“,“errorMsg“:“Invalid file name or password“}

Текстът в полето errorMsg е само информативен и не е предназначен за машинна обработка. Кодовете на грешките в полето errorCode са следните:

HTTP Code

Error Code

Description

404

ERR_INVALID_FILE

Invalid file name or password

417

ERR_INVALID_OFFSET

Invalid offset

416

ERR_INVALID_SIZE

Invalid number of bytes

500

ERR_GENERAL

General error (the server cannot fulfil the request)

Качване на видео файл

При качване на ново видео, клиентът го разделя на четни и нечетни байтове и качва отделните части с две отделни заявки към някой от четните и някой от нечетните сървъри. Клиентът сам избира към кой от сървърите да качи всяка от половините, а сървърите след това могат по желание да репликират качените части от файлове или да ги преместят на друг сървър. При качване на част от файл, клиентът задава парола за достъп, име на файла и дължина на файла.

Например, ако трябва да качим файл „example.mp4“ с размер 200 001 байта, ще качим четните битове (100 001 байта след допълване) на някой от четните сървъри и нечетните битове (100 001 байта след допълване) на някой от нечетните сървъри.

За качване на част от файл клиентът изпълнява заявка в следния формат:

URL

http://service-url/odd-server/upload-file-chunk

Method: POST

Body

{„file“:“WeiHuiChunWang.mp4″,“password“:“s0m3@ssw0rd“,“type“:“odd“,“bytes“:“ QmVzdCByZWdhcmRzIGZyb20gTmFrb3Yh“}

За простота цялата четна или нечетна част от даден файл се качва на веднъж. Това би могло да създаде трудности при обемни файлове (примерно стотици мегабайти), така че по желание може да се имплементира и качване на серии от по-малки части.

Името на файла може да е произволен непразен текст до 200 символа, уникален за системата. Паролата е стринг във формат, описан по-горе в секцията „извличане на списък от споделените файлове“. Типът на качения файл може да е единствено „odd“ или „even“ и трябва да съответства на типа на сървъра. Съдържанието на четните / нечетните битове от файла трябва да се изпрати като поредица от байтове, кодирани като BASE64 стринг.

При успех услугата връща HTTP статус код 200 и резултат в следния формат:

Body

{status:“OK“}

При грешка услугата връща трицифрен HTTP статус код за грешка и резултат в следния формат:

Body

{„erorrCode“:“ERR_INVALID_FILE“,“errorMsg“:“Invalid file name or password“}

Текстът в полето errorMsg е само информативен и не е предназначен за машинна обработка. Кодовете на грешките в полето errorCode са следните:

HTTP Code

Error Code

Description

404

ERR_INVALID_FILE

The specified file name is invalid

404

ERR_INVALID_PASSWORD

The specified password is invalid

404

ERR_INVALID_TYPE

Invalid chunk type (valid ones are ‘odd’ and ‘even’)

413

ERR_INVALID_SIZE

The file is empty or too long

403

ERR_DUPLICATE

File name duplicated

417

ERR_INVALID_CONTENT

The file content is invalid BASE64-encoded sequence of bytes

500

ERR_GENERAL

General error (the server cannot fulfil the request)

Незадължителна сървърна функционалност

Освен задължителната функционалност всеки може да имплементира допълнителна сървърна функционалност с цел предоставяне на допълнителни функции, координация между сървърите на системата, репликация (дублиране) на съдържание, разпределение на натоварването и други.

Незадължителната функционалност може да бъде имплементирана по начин, който прецените, че е най-удачен. За нея няма спецификация, която да следвате. Сървърите на торент мрежата могат да комуникират по между си и да обменят данни по всякакви канали и протоколи.

Функционалност на клиента

Втората част от задачата е приложната. В нея се изисква да разработите клиент за китайската торент система, който служи да възпроизвежда видео, стопанисвано в нея, съединявайки четните и нечетните битове за даден споделен файл. Клиентът трябва да позволява свързване, извличане на актуален списък със сървърите на системата, извличане на имената на споделените в системата видео файлове, възпроизвеждане на споделен видео файл и качване (споделяне) на файл.

По желание клиентът може да работи едновременно и като сървър (на принципа на peer-to-peer мрежите) като предоставя освен клиентската функционалност и всички функции на сървър (ако решите да се захванете с този подход, имайте предвид, че не е никак лесен за имплементиране).

Клиентът може да е настолно, уеб базирано или мобилно приложение, разработено с технология по избор.

Свързване към торент системата и извличане на актуален списък от сървъри

При стартирането си клиентът за китайската торент мрежа зарежда предварително зададен списък от сървъри и опитва да се закачи за някой от тях като ги пробва подред. При успешно свързване той извлича актуален списък със сървърите на системата и обновява своя списък (който може да е например локален файл). Имайте предвид, че е нормално за торент мрежите някои от сървърите да не работи и трябва да се предвиди закачане за друг сървър при неуспешно свързване.

Извличане на списъка от видео файлове по дадена парола

Системата трябва да позволява извличане и визуализиране на списък от всички файлове, достъпни по дадена парола. За целта клиентът трябва да позволява въвеждане на парола (евентуално празна) и да визуализира файловете от торент мрежата, достъпни по тази парола.

Възпроизвеждане на видео файл

След извличането на файловете, достъпни по дадена парола потребителите могат да поискат възпроизвеждане на избран видео файл. Тогава клиентът трябва да се свърже към два от сървърите на системата (един четен и един нечетен) и да започне възпроизвеждане на видеото. Ако някой от сървърите не отговаря, трябва да се пробва следващият в списъка. Ако всички четни или всички нечетни сървъри не отговарят, трябва да се съобщи за грешка.

За да работи бързо възпроизвеждането на видео файл, се препоръчва частите от файла да се теглят на фрагменти с малък размер (например 200-300 KB) и да се имплементира буфериране (четене на данните за няколко секунди напред). Буферирането избягва накъсване при забавяне на мрежата.

По желание може да се имплементират функции като start, stop, пауза и други.

Качване на част от файл

При качване на файл потребителят избира локален файл от своята локална файлова система и задава парола (може и празна) за достъп до файла, след което клиентът избира един от четните и един от нечетните сървъри и изпраща двете половини на файла към тях.

По желание може да се имплементира качване на серия файлове, както и визуализация на напредъка по качването по подходящ начин.

Тестова имплементация на сървърната функционалност

Ако не сте разработили сървърната част на проекта, можете да си тествате клиента върху тестовата имплементация на китайската торент мрежа, която авторският екип на задачата е подготвил. Тя е достъпна от облака на AppHarbor от следните URL адреси:

http://torrent-hangzhou02.apphb.com/ChineseTorrent.svc (четен сървър)

http://torrent-beijing01.apphb.com/ChineseTorrent.svc (нечетен сървър)

Имплементацията на REST услугите от китайската торент мрежа е примерна и е предназначена само за тестови цели. С цел спестяване на ресурси всички видео файлове, които качите на посочените сървъри, мога да бъдат автоматично изтрити след няколко минути. За тестване на примерната имплементация можете да ползвате инструменти като http://apikitchen.com.

Критерии за оценяване

Критериите за оценяване на задачата за китайската торент система са разделени на две части (сървърна и клиентска).

Сървърна част

Сървърната част се оценява с до 12 точки по следните критерии:

Дизайн на системата (оценява се по изпратената документация) – архитектура (клиент-сървър, peer-to-peer или хибридна), начин на взаимодействие между сървърите, организация и съхранение на данните, криптография и т.н.

3 т.

Функционалност „извличане на сървърите“

1 т.

Функционалност „извличане на списък със споделените файлове“

1 т.

Функционалност „изтегляне на част от видео файл“

1 т.

Функционалност „качване на видео файл“

1 т.

Незадължителна функционалност (например репликация на файлове, преместване на файлове с цел балансиране на натоварването, следене и актуализиране на списъка със сървъри, включване на нови сървъри, работа в режим peer-to-peer и др.)

5 т.

Голяма част от оценката е върху незадължителната функционалност, тъй като една добра торент система обикновено има много по-богата и по-сложна функционалност, отколкото са описаните в условието задължителни функции.

Клиентска част

Клиентската част се оценява с до 8 точки (защото е по-лесна от сървърната). Оценката се базира на следните критерии:

Коректност: свързване към торент мрежата

1 т.

Коректност: извличане на списък от файлове по дадена парола

1 т.

Коректност: възпроизвеждане на видео файл

1 т.

Коректност: качване на видео файл

1 т.

Ползваемост (usability) – доколко е удобна и интуитивна работата с приложението

1 т.

UI дизайн – доколко потребителският интерфейс е приятен за работа и предлага добра визуализация

1 т.

Оригинални функции или решения, които да впечатлят журито

2 т.

Декларация за необвързване

Целта на настоящата задача е да насърчи креативното мислене на участниците в конкурса и да им даде възможност да демонстрират своите алгоритмични и технологични умения. Авторите на задачата осъзнават, че китайската торент система би могла да се използва за споделяне на материали, защитени с авторски права, но това може да се извършва и с всяка друга система за споделяне на файлове. Разработването на системата е с чисто учебна цел и по никакъв начин не нарушава българското и европейското законодателство. Всеки, който използва китайската торент система по непозволени начини, носи сам отговорност за действията си.

Допълнителни изисквания

Задачите позволяват използването на различни езици за програмиране и технологии (например PHP, Perl, Python, Ruby, C, C++, C#, Java, Delphi, WPF, XAML, Windows Forms, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows среда съгласно общите условия на конкурса.

Участниците в конкурса трябва да предадат сорс код на сървърната и клиентската част на проекта, който са разработили (или само едната част, ако не са успели да разработят и двете) + описание на начина, по който е организирана сървърната система (архитектурни решения, протоколи за комуникация, алгоритми и други).

 

Анализ на трети кръг и резултати

Създаването на торент система не е лека задача. Това си пролича и от този кръг на състезанието. С няколко думи, участието не беше силно, но поне го имаше. Не можем да кажем, че видяхме много напълно работещи решения, а повечето състезатели се бяха отказали от този кръг. Всъщност, получихме точно едно решение и титлата за победител, за разлика от в предишните кръгове, никак не е спорна.

Естествено, постарахме се да оценим предаденото решение, по критериите, по които се движехме и в миналите кръгове. Вижда се, че състезателите са се постарали и решението получи близък до максималния брой точки, като това което го раздели от максималния резултат беше най-вече критерият ползваемост.

Поздравяваме участвалите за усърдната работа и се надяваме, че следващите кръгове ще бъдат по-интересни и по-привлекателни за всички.

Крайни резултати

Това е класирането базирано на крайните резултати от трети кръг на състезанието, образувани от сбора на точките от клиентските и сървърните части, предадени от състезателите. Поздравления за резултатите! Благодарим Ви за участието!

 

Отбор

 

Краен резултат

 

Клиентска част

Сървърна част

Георги Ангелов, Станислав Гатев

14

7

7

(извиняваме се ако сме сгрешили изписването на нечие име)