Condense and Compress: nasz niestandardowy format plików binarnych

Pomyśl o ulepszeniach wydajności i funkcjach renderowania, które wprowadziliśmy do ROBLOX w ciągu ostatniego roku. Wśród nich są lekkie jak piórko elementy, szybkie klastry, wydajne wykrywanie kolizji i dynamiczne oświetlenie. Te ulepszenia przełamały ograniczenia – dotyczące liczby elementów, symulacji fizyki i elastyczności estetycznej – z którymi kiedyś borykali się twórcy, otwierając drzwi do świata nowych możliwości. Ujawniły też nowe ograniczenia, ponieważ twórcy przesunęli granice dalej niż kiedykolwiek. W tym artykule wyjaśnimy, w jaki sposób udało nam się zmniejszyć rozmiar plików miejsc ROBLOX około 100-krotnie oraz skrócić czas ładowania/zapisywania 5–10-krotnie.

Pomyśl o elementach typu „featherweight”. Ta funkcja, która obecnie dotyczy wszystkich elementów ROBLOX (a nie tylko wybranych kształtów i materiałów), pozwala tworzyć miejsca ROBLOX z dziesiątkami tysięcy klocków i uruchamiać je zarówno na komputerach stacjonarnych, jak i urządzeniach mobilnych. Jednak miejsce z dziesiątkami tysięcy elementów może skutkować bardzo dużym plikiem. Nasze miejsce testowe, do którego będziemy się odnosić w całym tym artykule, ma 50 000 elementów i waży aż 230 megabajtów. To wystarczająco dużo, by wpłynąć na twórców na wiele sposobów: renderowanie, zapisywanie/ładowanie, publikowanie, ładowanie miejsca z serwera i nie tylko.

Uznaliśmy, że nadszedł odpowiedni moment, aby zająć się rozmiarem plików kreacji ROBLOX – zarówno w celu poprawy komfortu użytkowania, jak i wsparcia rozwoju jeszcze nieogłoszonego projektu. W tym celu wkrótce rozpoczniemy testowanie nowego formatu plików, który zapisuje dane ROBLOX w formacie binarnym zamiast XML. Zmiana będzie przebiegać płynnie, ale z czasem skróci czas oczekiwania twórców. Będziemy stopniowo wdrażać nową metodę zapisywania danych ROBLOX, zaczynając od plików tymczasowych tworzonych dla sesji „Play Solo” i „Start Server” w ROBLOX Studio, a ostatecznie wprowadzimy ją do pamięci Personal Build Server, przesyłania lokacji i zapisów lokalnych.

Pożegnaj stare

Rozmiar pliku ma znaczenie. Wpływa on na czas potrzebny do zapisania i załadowania pliku lokalnie oraz opublikowania i pobrania treści z ROBLOX.com. Ponadto istnieją ograniczenia dotyczące rozmiaru plików, które można publikować na ROBLOX.com (twórcy znaleźli obejścia, pisząc skrypty, które generują dodatkowe elementy po załadowaniu gry).

ROBLOX od dawna zapisuje dane miejsc w formacie XML. Jest to intuicyjny format oparty na hierarchii, w którym każdy obiekt ma właściwości, a każda właściwość ma wartość, a wszystko to układa się w ładne drzewo danych. Nie skaluje się ono jednak w nieskończoność, głównie dlatego, że konwersja danych czytelnych dla pamięci na ciąg znaków (np. podczas zapisywania) zajmuje czas i występuje znaczna redundancja. Dwie części, które są niemal identyczne, są przechowywane w całości jako oddzielne fragmenty XML. Nasze testowe miejsce z 50 000 części i rozmiarem pliku 230 megabajtów, zapisane jako XML, zajmuje 23 sekundy do zapisania i 37 sekund do załadowania. Chociaż istnieją zalety, takie jak czytelność dla człowieka (przydatna do celów debugowania) oraz kompatybilność wsteczna i przyszła (przydatna w środowisku, w którym ROBLOX Studio i ROBLOX Player nie zawsze mają zgodne wersje), format ten przestaje nam wystarczać.

