-
Notifications
You must be signed in to change notification settings - Fork 0
/
dissertation.tex
2665 lines (2122 loc) · 197 KB
/
dissertation.tex
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass{lib/styles/default-style}
\begin{document}
\pagestyle{default-numbered}
\startPageCountFrom{5}
\tableofcontents
\newpage
\unnumberedSection{ПЕРЕЛІК УМОВНИХ СКОРОЧЕНЬ}
PoW --- Proof of Work
PoS --- Proof of Stake
DPoS --- Delegated Proof of Stake
BFT --- Byzantine Fault Tolerance
PBFT --- Practical Byzantine Fault Tolerance
HBBFT --- Honey Badger Byzantine Fault Tolerance
PEG --- Parsing expression grammar
CFG --- Context free grammar
VM --- Virtual Machine
PVM --- Program virtual machine
MRE --- Managed runtime environment
ISA --- Instruction set architecture
EVM --- Ethereum Virtual Machine
RPC --- Remote Procedure Call
REST --- Representational State TransferI/O
I/O --- Input/Output operations
\newpage
\unnumberedSection{ВСТУП}
З кожним роком кількість інформації непреривно збільшується, а кількість цифрової інформації і поготів,
та, судячи з усього, ця тенденція не планує припинятися. Із ростом кількості цифрової інформації, зростає і
кількість ресурсів, необхідних для обробки цієї інформації. Хоча вартість цих ресурсів непреривно зменшується,
проте великі системи потребують чимало коштів. Системи стають складнішими, необхідно ще більше потужностей для обробки інформації.
Такі системи складно підтримувати, саме тому і почався пошук альтернативних рішень. В останній час все більше людей дивиться у бік
децентралізованих рішень. Проте, у існуючих рішень є проблеми із масштабованість та швидкістю транзакцій в тому, чи іншому вигляді.
Вирішення даних проблем може кардинально змінити укореніле уявлення про системи обробки інформації, та дати поштовх до створення
більш оптимальних систем.
Результати можуть бути використані у всіх галузях виробництва, де тим чи іншим чином оброблюється інформація.
Саме тому обрана проблематика дослідження є вельми актуальною на даний момент.
Метою даної магістерської дисертації є дослідження концепцій для створення гнучкої платформи для розробки швидких децентралізованих додатків
та реалізація прототипу платформи. Проаналізувати існуючі платформи, запропонувати алгоритм консенсусу даних в розподілених системах,
алгоритм сереалізації даних, механізми для оптимізації використання ресурсів в децентралізованих системах,
спроектувати систему котра підтримує запропоновані концепції.
Відповідно до мети роботи необхідно вирішити такі завдання:
\listDefault{
\item розглянути поняття про платформи для створення децентралізованих додатків;
\item описати устрій спроектованої системи для розробки блокчейн додатків;
\item описати реалізацію запропонованих концепцій;
\item навести результати випробовування розробленого рішення;
\item розробити стартап-проект.
}
Об'єкт дослідження – платформа для створення децентралізованих додатків.
Предметом дослідження є концепції побудови децентралізованих додатків, які дозволяють створювати ефективні рішеня.
Основним здобутком дисертації є методологія проектування алгоритму консесусу, для
швидкого та надійного обміну даними у децентралізованих мережах,
проектування алгоритму пошуку вузлів, для стабілізації децентралізованої системи та
проектування механізмів використання ресурсів для підтримки децентралізованих додатків, зокрема
проектування та оптимізація програмних віртуальних машин для виконання криптографічних операцій
та оптимізація механізма виконання I/O операцій.
Отримана в результаті виконаної дослідницької роботи методологія
оптимізації були опубліковані у статті «ЗАХИЩЕНА P2P КОМУНІКАЦІЯ НА ОСНОВІ ТЕХНОЛОГІЇ BLOCKCHAIN» в
сучасному науковому журналі «Інформаційне суспільство: технологічні,
економічні та технічні аспекти становлення» в 2019 році.
\startSection{АНАЛІЗ ІСНУЮЧИХ ПЛАТФОРМ ДЛЯ СТВОРЕННЯ ДЕЦЕНТРАЛІЗОВАНИХ ДОДАТКІВ}
\subsection{Платформа для створення додатків Ethereum}
Платформа для створення практично будь-яких децентралізованих
онлайн-сервісів на базі блокчейна (Đapps), що працюють на базі розумнихĐapps), що працюють на базі розумних), що працюють на базі розумних
контрактів. Реалізована як єдина децентралізована віртуальна машина. Ідея була
втілена 30 липня 2015 року. Оскільки Ethereum сильно спрощує і здешевлює
впровадження блокчейна, його впроваджують як великі гравці, такі як Microsoft, IBM, Acronis,
Сбербанк, банківський консорціум R3, так і нові стартапи.
У кінці 2013 року Ethereum запропонував дослідник
і програміст криптовалют Віталік Бутерін. Розвиток фінансувався через інтернет-краудфандінг, який проходив
у липні-серпні 2014 року. Потім система вийшла у світ 30 липня 2015 року, при цьому 72 мільйони монет були
створені "попередньо". Це становить близько 68 відсотків загального обсягу постачання у 2019 році [1].
У 2016 році,
внаслідок експлуатації вразливості в програмному забезпеченні проекту, та подальшого розкрадання ефіру на суму
50 мільйонів доларів, Ethereum було розділено на дві окремі блокчейн --- нова окрема версія стала Ethereum (ETH), а оригінал продовжувався
як Ethereum Classic (ETC).
Ethereum є дуже потужною платформою розробки через технологію розумних контрактів
Розумний контракт --- це код, який працює на EVM.
Смарт-контракти можуть приймати та зберігати ефір, дані або комбінацію обох.
Потім, використовуючи логіку, запрограмовану в договорі, він може поширювати
цей ефір на інші рахунки або навіть інші смарт-контракти.
Як приклад, приведемо відомий контракт з Бобом та Алісою (рисунок \ref{img:alice-bob-contract-example}). Аліса хоче найняти Боба, щоб побудувати їй внутрішній дворик,
і вони використовують контракт для депонування (місце для зберігання грошей, доки умова не буде виконана),
щоб зберігати свій ефір до остаточної транзакції.
\printImage[1][0.3]{alice-bob-contract-example}{Приклад виконання розумного контракта Боба та Аліси}
Розумні контракти пишуться мовою, що називається "Solidity". Solidity має статичний тип і підтримує механізм успадкування,
бібліотеки та складні,визначені користувачем типи. Синтаксис Solidity схожий на JavaScript [2].
Програми, що використовують смарт-контракти для їх обробки, називаються "децентралізованими програмами"\enspace або "dapps".
Користувацькі інтерфейси для цих daaps складаються з відомих мов, таких як HTML, CSS та JavaScript.
Саму програму можна розмістити на традиційному веб-сервері або на децентралізованій файловій службі, наприклад, Swarm або IPFS.
Враховуючи переваги блокчейна Ethereum, dapp може бути рішенням для багатьох галузей, включаючи, але не обмежуючись ними:
\listDefault{
\item бухгалтерський облік;
\item фінанси;
\item логістика;
\item нерухомість;
\item електронні магазиги (маркетплейси).
}
\subsection{Платформа для створення додатків Hyperledger}
Комплексний проект розробки блокчейну з відкритим вихідним кодом та пов'язаних з цим інструментів,
який було розпочато Linux Foundation у грудні 2015 року. Основною метою проекту є підтримка спільної
розробки мереж з розподіленим реєстром, заснованих на технології блокчейн.
У грудні 2015 року Linux Foundation анонсувала створення проекту Hyperledger.
Імена компаній-засновників були оголошені у лютому 2016, до яких 29 березня того ж року приєдналися ще
десять учасників і було затверджено склад ради правління. 29 травня виконавчим директором проекту призначили Брайана Белендорфа [3].
Метою проекту є посилення міжгалузевої співпраці за допомогою технології блокчейну та мереж з розподіленим реєстром.
Особлива увага приділяється підвищенню продуктивності та надійності цих систем (у порівнянні з аналогічними криптовалютними розробками),
аби вони могли використовуватися технологічними, фінансовими та компаніями-постачальниками в масштабах глобальних комерційних оборудок.
Проект поєднуватиме незалежні відкриті стандарти та протоколи за допомогою фреймворків для створення специфічних модулей, включно з
блокчейнами з власними механізмами досягнення консенсусу та порядком збереження даних, а також ідентифікаційними сервісами, контролем
доступу та смарт-контрактами. Попри чутки, згідно з заявою Брайана Белендорфа, введення та використання власної криптовалюти у проекті
ніколи не відбудеться.
На початку 2016 проект розпочав розглядати пропозиції щодо створення вихідного коду
та інших ключових технологічних елементів. Однією з перших пропозицій було поєднати попередні розробки Digital Asset,
механізм досягнення консенсусу від Blockstream та OpenBlockchain від IBM. Пізніше ця технологія отримала назву Fabric (рисунок \ref{img:hyperledger-struct}).
\printImage[1][0.7]{hyperledger-struct}{Структурна схема платформи Hyperledger Fabric}
У травні розпочалася розробка мережі з розподіленим реєстром Sawtooth від Intel.
12 червня 2017 року проект анонсував готову до промислового використання версію Hyperledger Fabric 1.0 який одразу
почав набирати популярність на ринку ICO. Того ж місяця London Stock Exchange Group, спільно з IBM, заявила про початок
розробки блокчейн-платформи на базі Hyperledger Fabric для випуску цифрових акцій італійських компаній.
У серпні 2017, компанія Oracle приєдналася до консорціуму Hyperledger і оголосила про початок розробки власного хмарного блокчейн-сервісу.
У вересні 2017 Королівський банк Канади почав використовувати Hyperledger для міжбанківських розрахунків з США.
Hyperledger забезпечує такі функціональні можливості для мережі:
\listDefault{
\item управління ідентичністю --- Hyperledger Fabric надає послугу посвідчення членства,
яка керує ідентифікаторами користувачів та аутентифікує всіх учасників мережі,
списки контролю доступу можуть використовуватися для надання додаткових рівнів дозволу через авторизацію конкретних
мережевих операцій;
\item приватність та конфідейційність --- Hyperledger дозволяє конкуруючим інтересам бізнесу
та будь-яким групам, які потребують приватних, конфіденційних транзакцій, співіснувати в одній і тій же дозволеній мережі, через
приватні канали, які представляють із себе обмежені шляхи обміну повідомленнями, які можна використовувати для
забезпечення конфіденційності та конфіденційності транзакцій для конкретних підмножин членів мережі,
усі дані, включаючи інформацію про трансакції, учасників та каналів, на каналі є невидимими та недоступними
для будь-яких членів мережі, яким явно не надано доступ до цього каналу;
\item ефективна обробка --- Hyperledger Fabric призначає мережеві ролі за типом вузла,
для забезпечення одночасності та паралелізму в мережі виконання транзакцій відокремлено
від впорядкування та зобов'язань транзакцій. Виконання транзакцій перед їх
замовленням дозволяє кожному вузлу однорангових обробляти одночасно кілька транзакцій,
це одночасне виконання збільшує ефективність обробки кожного партнера та прискорює доставку транзакцій до служби замовлення;
\item chaincode --- це визначення програмного забезпечення як активів та інструкція щодо
транзакцій для зміни активів, chaincode виконує правила читання або зміни пар ключових
значень або іншої інформації бази даних стану, його функції виконуються в базі даних поточного стану
і ініціюються через пропозицію транзакцій.
}
\subsection{Платформа для створення додатків Corda}
Платформа з відкритим вихідним кодом, яка дозволяє підприємствам здійснювати операції безпосередньо
та у суворій конфіденційності за допомогою інтелектуальних контрактів, зменшуючи витрати на операції
та ведення записів та оптимізацію бізнес-операції. У світі блокчейн платформ, де всі дані передаються
всім учасникам, сувора модель конфіденційності Corda дозволяє бізнесу здійснювати операції без проблем.
R3 поставляє два повністю сумісні дистрибутиви платформи --- Corda, безкоштовне завантаження коду,
доступного на GitHub та Corda Enterprise, комерційній версії, яка пропонує функції та послуги, які налаштовані
для сучасних підприємств [4].
Основоположним об'єктом в концепції є "державний"\enspace об'єкт, який є цифровим документом,
який реєструє існування, зміст та поточний стан угоди між двома або більше сторонами.
Він призначений для обміну лише з тими, хто має законну причину бачити це.
Для забезпечення узгодженості глобальної спільної системи, де не всі дані видно всім учасникам,
використовують безпечні криптографічні хеші для ідентифікації сторін і даних, а також для зв’язку користувачів
з попередніми перетвореннями,
щоб забезпечити ланцюги походження. Головну базу даних визначають як сукупність незмінних об'єктів стану.
На відміну від більшості існуючих сьогодні платформ для створення блокчейнів додатків, Corda була побудована з чіткою метою
запису та забезпечення ділових угод між торговими партнерами.
Як такий, платформа використовує унікальний підхід до розподілу даних та семантики транзакцій,
підкреслюючи особливості розподілених баз даних, привабливих для фірм, а саме надійне виконання контрактів в автоматизованому
та примусовому виконанні.
На рисунку \ref{img:corda-example} зображений приклад, державний об'єкт,
який представляє депозит у розмірі 100 фунтів стерлінгів у комерційному банку,
що належить вигаданій судноплавній компанії.
Державний об'єкт посилається на код договору,
який регулює його переходи, який, ймовірно,
буде написаний один раз і повторно використаний величезною кількістю штатів, і може посилатися на хеш тої, що регулює юридичну прозу.
\printImage[1][0.7]{corda-example}{Схема роботи децентралізованого банку на платформі Corda}
\subsection{Платформа для створення додатків Quorum}
Quorum --- протокол розподіленої бази даних на основі Ethereum, розроблений для забезпечення таких галузей,
як фінанси, логістика, роздрібна торгівля, нерухомість, тощо з дозволеною реалізацією Ethereum,
що підтримує конфіденційність транзакцій та контрактів [5].
Quorum включає мінімалістичне відгалуженя клієнта Go Ethereum (geth) і,
як такий, використовує роботу, яку розпочала спільнота розробників Ethereum.
Основними відмінностями Quorum є:
\listDefault{
\item конфіденційність транзакцій та контрактів;
\item кілька механізмів консенсусу на основі голосування;
\item мережеве/однорангове управління дозволами;
\item більш висока продуктивність.
}
На даний момент, Quorum складається з архітектурних компонентів, зображених на рисунку \ref{img:quorum-architecture}
\printImage[1][0.4]{quorum-architecture}{Схема логічної архітектури Quorum}
\startSection{КОНЦЕПЦІЯ ТА ТЕХНОЛОГІЧНІ ПАРАДИГМИ ПЛАТФОРМИ}
Для того, щоб розробити оптимальну платформу, необхідно вирішити ряд проблем,
пов'язаних із децентралізованими системами, серед них:
\listEnumerated{
\item низька швидкодія, яка обумовлена декількома причинами:
\listInnerEnumerated{
\item повільні алгоритми консенсусу;
\item неоптимальні структури збереження данних;
\item неоптимальні формати для обміну даними;
}
\item завищене використання платформою ресурсів --- децентралізованим системам необхідно
виконувати більше операцій, тому що уся бізнес логіка знаходиться на клієнтській стороні,
тому, якщо клієнту не вистачає ресурсів, то це може спричинити відмову функціонування додатку;
\item незручний доступ до мережі --- користувачам необхідно встановлювати додаткове ПО,
для того, щоб потрапити до системи.
}
В даному розділі розглянуто концепції та механізми, які допоможуть усунути ці недоліки.
\subsection{Програмна віртуальна машина}
Програмна віртуальна машина (PVM), іноді називається віртуальною машиною програми
або керованим середовищем виконання (MRE),
працює як звичайна програма всередині операційної системи та підтримує єдиний процес.
Вона створюється при запуску цього процесу і руйнується, коли він закінчується.
Її мета полягає в тому, щоб створити незалежне від платформи середовище програмування,
яке відкидує деталі апаратного обладнання або операційної системи і
дозволяє програмі виконуватися однаково на будь-якій платформі [6].
Процес VM забезпечує абстракцію високого рівня
--- мову програмування високого рівня (порівняно з низькорівневою абстракцією ISA системи VM).
Програмна віртуальна машина реалізуються за допомогою інтерпретатора;
ефективність, порівнянна зі скомпільованими мовами програмування, може бути досягнута за допомогою компіляції "just in time".
Цей тип VM набув популярності в мові програмування Java (рисунок \ref{img:hotspot-jvm}), яка реалізована за допомогою віртуальної машини Java.
Інші приклади включають віртуальну машину Parrot і .NET Framework, яка працює на VM під назвою " Common Language Runtime".
Усі вони можуть служити шаром абстракції для будь-якої мови комп'ютера.
\printImage[1][0.7]{hotspot-jvm}{Архітектура Hotspot JVM}
Особливим випадком віртуальних машин управління є системи,
які абстрагуються над механізмами зв'язку (потенційно гетерогенного) комп'ютерного кластеру.
Такий тип VM складається не з одного програмного процесу, а з одного процесу на фізичній машині в кластері.
Вони розроблені для полегшення завдання програмування багатопоточних додатків, дозволяючи програмісту зосередитися на алгоритмах,
а не на механізмах зв'язку, що забезпечуються взаємозв'язком та ОС.
Вони не приховують факту, що спілкування відбувається, і не намагаються представити кластер як єдину машину.
На відміну від інших віртуальних машин, ці системи не забезпечують конкретної мови програмування,
але вбудовані в існуючу мову;
зазвичай така система забезпечує прив'язку для декількох мов (наприклад, C та Fortran).
Прикладами є паралельна віртуальна машина (PVM)
та інтерфейс передачі повідомлень (MPI).
Вони не є строго віртуальними машинами, оскільки додатки, що працюють на них, все ще мають
доступ до всіх служб ОС і тому не обмежені системою.
Тож, із зазначених переваг можна виділити:
\listDefault{
\item швидкий час розробки --- написання програми не займе багато часу,
оскільки розробникам не потрібно створювати функції для окремих платформ та специфікацій;
\item безпечний код --- керовані режими виконання просувають безпечніший код,
знімаючи з розробників частину відповідальності за безпеку та управління обладнанням;
\item низькі витрати на розгортання --- компонентна архітектура спрощує та швидше розгортає додатки у корпоративному середовищі,
що характеризується багатьма платформами, пристроями та застарілими системами;
\item більш якісне програмне забезпечення --- керований час виконання звільняє розробників зосереджуватися
на бізнес-логіці та коді, специфічних для програми, зменшуючи при цьому кількість помилок кодування;
\item агностична платформа --- завдяки виконанню часу перекладу між вашим додатком та операційною системою
наявна можливість писати код один раз, дозволяючи клієнтам запускати програму в декількох системах;
\item чистота коду --- простота функціоналу дозволяє писати модульний код, який можна переробити в нові програми та нові системи.
}
Отже, із вище зазначених переваг можна точно сказати, шо віртуальна машина необхідна для реалізації платформи, так як це допоможе
в реалізації кросплатформеності та створить безпечну середу для виконання криптографічних операції [7].
\subsection{Протокол серіалізації даних}
Серіалізація даних --- це процес перетворення об'єктів даних (рисунок \ref{img:serealization-example}),
що знаходяться у складних структурах даних,
у потік байтів для цілей зберігання, передачі та розповсюдження на фізичних пристроях [8].
\printImage[1][0.7]{serealization-example}{Узагальнений алгоритм серіалізації}
Комп'ютерні системи можуть відрізнятися за своєю апаратною архітектурою, ОС,
механізмами адресації. Внутрішні бінарні представлення даних також відповідно
змінюються в кожному середовищі. Зберігання та обмін даними між такими різними середовищами
вимагає нейтрального для платформи та мови формату даних, який розуміють усі системи.
Після передачі серіалізованих даних з вихідної машини на машину призначення
здійснюється зворотний процес створення об'єктів із послідовності байтів, що називається десеріалізацією.
Реконструйовані об'єкти --- це клони вихідного об'єкта.
Вибір формату серіалізації даних для програми залежить
від таких факторів, як складність даних, потреба в читабельності людини, швидкість
та обмеження місця для зберігання. XML, JSON, BSON, YAML, MessagePack і Protobuf --- деякі
часто використовувані формати серіалізації даних.
Комп'ютерні дані зазвичай організовані в структурах даних, таких як масиви,
таблиці, дерева, класи. Коли структури даних потрібно зберігати або передавати
в інше місце, наприклад, через мережу, вони серіалізуються.
Для простих лінійних даних (число або рядок) нічого робити.
Серіалізація стає складною для вкладених структур даних та посилань на об'єкти.
Коли об'єкти вкладені в кілька рівнів, наприклад, у деревах, він згортається на ряд
байтів, і достатньо інформації (наприклад, порядок обходу) включається для відновлення
початкової структури дерева на стороні призначення.
Коли об'єкти із посиланнями вказівників
на інші змінні члена серіалізовані, посилаються об'єкти відстежуються та
серіалізуються, забезпечуючи, щоб той самий об’єкт не був серіалізований більше одного разу.
Однак усі вкладені об'єкти теж повинні бути серіалізованими.
Нарешті, серіалізований потік даних зберігається у послідовності байтів,
використовуючи стандартний формат.
ISO-8859-1 --- популярний формат для 1-байтного представлення англійських символів та цифр.
UTF-8 --- світовий стандарт кодування багатомовних, математичних та наукових даних; кожен символ може приймати 1-4 байти даних у Unicode.
На рисунку \ref{img:serialization-data-example} зображено приклад серіалізації структури у текстовий формат.
\printImage[1][0.6]{serialization-data-example}{Приклад серіалізації даних}
Якщо визначати, які з форматів для яких цілей підходять краще, то можна визначити, що:
\listDefault{
\item швидкість --- за даними Uber Engineering, бінарні формати швидші , ніж текстові формати,
Google Protobuf має найкращі показники на сьогодні (рисунок \ref{img:protobuf-example}) а при стиснені даних показники
будуть ще більші, проте для додатків, які не потребують
інтенсивного використання даних або в режимі реального часу,
JSON є кращим із-за читабельності та відсутності схем;
\item розмір даних --- це стосується фізичного простору в байтах після серіалізації,
для невеликих даних стислі дані JSON займають більше місця в порівнянні з бінарними форматами, як Protobuf,
і, як правило, бінарні формати завжди займають менше місця;
\item корисність --- людиночитаємі формати, такі як JSON, природно переважніші перед бінарними форматами,
для складних типів даних бібліотеки міжплатформової серіалізації дозволяють визначати структуру даних на схемах
(для текстових форматів) або IDL (для бінарних форматів);
\item сумісність або розширюваність --- JSON є закритим форматом,
XML є середнім за версією схеми, а зворотна сумісність (розширювані схеми) найкраще обробляється Protobuf.
}
\printImage[1][0.6]{protobuf-example}{Графік відношеня швидкості роботи Protobuf до розмірів вихідних даних}
Навіть у Big Data серіалізація стосується перетворення даних у портативні потоки байтів.
Але управління схемою --- ще одна проблема, яку необхідно брати до уваги.
Проблеми з узгодженістю даних, такі як пробіли або неправильні значення даних,
можуть бути дуже дорогими, залучаючи великі зусилля щодо очищення даних.
Наступний важливий аспект --- можливість легко розділяти
та реконструювати дані (наприклад, MapReduce).
JSON або XML можуть не працювати належним чином.
Apache Hadoop має власний формат серіалізації на основі схеми під назвою Avro (рисунок \ref{img:avro}),
схожий на Protobuf. Схеми Apache також визначаються на основі JSON.
Apache Hadoop використовує RPC для розмови з різними компонентами.
\printImage[1][0.6]{avro}{Функціональна схема системи сереліалізації даних, побудованої з використанням Avro}
Механізм серіалізації є важливою частиною платформи, оскільки не тільки дозволяє досягти агностичності, але і збільшити
швидкодію та зменшити об’єм сховища даних.
\subsection{Збереження даних}
На відміну від клієнт-серверної архітектури, де існує централізоване сховище даних, децентралізовані мережі не можуть
так працювати.
Тому дані зберігаються на кожній машині, яка підключена до централізованої мережі.
Що стосується розподіленої блокчейн-мережі, кожен учасник мережі підтримує, затверджує та оновлює нові записи.
Структура даних, в якій вони зберігаються, називається blockchain (рисунок \ref{img:blockchain-struct}).
\printImage[1][0.5]{blockchain-struct}{Схема blockchain структури даних}
За задумом, блокчейн стійкий до модифікації даних.
Це "відкрита, розподілена книга, яка може ефективно і оперативно фіксувати транзакції між двома сторонами".
Для використання в якості розподіленого сховища, блокчейн,
як правило, управляється одноранговою мережею,
яка колективно дотримується протоколу для міжвузлового зв'язку
та перевірки нових блоків. Після запису дані в будь-якому
даному блоці не можуть бути змінені заднім числом без зміни всіх наступних блоків,
що вимагає консенсусу більшості мережі.
Проте, із часом, об'єм даних буде рости, це будет спричиняти зповілненя пошуку та оновленя цих даних у кожного
клієнта мережі. Саме тому, для оптимального представлення даних використовують структуру даних під назвою
"дерево Меркле" (рисунок \ref{img:merkle}).
\printImage[1][0.5]{merkle}{Приклад структури дерева Меркле}
Меркелеве дерево - це структура, яка дозволяє ефективно і
безпечно перевіряти вміст у великому масиві даних.
Ця структура допомагає перевірити узгодженість та зміст даних.
Дерево Меркле підсумовує всі транзакції в блоці,
створюючи цифровий відбиток пальця всього набору транзакцій,
тим самим дозволяючи користувачеві перевірити, включена чи ні транзакція в блок.
Дерева Меркле створюються багаторазово хешуючими
парами вузлів, поки не залишиться лише один хеш
(цей хеш називається кореневим хешом, або корінь Меркле).
Вони будуються знизу вгору, з хешей окремих транзакцій (відомих як ідентифікатори транзакцій).
Кожен вузол листів --- це хеш даних транзакцій,
а кожен нелистовий вузол --- хеш попередніх хешів.
Мерклеві дерева є двійковими і тому потребують парної кількості листових вузлів.
Якщо кількість транзакцій непарна, останній хеш дублюється один раз,
щоб створити парну кількість вузлів листів.
В даній роботі не будуть детально розглядатися підходи до збереження даних, так як це добре досліджена тема.
\subsection{Протокол консенсусу}
Принциповою проблемою розподілених обчислювальних і багатоагентних систем
є досягнення загальної надійності системи за наявності низки несправних процесів.
Це часто вимагає від процесів узгодження певної вартості даних, яка потрібна під час обчислення.
Приклади застосувань консенсусу включають, чи слід здійснювати транзакцію в базі даних, узгоджуючи особу лідера,
центральну машинну реплікацію (генезис) та атомарну трансляцію.
Однак у процесі застосування технології blockchain виникає багато проблем і питань,
серед яких велике питання --- як розробити відповідний протокол консенсусу.
Консенсус блокчейна полягає в тому, що всі вузли підтримують однакове розподілене сховище.
У традиційній архітектурі програмного забезпечення консенсус навряд чи є проблемою через існування центрального сервера,
отже, інші вузли потрібно лише узгодити з сервером. Однак у розподіленій мережі, такій як блокчейн, кожен вузол є і хостом,
і сервером, і йому потрібно обмінюватися інформацією з іншими вузлами, щоб досягти консенсусу. Іноді деякі вузли будуть
працювати в режимі онлайн або в режимі офлайн, а також з’являться деякі шкідливі вузли, що серйозно вплине на систему або знищить
процес консенсусу. Тому відмінний консенсус-протокол може допустити виникнення цих явищ і мінімізувати шкоду,
щоб не вплинути на кінцевий результат консенсусу.
Крім того, прийнятий системою протокол консенсусу
також повинен бути придатним для типу блокчейн, який використовується системою. Загалом, можна виділити три основні типи blockchain:
загальний блокчейн, консорціумний блокчейн та приватний блокчейн.
Кожен тип blockchain має різні сценарії застосування.
Таким чином, прийнятий протокол консенсусу повинен відповідати вимогам конкретного сценарію застосування.
\subsubsection{Алгоритм Proof of Work}
PoW вибирає один вузол, щоб створити новий блок у кожному раунді консенсусу шляхом конкуренції з
обчислювальної потужності. У змаганні вузлам-учасникам потрібно розв'язати криптографічну проблему.
Вузол, який першим вирішить задачі, може мати право створити новий блок.
Потік створення блоку в PoW представлений на рисунку \ref{img:flow-pow}.
\printImage[1][0.6]{flow-pow}{Cхема роботи PoW алгоритму}
Розв'язати проблему, яку представляє PoW дуже важко.
Вузлам потрібно постійно коригувати значення nonce, щоб отримати правильну відповідь,
що вимагає великої обчислювальної потужності.
Зловмисник може скинути один блок в ланцюжку, але в міру збільшення дійсних блоків ланцюга
також накопичується навантаження, тому для скидання довгого ланцюга потрібна величезна обчислювальна потужність.
PoW належить до протоколів консенсусу ймовірнісно-кінцевих, оскільки він гарантує можливу послідовність.
\subsubsection{Алгоритм Proof of Stake}
У PoS вибір кожного раунду вузла, який створює новий блок, залежить від утримуваного кола, а не обчислювальної потужності.
Хоча вузлам все-таки потрібно вирішити задачу SHA256, представлену формулою \ref{eq:pos_sha}:
\begin{equation}
SHA512(timestamp, previous hash...) < target*coin
\label{eq:pos_sha}
\end{equation}
Від PoW відмінність полягає в тому, що вузлам не потрібно багато разів коригувати нуль,
натомість ключовим для вирішення цієї задачі є кількість ставок (монет).
Отже, PoS --- це енергозберігаючий консенсус-протокол, який використовує спосіб стимулювання внутрішньої валюти,
а не витрачає багато обчислювальної сили для досягнення консенсусу.
Схема алгоритму виконання PoS показана на рисунку \ref{img:flow-pos}.
\printImage[1][0.6]{flow-pos}{Cхема роботи PoS алгоритму}
Як і PoW, PoS також є протоколом консенсусу ймовірнісно-кінцевих.
PPcoin була першою криптовалют, яка застосувала PoS до блокчейн.
У PPcoin, крім розміру ставки, вік монети також вводиться для вирішення задачі PoS.
Наприклад, якщо ви тримаєте 10 монет протягом 20 днів, то ваш вік монет --- 200.
Після того, як вузол створить новий блок, його вік монет очиститься до 0.
Крім PPcoin, багато криптовалют використовують PoS, наприклад , Nxt, Odour.
\subsubsection{Алгоритм Delegated Proof of Stake}
Принцип DPoS --- дозволити вузлам, які мають пакет голосів,
обирати верифікаторів блоків (тобто, творців блоків).
Цей спосіб голосування змушує зацікавлені сторони надавати право створювати блоки для делегатів, яких вони підтримують,
а не створювати блоки, таким чином зменшуючи їх обчислювальне енергоспоживання до нуля.
Алгоритм роботи DPoS на рисунку \ref{img:flow-dpos}
\printImage[1][0.6]{flow-dpos}{Cхема роботи DPoS алгоритму}
DPoS --- це як парламентська система, якщо делегати не зможуть генерувати блоки в свою чергу,
вони будуть звільнені, а зацікавлені сторони виберуть нові вузли для їх заміни. DPoS максимально використовує
голоси акціонерів для досягнення консенсусу справедливим та демократичним способом.
Порівняно з PoW та PoS, DPoS --- консенсус-протокол з низькою вартістю та високою ефективністю
Існують також деякі криптовалюти, які приймають DPoS, такі як BitShares, EOS.
Нова версія EOS перетворила DPoS на BFT-DPoS (Byzantine Fault Tolerance-DPoS).
\subsubsection{Алгоритм Practical Byzantine Fault Tolerance}
PBFT --- це візантійський протокол допуску відмов з низькою складністю алгоритму та високою практичністю в розподілених системах.
PBFT містить п’ять етапів: запит, попередня підготовка, підготовка, виконання та відповідь. На рисунку \ref{img:flow-pbft}
зображено, як працює PBFT.
\printImage[1][0.6]{flow-pbft}{Cхема роботи PBFT алгоритму}
Первинний вузол пересилає повідомлення, надіслане клієнтом, на три інші вузли.
У випадку збою 3 вузла одне повідомлення проходить через п'ять фаз, щоб досягти консенсусу серед цих вузлів.
Нарешті, ці вузли відповідають клієнту для завершення консенсусу.
PBFT гарантує, що вузли підтримують загальний стан і вживають послідовних дій у кожному раунді консенсусу.
PBFT досягає мети міцної послідовності, таким чином, це протокол консенсусу абсолютної остаточності.
Новий протокол під назвою Stellar --- це поліпшення PBFT.
Stellar приймає протокол FBA (Федеративна візантійська угода), в якому вузли можуть обрати федерацію,
якій вони довіряють, щоб провести процес консенсусу.
\subsubsection{Порівняння алгоритмів консенсусу}
Для того, щоб обрати, який з алгоритмів буде найкраще підходити для
даної платформи, необхідно спочатку порівняти їх за певними критеріями (таблиця \ref{tbl:cons-comp}).
\printTableWithCaption{
\makeTable{
Властивості & PoW & PoS & DPoS & PBFT
}{
Тип & ймовірнісно-кінцевий & ймовірнісно-кінцевий & ймовірнісно-кінцевий & абсолютно-кінцевий \\
\hline
Відмовостійкість & 50\% & 50\% & 50\% & 33\% \\
\hline
Споживання енергії & Велике & Низьке & Низьке & Відсутне \\
\hline
Масштабованість & Добре & Добре & Добре & Погано \\
\hline
Застосування & Публічне & Публічне & Публічне & Приватне \\
}{|c|p{4cm}|p{4cm}|p{4cm}|p{4cm}|}
}{
Порівняння протоколів консенсусу
}{cons-comp}
Як можна побачити, найоптимальнішого алгоритму для даної платформи не існує, проте PoS добре показує себе у відкритих системах,
в той час як BPFT може себе показати у приватних блокчейнах.
\subsection{Механізм обробки подій}
Цикл подій --- це програмана модель дизайну, яка чекає і пересилає події або повідомлення в програмі [9].
Цикл подій працює (рисунок \ref{img:eloop-example}), надсилаючи запит до якогось внутрішнього або зовнішнього "постачальника подій"
(який, як правило, блокує запит, поки подія не надійшла), а потім викликає відповідного обробника подій ("розсилає подію").
Event-Driven підхід, може відокремлювати потоки від з'єднань,
які використовують лише потоки для подій на конкретних зворотних викликах або обробниках.
\printImage[1][0.5]{eloop-example}{Cхема роботи Event Loop на чотирьох потоках}
Керована подіями архітектура складається з творців подій та споживачів подій.
Творець, який є джерелом події, знає лише, що подія сталася.
Споживачі --- це суб'єкти, які повинні знати, що відбулася подія.
Вони можуть бути залучені до опрацювання події або можуть просто вплинути на подію.
Даний підхід дозволить максимально оптимально використовувати ресурси, тим самим підвищуючи швидкість встановлення консенсусу в системі.
\subsection{Механізм зовнішнього доступу}
Для того, щоб створювати додатки для користувачів, необхідний механізм, який надаватиме змогу отримувати данні системи ззовні,
таким чином буде можливість підключати різноманітні клієнтські додатки із мінімальними зусиллями.
\subsubsection{Технологія Remote Procedure Call}
Віддалений виклик процедури (RPC) --- це коли комп'ютерна програма спричиняє виконання процедури (підпрограми) в
іншому адресному просторі (зазвичай на іншому комп’ютері в спільній мережі),
який кодується так, ніби це був звичайний (локальний) виклик процедури [10].
Тобто, програміст пише по суті той самий код, чи підпрограма є локальною для виконавчої програми, або віддаленою.
Це форма взаємодії клієнт-сервер (абонент --- клієнт, виконавець --- сервер), що зазвичай реалізується через систему передачі
повідомлень запит-відповідь (рисунок \ref{img:rpc-example}). У об'єктно-орієнтованій парадигмі програмування виклики RPC
представлені вилученим методом виклику (RMI).
\printImage[1][0.7]{rpc-example}{Cхема роботи виклику за допомогою RPC}
Модель RPC передбачає рівень прозорості місцеположення, а саме те,
що процедури виклику значною мірою однакові, незалежно від того,
локальні вони або віддалені, але зазвичай вони не є ідентичними,
тому локальні виклики можна відрізнити від віддалених.
Віддалені виклики зазвичай на порядок повільніші і менш надійні, ніж локальні, тому важливо розрізняти їх.
RPC --- це форма міжпроцесорного зв'язку (IPC), оскільки різні процеси
мають різні адресні простори: якщо на одній хост-машині вони мають чіткі віртуальні
адресні простори, хоча фізичний простір адрес однаковий; якщо вони знаходяться на різних хостах,
фізичний адресний простір відрізняється.
\subsubsection{RESTful сервіс}
REST --- архітектурний стиль програмного забезпечення, який визначає набір обмежень,
які будуть використані для створення веб-служб(рисунок \ref{img:restful-example}) [11].
\printImage[1][0.7]{restful-example}{Принцип роботи Restful API}
"Веб-ресурси" вперше були визначені у Всесвітній павутині як документи або файли, визначені за їх URL-адресами.
Однак сьогодні вони мають набагато більш загальне та абстрактне визначення, яке охоплює будь-яку річ чи сутність,
які можна будь-яким чином ідентифікувати, назвати, звертатись чи обробляти в Інтернеті.
У веб-службі RESTful запити, що надсилаються до URI ресурсу, викликають відповідь з корисним навантаженням,
відформатованим у HTML, XML, JSON чи іншому форматі. Відповідь може підтвердити, що деякі зміни були внесені
до збереженого ресурсу, і відповідь може забезпечити гіпертекстові посилання на інші пов'язані ресурси або набори ресурсів.
Якщо використовується HTTP, як це найбільш часто, доступними операціями (методами HTTP) є GET, HEAD, POST, PUT,
PATCH, DELETE, CONNECT, OPTIONS та TRACE.
\startSection{РЕАЛІЗАЦІЯ ТА ТЕХНІЧНА ОПТИМІЗАЦІЯ}
% TODO description of impl
\subsection{Формат серіалізації Dragnit}
Dragnit --- це бінарний формат на основі схем для ефективної сереалізації дерев даних. Він натхненний
Google Protobuf [12], але простіший, проте має більш компактне кодування та кращу підтримку додаткових полів.
\subsubsection{Особливості алгоритму}
Основні особливості алгоритму:
\listDefault{
\item ефективна серіалізація загальних значень --- кодування змінної довжини використовується для числових значень,
де малі значення займають менше місця;
\item ефективна серіалізація складних об'єктів --- структурна функція підтримує вкладені об'єкти з нульовою серіалізацією
накладних витрат;
\item виявлення наявності необов'язкових полів --- це неможливо в protobuf, особливо для повторних полів;
\item лінійна серіалізація (читання та запис) --- це операції одноканального сканування,
тому вони ефективні в кеш-пам'яті та мають гарантовану часову складність;
\item зворотна сумісність --- нові версії схеми все ще можуть читати старі дані;
\item сумісність вперед --- старі версії схеми можуть читати нові дані,
якщо копія нової схеми в комплекті з даними (нова схема дозволяє декодеру пропускати через невідомі поля);
\item проста реалізація --- API дуже мінімальний.
}
Серіалізатор підтримує такі типи:
\listEnumerated{
\item нативні типи:
\listInnerEnumerated{
\item bool --- значення, яке зберігає істинне або хибне, буде використовувати 1 байт;
\item byte --- беззнакове 8-бітове ціле число, очевидно, використовується 1 байт;
\item int --- ціле 32-бітне ціле значення, що зберігається з використанням кодування;
змінної довжини, оптимізованого для зберігання чисел з невеликою величиною, буде використано не більше 5 байт;
\item uint --- ціле 32-бітне ціле значення, що зберігається з використанням кодування;
змінної довжини, оптимізованого для зберігання малих невід’ємних чисел,уде використано не більше 5 байт;
\item float --- 32-бітове число з плаваючою комою, зазвичай використовує 4 байти;
але для значення нуля використовує 1 байт;
\item string --- рядок з нульовим завершенням UTF-8, буде використаний принаймні 1 байт;
\item T [] --- будь-який тип може бути перетворений у масив, використовуючи суфікс [];
}
\item користувацькі типи:
\listInnerEnumerated{
\item enum --- uint з обмеженим набором значень,
які ідентифікуються за назвою,
нові поля можна додавати до будь-якого повідомлення, зберігаючи зворотну сумісність;
\item struct --- складене значення з фіксованим набором полів,
які завжди обов'язкові та записані в порядку,
нові поля не можуть бути додані до структури, коли ця структура використовується;
\item message --- складене значення з необов’язковими полями,
нові поля можна додавати до будь-якого повідомлення, зберігаючи зворотну сумісність.
}
}
На лістингу \ref{code:simple_schema_dragnit} зображена проста схема для Drargnit.
\begin{stdout}{Проста схема серіалізації}{simple_schema_dragnit}
enum Shape {
BIG = 0;
MEDIUM = 1;
SMALL = 2;
}
struct Color {
byte r;
byte g;
byte b;
}
message Example {
uint clientId = 1;
Shape shape = 2;
Color[] colors = 3;
}\end{stdout}
\subsubsection{Алгоритм роботи}
Уданому розділі наведені приклади кодування кожної структури.
Для початку, нехай буде обрано просте повідомлення (лістинг \ref{code:uint_schema_dragnit}), що складається із одного натурального числа у діапазоні (0-255):
\begin{stdout}{Схема простого повідомленя із натуральним числом у якості даних}{uint_schema_dragnit}
message ChangeBitOperation {
uint bitPosition = 1;
}\end{stdout}
Якщо встановити значення, наприклад, в 1, то
після серіалізації можна побачити наступну картирну (рисунок \ref{img:drag_algo_1}):
\printImage[0.8][0.3]{drag_algo_1}{Приклад роботи алгоритму серіалізації із натуральним числом}
Щоб зрозуміти, як серіалізація працює, спочатку потрібно зрозуміти метод "varint".
Varint- це метод серіалізації цілих чисел за допомогою одного або декількох байтів.
Менші числа займають меншу кількість байтів.
Кожен байт у varint, крім останнього байта, має найзначніший набір бітів (msb) --- це вказує на те,
що надходять ще байти.
Молодші 7 біт кожного байта використовуються для зберігання представленого ними комплексу
представлення числа в групах по 7 біт, найменш значущої групи спочатку.
Строкові рядки кодуються схожим методом, проте для кожного символу використовуеться ключ, ключем є номер поля у повідомлені.
Наприклад, нехай буде серіалізовано рядок "test" за схемою, наведеною у лістингу \ref{code:string_schema_dragnit}.
\begin{stdout}{Схема простого повідомленя із строкою у якості даних}{string_schema_dragnit}
message StringOperation {
string str = 1;
}\end{stdout}
На виході буде отримано значення, яке зображено на рисунку \ref{img:drag_algo_2}:
\printImage[0.8][0.3]{drag_algo_2}{Приклад роботи алгоритму серіалізації на строкових даних}
Як можна побачити, перше значення, 01, і є ключ, тобто номер рядка у повідомлені, інші байти --- саме слово.
Для більше комплексних данних, завдяки оптимізаціям, можна досягнути значних оптимізацій використання ресурсів.
Нехай, буде задана більш складна схема, приведена на лістингу \ref{code:complex_schema_dragnit}.
\begin{stdout}{Схема для сереалізації із користувацькими типами}{complex_schema_dragnit}
enum Shape {
BIG = 0;
MEDIUM = 1;
SMALL = 2;
}
struct Color {
byte r;
byte g;
byte b;
}
message Example {
uint clientId = 1;
Shape shape = 2;
Color[] colors = 3;
}\end{stdout}
В даній схемі можна побачити як і користувацькі типи, як struct та enum, так і вкладені данні у повідомлення.
Задана схема будет сереалізована даними, представленими на лістингу \ref{code:complex_schema_init_dragnit}.
\begin{stdout}{Дані для сереалізації}{complex_schema_init_dragnit}
{
"clientId": 21,
"shape": "MEDIUM",
"colors": [
{
"r": 122,
"g": 127,
"b": 0
}
]
}\end{stdout}
Після серіалізації буде отримано такий потік байтів (рисунок \ref{img:drag_algo_3}):
\printImage[0.8][0.4]{drag_algo_3}{Приклад роботи алгоритму серіалізації на складних структурах даних}
Як можна побачити, алгоритм непогано оптимізує вкладені структури данних,
зберігши по 1 байту на кожне одиничне значення, тобо 5 байтів усього.
Алгоритм також підтримує опціональні поля та обробку помилок у схемі. Це дозволяє двум конкуруючим схемам
впізнавати один одну навіть при незначних відмінностях у схемах.
Для прикладу, у даних для ініціалізації, розглянутих вище (лістинг \ref{code:complex_schema_init_dragnit}), зроблена помилка,
замість поля "clientId" представлено "clientID", результат сереалізації можна побачити на рисунку \ref{img:drag_algo_4}.
\printImage[0.8][0.4]{drag_algo_4}{Приклад роботи алгоритму серіалізації при помилках у даних}
Як можна побачити, алгоритм просто проігнорував невалідне поле і просто закодував правильні дані, тим самим дозволяючи
вирішувати конфлікти між схемами та невалідними пакетами даних.
\subsubsection{Реалізація алгоритму}
Даний алгоритм реалізований мовою Rust, так як вона ідеально підходить для реалізації низькорівневих речей, без великих затрат часу.
Rust --- це системна мультипарадигмена мова програмування, орієнтована на безпеку, особливо безпечну багатопоточність.
Rust синтаксично схожа на C++, але розроблений для забезпечення кращої безпеки пам’яті при збереженні високої продуктивності.
Дана мова була обрана із декількох переваг [13]. За задумом, код Rust не може мати загублені покажчики,
переповнення буфера чи цілу низку інших помилок пам'яті.
Будь-який код, який би спричинив це буквально, неможливо скомпілювати.
Мова цього не дозволяє.
Найголовніше, що Rust досягає всіх цих гарантій безпеки пам’яті під час компіляції.
Немає режиму виконання, що робить кінцевий код таким же швидким, як C/C++, проте він набагато безпечніший.
Rust дозволяє писати високопродуктивний код, проте не задумуватися про технічні моменти реалізації потоків чи
управління пам’яті. Це дозволяє проектувати програмне забезпечення на іншому рівні абстракції.
Також, ще однією причиною для вибору, була дуже гнучка модульна система, яку підтримує інфраструктура Rust.
Для більшої зручності, алгоритм був реалізований в якості модуля бібліотеки, таким чинов він не був кросзалежним від інших модулів,
його можна легко збирати та тестувати.
Якщо представити код бібліотеки простою структурною діагармаю, то він буде виглядати, як зображено на рисунку \ref{img:dragnit_schema}.
\printImage[1][1.3]{dragnit_schema}{Структурна схема модуля серіалізації}
Алгоритм серіалізації простого натурального числа представлений в лістингу \ref{code:serialization-uint}.
\begin{stdout}{Частина коду функції сереліалізації натурального 32 бітного числа}{serialization-uint}
loop {
let byte = value as u8;
byte &= 127;
value >>= 7;
if value == 0 {
write_chunck(byte);
break;
}
write_chunck(byte|128);
}\end{stdout}
У представлені алгоритму, кожне число розбивається на частини по 7 бітів, а старший, восьмий,
біт представляє 1 або 0, в залежності від того, чи є частина останньою.
Реалізація десеріалізації зображена на лістингу \ref{code:deserialization-uint}).
\begin{stdout}{Частина коду функції десереліалізації натурального 32 бітного числа}{deserialization-uint}
let mut shift: u8 = 0;
loop {
let byte = read_byte()?;
result |= (byte & 127) << shift;
shift += 7;
if ((byte & 128) == 0 || shift >= 35)
break;
}\end{stdout}
Особливу увагу слід приділити методу skip, а точніше обробці вкладених структур, із структураа Schema (лістинг \ref{code:skip-func}).
\begin{stdout}{Частина коду функції skip, відповідальна за обробку структур}{skip-func}
...
Message => {
loop {
let value = stream.read_var_uint()?;
if let Some(index) = defined.value_to_index.get(&value)
skip_field(stream, &defined.fields[*index])?;
else
return Err(());
}
}
...\end{stdout}
Завдяки можливості ігнорувати невалідні дані, алгоритм дає змогу обробляти застарілі схеми і навіть пропускати схеми із надлишковою інформацією.
Такий функціонал є важливим для розподілених систем, оскільки, незважаючи на протокол консенсусу,
існують субмережі, які мають різні ланцюги розподіленого сховища, проте їм необхідна можливість спілкуватися між собою.
Наприклад, існує дві компанії, вони використовують один і той же протокол передачі даних, проте мають різні версії протоколу.
Завдяки серіалізації опційних полів, у них є така можливість, адже алгоритм може без конфліктів викинути поля, які були опціональними
у більш новій версії протоколу передачі даних.
\subsubsection{Порівняння з Protobuf}
Перевірка буде виконана на схемі, представленій у лістингу \ref{code:dragnit-compare-schema}
\begin{stdout}{Схема для тестування швидкодії}{dragnit-compare-schema}
message Person {
string name = 1;
int id = 2;
string email = 3;
enum PhoneType {
MOBILE = 0;
HOME = 1;
WORK = 2;
}
message PhoneNumber {
string number = 1;
PhoneType type = 2;
}
}\end{stdout}
Тести виконуватимуться для 10000000 операціх серіалізаціЇ та десеріалізації.
Для серілазації отриманий результат зображений на лістингу \ref{code:dragnit-proto-serialization}.
\begin{stdout}{Результат замірів роботи серіалізації алгоритмів}{dragnit-proto-serialization}
BenchmarkSerializeToDragnit 10000000 230 ns/op 143 B/op 1 allocs/op
BenchmarkSerializeToProtobuf 10000000 197 ns/op 80 B/op 1 allocs/op\end{stdout}
Для десеріалізації отриманий результат на лістингу \ref{code:dragnit-proto-deserialization}.
\begin{stdout}{Результат замірів роботи десеріалізації алгоритмів}{dragnit-proto-deserialization}
BenchmarkSerializeToDragnit 10000000 711 ns/op 421 B/op 15 allocs/op
BenchmarkSerializeToProtobuf 10000000 461 ns/op 272 B/op 9 allocs/op\end{stdout}
Графік, отриманий в результаті тестів, зображений на рисунку \ref{img:drag-vs-proto}:
\printImage[1][0.5]{drag-vs-proto}{Швидкість операцій (зліва --- Protobuf, зправа --- dragnit)}
Як можна побачити, в десеріалізації dragnit сильно програє protobuf, проте це пов'язано із перевіркою на опціональні поля,
а ця особливість є критично необхідною для платформи.
\subsection{Програмна віртуальна машина}
Програмна віртуальна машина необхідна для створення захищеної середи виконання криптографічних операцій, та
створення агностичної платформи, яка зможе запускатися на будь-якій ОС.
Так-як потужність сучасного смартфона може позмагатися із простим ПК, то важливо, щоб платформа могла запускатись усюди,
при цьому використовуючи мінімум ресурсів.
У розділі розглянуто реалізація простої стекової машини, парсера програмної мови, оптимізація її швидкодії та використання ресурсів,
та реалізація базових криптографічних алгоритмів на створеній для віртуальної машини мові.
\subsubsection{Архітектура}
Обираючи із стекової та реєстрової машини, було обрану стекову, через її простоту, проте і значну швидкодію, ніж реєстрова.
Однією з важливих причин розроблення мов на основі стека є те,
що мінімалізм їх семантики дозволяє просту інтерпретацію та реалізацію компілятора, а також оптимізацію.
Отже, однією з практичних переваг такої парадигми є те,
що вона дозволяє розробникам легко будувати над ними складніші речі та парадигми.
Серед переваг також можна назвати:
\listDefault{
\item час процесора --- вартість часу на розподіл пам'яті в стеку практично безкоштовна,
неважливо, виділяється одна чи тисячуа цілих чисел, все, що потрібно, --- це операція зменшення покажчика стека;
\item витік пам'яті --- під час використання стеку немає витоків пам'яті, це відбувається природно, без додаткових накладних витрат
на вирішення цього питання, пам'ять, яку використовує функція,
повністю звільняється при поверненні з кожної функції навіть при
обробці винятків або використанні longjmp (відсутність посилань на підрахунок, збирання сміття, тощо);
\item фрагментація --- стеки також уникають фрагментації пам'яті природним шляхом,
можна домогтися нульової фрагментації без будь-якого додаткового коду для вирішення цього питання,
наприклад, пулу об'єктів або розподілу пам'яті на платформі.
\item локальність --- дані в стеку надають перевагу локальному збереженню, використовуючи кеш-пам'ять та уникаючи змін сторінок.
}
Віртуальна машина також реалізована мовою Rust.
Архітектура машини досить проста [14]. За значення стеку відповідає StackValue, зображений на рисунку \ref{img:vm_algo_1}.
\printImage[0.6][0.3]{vm_algo_1}{Структура абстракції StackValue}