Rozważaliśmy ulepszenie naszego parsera XML, ale wiedzieliśmy, że korzyści będą ograniczone. Zdecydowaliśmy się pójść na całość, gruntownie zmieniając format, w którym zapisujemy dane ROBLOX.

Wprowadzamy nowości

Zapisując dzieło ROBLOX w formacie binarnym, eliminujemy zbędne odniesienia do właściwości. Już samo to powoduje 10-krotne zmniejszenie rozmiaru pliku.

Jedną z alternatyw dla formatu XML, zawierającego dużo tekstu, jest format binarny. Istnieją między nimi wyraźne różnice.

• Format binarny nie jest czytelny dla człowieka. Jednak dane binarne bardzo przypominają ich reprezentację w pamięci, co oznacza, że łatwo jest nam pobrać obiekt znajdujący się w pamięci i zapisać go jako strumień bajtów (i odwrotnie).
• Zamiast hierarchii obiektów, z których każdy zawiera około 30 właściwości i ich wartości, dane ROBLOX są przechowywane w grupach (tj. dla każdej właściwości zapisujemy wartość dla wszystkich obiektów w danym miejscu), aby ograniczyć powtórzenia. Ułatwia to również pominięcie ładowania danych, które mogą stać się przestarzałe, co mogłoby nastąpić, gdybyśmy w przyszłości usunęli jakąś właściwość części. Nadal zachowujemy korzyści wynikające z kompatybilności wstecznej i przyszłej.

Zapisując dzieło ROBLOX w formacie binarnym, eliminujemy zbędne odniesienia do właściwości (których użytkownicy nie mogą dodawać ani usuwać i które często są statyczne) oraz zmniejszamy rozmiar plików mniej więcej 10-krotnie. Nie jest to jednak tak proste, jak naciśnięcie jakiegoś magicznego przełącznika; stworzyliśmy niestandardową metodę zapisywania wartości właściwości (liczb całkowitych) w sposób, który jest zarówno szybki, jak i umożliwia kompresję.

Konwersja wartości właściwości w celu przyspieszenia i kompresji

Zaczyna się od rozbicia liczb całkowitych wartości właściwości na cztery bajty. Maksymalna wartość każdego bajtu to 2^8-1 (czyli 255). Liczba siedem wygląda tak:

A wartość 258 wygląda tak:

Zamiast przechowywać każdą wartość w wierszu, nasz kod przechowuje wartości w kolumnie. Ponieważ większość wartości właściwości w ROBLOX jest niewielka, w rezultacie mamy wiele zera ułożonych jeden po drugim. Tego rodzaju nadmiarowość świetnie nadaje się do kompresji.

Załóżmy na przykład, że chcemy zapisać w pliku następujące liczby całkowite: 1, 5, 4, 258. Naiwne podejście polegałoby na zapisaniu ich bajtów kolejno, tak jak poniżej:

Jednak po ponownym posortowaniu według kolumn zostaną zapisane jako:

Dzięki powtarzającym się zerom kompresja przebiega znacznie wydajniej.

Liczby ujemne komplikują tę technikę. Nie są one zbyt powszechne, ale mogą pojawić się w danych ROBLOX, na przykład gdy liczba ujemna jest używana do przesunięcia elementu GUI. Po zastosowaniu operacji matematycznej znanej jako uzupełnienie do dwójki w celu odwrócenia znaku (2^32 + (-7)), liczba ujemna siedem wygląda następująco:

Wszystkie te liczby niezerowe przeszkadzają nam w osiągnięciu celu: uzyskaniu strumienia bajtów zer, który można mocno skompresować. Wymyśliliśmy drugą sztuczkę, żeby zamienić ujemne liczby całkowite na małe liczby dodatnie. Za każdym razem, gdy wartość jest większa lub równa 0, stosujemy do niej ten wzór:

2 x n

Za każdym razem, gdy liczba jest mniejsza od 0, traktujemy ją jako:

2 x |n| - 1

Oznacza to, że wartość 7 jest reprezentowana jako 14 (2 x 7). Wartość -7 jest reprezentowana jako 13 (2 x |7| - 1). Kiedy ułożymy te liczby w stos, zera się kumulują i otrzymujemy plik, który można bardzo dobrze skompresować.

Wszystkie te konwersje i obliczenia odbywają się przy bardzo niewielkim nakładzie. Z tego powodu znacznie wydajniejsze jest wykonywanie tej pracy po stronie klienta niż poleganie wyłącznie na algorytmie kompresji.

Po rozbiciu wartości właściwości na bajty automatycznie poddajemy dane kompresji LZ4, która jest bezstratnym algorytmem szybko kompresującym dane binarne przy bardzo niewielkim nakładzie obliczeniowym. To jeszcze bardziej zmniejsza rozmiar pliku. Wcześniej na tym etapie procesu przechowywania plików nie stosowano kompresji – odbywała się ona wyłącznie poprzez automatyczną kompresję Gzip, gdy plik był przesyłany przez HTTP do serwisu ROBLOX.com.

Testowanie nowego formatu

Dzięki formatowi pliku binarnego i kompresji LZ4 miejsce ROBLOX o wielkości 230 megabajtów zostaje zredukowane do mniej niż 1 megabajta. Po kompresji Gzip plik ma około 100 kilobajtów. Oto wyniki kilku testów, które przeprowadziliśmy wewnętrznie:

Test 1
Zbudowaliśmy testowe miejsce składające się z 50 000 części, 150 000 połączeń ManualWeld i 8 milionów wokseli.

Test 2
Przetestowaliśmy poziom „Welcome to the Neighborhood of ROBLOXia”, rzeczywisty poziom ROBLOX zbudowany z 40 000 elementów. Poziom ten nie zawiera wielu połączeń, co wyjaśnia różnicę w wynikach w porównaniu z miejscem testowym. Wielu nieustraszonych konstruktorów usunęło połączenia ze swoich poziomów za pomocą skryptów, aby zmniejszyć rozmiar pliku, ale kosztem symulacji fizycznej. To powinno im ułatwić życie.

Uwaga: czasy ładowania/zapisywania pochodzą z serwera; czas zapisywania w Studio jest taki sam, czas ładowania w Studio jest nieco dłuższy, ponieważ wykonuje ono dodatkową pracę, aby skonfigurować system obsługujący cofanie/ponawianie.

W obu testach odnotowano poprawę rzędu 100-krotnego zmniejszenia rozmiaru pliku oraz 5-10-krotnego skrócenia czasu ładowania/zapisywania. Jak wspomniano na początku tego artykułu, będziemy stopniowo wdrażać format plików binarnych, zaczynając od plików tymczasowych tworzonych podczas uruchamiania sesji gry za pośrednictwem ROBLOX Studio przy użyciu opcji „Play Solo” lub „Start Server”. Dołożyliśmy wszelkich starań, aby upewnić się, że nie spowoduje to uszkodzenia danych, ale będziemy prosić o informacje zwrotne, jeśli zauważysz jakiekolwiek nietypowe zachowanie (np. elementy nie wyświetlają się tak, jak powinny lub, co mniej prawdopodobne, nie możesz otworzyć pliku).

Ostatecznie zaczniemy przechowywać dane w formacie binarnym dla Personal Build Server i lokalnych zapisów. Wtedy powinniście zacząć dostrzegać większe korzyści. Mamy nadzieję, że po prostu płynnie przejdziecie do płynniejszego procesu tworzenia, zapisywania i publikowania oraz będziecie cieszyć się subtelnym, ale znaczącym wzrostem jakości doświadczenia ROBLOX.