Rýchle stránkovanie v relačných databázach

16.04.2023 | 18:35 | Mirecove dristy | Miroslav Bendík

Tento článok rozoberá rôzne spôsoby stránkovania v databáze, ich nevýhody a dôvody, prečo sú pomalé. Nakoniec predstavím aktuálne riešenie, ktoré používam pre stránkovanie vo veľkých tabuľkách.

Ako pokusnú databázu budem používať fiktívnu databázu kníh. Tabuľka book obsahuje ID a názov knihy. V tabuľke book_rating sú hodnotenia kníh (hodnotenie je hodnota od 1 do 5). Tabuľka book_order obsahuje fiktívne nákupy kníh (total_price pretože jeden nákup môže zahŕňať viac kusov).

Databázové modely
Obrázok 1: Databázové modely

SQL pre vytvorenie databázy vyzerá nasledovne:

CREATE TABLE book (
    id bigint NOT NULL,
    name character varying(100) NOT NULL,
    year integer NOT NULL
);

ALTER TABLE book ALTER COLUMN id ADD GENERATED BY DEFAULT AS IDENTITY (
    SEQUENCE NAME book_id_seq
    START WITH 1
    INCREMENT BY 1
    NO MINVALUE
    NO MAXVALUE
    CACHE 1
);

CREATE TABLE book_order (
    id bigint NOT NULL,
    total_price numeric(10,2) NOT NULL,
    book_id bigint NOT NULL
);

ALTER TABLE book_order ALTER COLUMN id ADD GENERATED BY DEFAULT AS IDENTITY (
    SEQUENCE NAME book_order_id_seq
    START WITH 1
    INCREMENT BY 1
    NO MINVALUE
    NO MAXVALUE
    CACHE 1
);

CREATE TABLE book_rating (
    id bigint NOT NULL,
    rating integer NOT NULL,
    book_id bigint NOT NULL
);

ALTER TABLE book_rating ALTER COLUMN id ADD GENERATED BY DEFAULT AS IDENTITY (
    SEQUENCE NAME book_rating_id_seq
    START WITH 1
    INCREMENT BY 1
    NO MINVALUE
    NO MAXVALUE
    CACHE 1
);

ALTER TABLE ONLY book_order
    ADD CONSTRAINT book_order_pkey PRIMARY KEY (id);

ALTER TABLE ONLY book
    ADD CONSTRAINT book_pkey PRIMARY KEY (id);

ALTER TABLE ONLY book_rating
    ADD CONSTRAINT book_rating_pkey PRIMARY KEY (id);

CREATE INDEX book_order_book_id_idx ON book_order USING btree (book_id);

CREATE INDEX book_rating_book_id_idx ON book_rating USING btree (book_id);

CREATE INDEX book_year_56cba46b ON book USING btree (year);

ALTER TABLE ONLY book_order
    ADD CONSTRAINT book_order_book_id_idx_fk_book_id FOREIGN KEY (book_id) REFERENCES book(id) DEFERRABLE INITIALLY DEFERRED;

ALTER TABLE ONLY book_rating
    ADD CONSTRAINT book_rating_book_id_idx_fk_book_id FOREIGN KEY (book_id) REFERENCES book(id) DEFERRABLE INITIALLY DEFERRED;

Skript pre generovanie dát je s súbore load_data.sql.

Výber hodnotení kníh

Nasledujúci dotaz vyberie 10 hodnotení kníh podľa ID:

SELECT book_id, rating FROM book_rating ORDER BY id LIMIT 10;
+---------+--------+
| book_id | rating |
+---------+--------+
|   91406 |      4 |
|    7794 |      1 |
|   11422 |      2 |
|   54729 |      4 |
|   24238 |      1 |
|   12438 |      2 |
|   79359 |      5 |
|   58785 |      4 |
|    3287 |      2 |
|   50076 |      5 |
+---------+--------+
(10 rows)

Time: 0,371 ms

Zatiaľ všetko vyzerá v poriadku. Pre istotu sa pozrime na query plán:

EXPLAIN (COSTS FALSE, ANALYZE TRUE, TIMING FALSE) SELECT book_id, rating FROM book_rating ORDER BY id LIMIT 10;
+---------------------------------------------------------------------------------+
|                                   QUERY PLAN                                    |
+---------------------------------------------------------------------------------+
| Limit (actual rows=10 loops=1)                                                  |
|   ->  Index Scan using book_rating_pkey on book_rating (actual rows=10 loops=1) |
| Planning Time: 0.133 ms                                                         |
| Execution Time: 0.081 ms                                                        |
+---------------------------------------------------------------------------------+

Dotaz vykonáva rýchly index sken obmedzený na 10 riadkov. Samotný čas vykonávanie 0.081 ms je veľmi dobrá hodnota.

Count je pomalý

Typické stránkovanie potrebuje najskôr skontrolovať počet riadkov v tabuľke. Po pridaní štandardného stránkovania v djangu sa zrazu webová aplikácia spomalí. Zároveň medzi vykonanými dotazmi pribudol nový dotaz:

SELECT COUNT(*) FROM book_rating;
+---------+
|  count  |
+---------+
| 1000000 |
+---------+
(1 row)

Time: 34,262 ms

Žeby boli staré štatistiky? Tak skúsme vygenerovať nové a potom zopakujeme rovnaký dotaz:

ANALYZE
Time: 183,467 ms

SELECT COUNT(*) FROM book_rating;
+---------+
|  count  |
+---------+
| 1000000 |
+---------+
(1 row)

Time: 35,655 ms

Zdá sa, že vygenerovanie štatistík nemá žiaden vplyv na počítanie riadkov. Teraz sa pozrime na výstup explain:

EXPLAIN (COSTS FALSE, ANALYZE TRUE, TIMING FALSE) SELECT COUNT(*) FROM book_rating;
+-------------------------------------------------------------+
|                         QUERY PLAN                          |
+-------------------------------------------------------------+
| Aggregate (actual rows=1 loops=1)                           |
|   ->  Seq Scan on book_rating (actual rows=1000000 loops=1) |
| Planning Time: 0.100 ms                                     |
| Execution Time: 44.656 ms                                   |
+-------------------------------------------------------------+

Pre spočítanie riadkov v tabuľke musí databázový systém preskenovať (prečítať) kompletne celú tabuľku. Väčšina čitateľov, ktorá do hĺbky neštudovala databázové systémy si teraz asi hovorí, prečo databázový systém nepoužije index? Však uložiť počet riadkov ako metadáta tabuľky nemôže byť predsa nič ťažké.

Lenže ono to nie je ani ťažké, ono to je prakticky nemožné. Pre vysvetlenie je potrebné hlbšie poznať fungovanie databázového systému.

We need to go deeper

Ako funguje databázový systém

Programátori si často predstavujú databázový systém ako centralizovaný sklad dát, ktorý má jediný jednoznačne definovaný stav. Taký zjednodušený pohľad platí na niektoré No-SQL databázové systémy.

Pre plnohodnotné databázové systémy ACID (atomicity, consistency, isolation, durability) to však neplatí. V takom databázovom systéme môže prebiehať jedna transakcia, ktorá číta tabuľku zatiaľ čo v inej transakcii sa nahrali nové dáta (pričom ešte nie je commitnutá), v ďalšej transakcii sa niektoré riadky zmazali a v ďalšej sa niektoré riadky zmenili. Vďaka vlastnosti zvanej izolácia musí prvá transakcia vidieť celú databázu v stave, v ktorom bola na začiatku transakcie bez ohľadu na to, čo sa deje v ďalších transakciách.

Databázový systém poskytuje teda každej transakcii vlastný pohľad na dáta v určitom čase, pričom jednotlivé transakcie nesmú byť ovplyvnené inými transakciami. Aby bolo možno niečo také, musí databázový systém ukladať rôzne verzie toho istého riadku a ponechávať zmazané riadky kým sú prístupné z niektorej transakcie.

PostgreSQL implementuje izoláciu pomocou dodatočných metadát pri riadkoch tabuľky. Riadky majú informáciu o minimálnom čísle transakcia, od kedy je viditeľná a o maximálnom čísle transakcie (ak bola vymazaná). Zmena dát v databáze sa tak implementuje pridávaním nových riadkov do WAL (Write-ahead logging) súborov. Staré verzie sa môžu odstrániť až vtedy, keď nie sú dostupné zo žiadnej transakcie.

Ako teda spočítať riadky v tabuľke? Jednoducho, stačí vedieť číslo aktuálnej transakcie a postupne skenovať celú tabuľku a aplikovať pravidlá viditeľnosti pre každý riadok. Presne to PostgreSQL robí.

Čas spočítania riadkov v tabuľke má kvôli podmienke izolácie lineárnu závislosť od počtu riadkov.

Situácia môže byť aj horšia

Príklad trochu skomplikujem tým, že v zozname budem chcieť zobraziť názov knihy a tržby za predaj. Dotaz v Django ORM vyzerá nasledovne:

LIST_QUERY = (BookRating.objects
	.values('id', 'rating', 'book__name')
	.order_by('id'))

Výsledný dotaz vyzerá nasledovne:

SELECT
	"book_rating"."id",
	"book_rating"."rating",
	"book"."name" AS "name",
	SUM("book_order"."total_price") AS "total_revenue"
FROM "book_rating"
INNER JOIN "book"
	ON ("book_rating"."book_id" = "book"."id")
LEFT OUTER JOIN "book_order"
	ON ("book"."id" = "book_order"."book_id")
GROUP BY "book_rating"."id", 3
ORDER BY "book_rating"."id" ASC
LIMIT 10;

Samotný výber riadkov je celkom uspokojivý.

+----+--------+-----------------+---------------+
| id | rating |      name       | total_revenue |
+----+--------+-----------------+---------------+
|  1 |      4 | mwJLdKU7i0Iqpe3 |        224.00 |
|  2 |      1 | 4AYnAqiSSAmfDt5 |        232.00 |
|  3 |      2 | EgYd9e4nYC1YX72 |        310.00 |
|  4 |      4 | kFCMna9vycWFvNT |        337.00 |
|  5 |      1 | 5Z9V3tTUCQPcWse |        243.00 |
|  6 |      2 | fuQu2GhvrwMIPfE |         88.00 |
|  7 |      5 | Wxn3gH6v2xeGD3p |        252.00 |
|  8 |      4 | VaeKeqymBj6fOEH |        180.00 |
|  9 |      2 | V3rkEJZ7ag8lAG0 |        310.00 |
| 10 |      5 | 0msAG9UwymXRs5Z |        239.00 |
+----+--------+-----------------+---------------+
(10 rows)

Time: 1,586 ms

Napriek tomu sa načítanie webu spomalilo na 3 s. Čo sa stalo?

Django rozpoznalo, že dotaz používa agregačné funkcie. Aby bolo možné spoľahlivo zistiť počet riadkov, musí sa dotaz spustiť ako subquery (ok, v tomto prípade by stačil jednoduchý count, ale logika za tým je pomerne zložitá, takže sa volí bezpečná aj keď pomalá metóda). Vygenerovaný dotaz vyzerá takto:

SELECT
	COUNT(*)
	FROM (
		SELECT
			"book_rating"."id" AS "col1",
			"book_rating"."rating" AS "col2"
		FROM "book_rating"
		INNER JOIN "book"
		ON ("book_rating"."book_id" = "book"."id")
		LEFT OUTER JOIN "book_order" ON ("book"."id" = "book_order"."book_id")
		GROUP BY 1, "book"."name"
	) subquery;

Výsledok je hrozný:

+---------+
|  count  |
+---------+
| 1000000 |
+---------+
(1 row)

Time: 2982,649 ms (00:02,983)

Pre doplnenie pridávam výstup z explainu:

+-------------------------------------------------------------------------------+
|                                  QUERY PLAN                                   |
+-------------------------------------------------------------------------------+
| Aggregate (actual rows=1 loops=1)                                             |
|   ->  HashAggregate (actual rows=1000000 loops=1)                             |
|         Group Key: book_rating.id, book.name                                  |
|         Batches: 257  Memory Usage: 9489kB  Disk Usage: 507472kB              |
|         ->  Hash Left Join (actual rows=10005165 loops=1)                     |
|               Hash Cond: (book.id = book_order.book_id)                       |
|               ->  Hash Join (actual rows=1000000 loops=1)                     |
|                     Hash Cond: (book_rating.book_id = book.id)                |
|                     ->  Seq Scan on book_rating (actual rows=1000000 loops=1) |
|                     ->  Hash (actual rows=100000 loops=1)                     |
|                           Buckets: 131072  Batches: 1  Memory Usage: 6493kB   |
|                           ->  Seq Scan on book (actual rows=100000 loops=1)   |
|               ->  Hash (actual rows=1000000 loops=1)                          |
|                     Buckets: 262144  Batches: 8  Memory Usage: 6981kB         |
|                     ->  Seq Scan on book_order (actual rows=1000000 loops=1)  |
| Planning Time: 0.494 ms                                                       |
| Execution Time: 3958.023 ms                                                   |
+-------------------------------------------------------------------------------+

Len pre zaujímavosť, databázový systém musel zapísať zhruba 500 MB dát na disk, aby vykonal korektne agregáciu.

Optimalizácia pomocou subquery

V django ORM je lepšie v takýchto prípadoch použiť subquery. Vďaka tomu bude ORM schopné odstrániť prebytočné parametre a vygeneruje jednoduchý count a zároveň nehrozí problém pri kombinácii viacerých agregačných funkcií keby som chcel napríklad zároveň vybrať priemerné hodnotenie a celkový zisk. Nasledujúci dotaz využíva subquery:

REVENUE_QUERY = Subquery(BookOrder.objects
	.filter(book_id=OuterRef('book_id'))
	.values('book_id')
	.annotate(total=Sum('total_price'))
	.values('total')[:1])
LIST_QUERY = (BookRating.objects
	.annotate(name=F('book__name'), total_revenue=REVENUE_QUERY)
	.values('id', 'rating', 'name', 'total_revenue')
	.order_by('id'))

Vygenerovaný dotaz vyzerá nasledovne:

SELECT
	"book_rating"."id",
	"book_rating"."rating",
	"book"."name" AS "name",
	(SELECT
		SUM(U0."total_price") AS "total"
		FROM "book_order" U0
		WHERE U0."book_id" = ("book_rating"."book_id")
		GROUP BY U0."book_id"
		LIMIT 1
	) AS "total_revenue"
FROM "book_rating"
INNER JOIN "book"
	ON ("book_rating"."book_id" = "book"."id")
ORDER BY "book_rating"."id" ASC
LIMIT 10;

Výsledný plán skutočne potreboval prejsť len 10 riadkov a pri každom prechode robil dodatočnú agregáciu s použitím jednoduchého index scanu:

+-------------------------------------------------------------------------------------------------------------------+
|                                                    QUERY PLAN                                                     |
+-------------------------------------------------------------------------------------------------------------------+
| Limit (actual rows=10 loops=1)                                                                                    |
|   ->  Nested Loop (actual rows=10 loops=1)                                                                        |
|         ->  Index Scan using book_rating_pkey on book_rating (actual rows=10 loops=1)                             |
|         ->  Memoize (actual rows=1 loops=10)                                                                      |
|               Cache Key: book_rating.book_id                                                                      |
|               Cache Mode: logical                                                                                 |
|               Hits: 0  Misses: 10  Evictions: 0  Overflows: 0  Memory Usage: 2kB                                  |
|               ->  Index Scan using book_pkey on book (actual rows=1 loops=10)                                     |
|                     Index Cond: (id = book_rating.book_id)                                                        |
|         SubPlan 1                                                                                                 |
|           ->  Limit (actual rows=1 loops=10)                                                                      |
|                 ->  GroupAggregate (actual rows=1 loops=10)                                                       |
|                       Group Key: u0.book_id                                                                       |
|                       ->  Index Scan using book_order_book_id_4178112d on book_order u0 (actual rows=10 loops=10) |
|                             Index Cond: (book_id = book_rating.book_id)                                           |
| Planning Time: 0.414 ms                                                                                           |
| Execution Time: 0.891 ms                                                                                          |
+-------------------------------------------------------------------------------------------------------------------+

Spočítanie riadkov vyzerá nasledovne:

SELECT
	COUNT(*) AS "__count"
FROM "book_rating"
INNER JOIN "book"
	ON ("book_rating"."book_id" = "book"."id");
+-------------------------------------------------------------------+
|                            QUERY PLAN                             |
+-------------------------------------------------------------------+
| Aggregate (actual rows=1 loops=1)                                 |
|   ->  Hash Join (actual rows=1000000 loops=1)                     |
|         Hash Cond: (book_rating.book_id = book.id)                |
|         ->  Seq Scan on book_rating (actual rows=1000000 loops=1) |
|         ->  Hash (actual rows=100000 loops=1)                     |
|               Buckets: 131072  Batches: 1  Memory Usage: 4931kB   |
|               ->  Seq Scan on book (actual rows=100000 loops=1)   |
| Planning Time: 0.267 ms                                           |
| Execution Time: 172.868 ms                                        |
+-------------------------------------------------------------------+

Štatistiky

Ako sa teda zbaviť pomalých dotazov na počet riadkov? Na internete sa často uvádza použitie štatistík. V tomto prípade je získanie približného počtu riadkov pomerne jednoduché.

SELECT reltuples FROM pg_class WHERE relname = 'book_rating';
+-----------+
| reltuples |
+-----------+
|     1e+06 |
+-----------+

Problém je, že počet je len približný a týmto spôsobom sa nedá zistiť ani približný počet riadkov pri použití where klauzuly.

Limit je pomalý

Takže zisťovanie počtu riadkov je pomalé a nedá sa s tým prakticky nič urobiť ak má byť zachovaná izolácia. Tak teda zobrazím stránkovač len s tlačidlom ďalej a na celý počet sa vykašlem.

Predstavme si však, že niekto chce skočiť na stránku číslo 5 000. Jednoducho v URL adrese prepíše parameter page. Pozrime sa teraz na dotaz:

SELECT
        "book_rating"."id",
        "book_rating"."rating",
        "book"."name" AS "name",
        SUM("book_order"."total_price") AS "total_revenue"
FROM "book_rating"
INNER JOIN "book"
        ON ("book_rating"."book_id" = "book"."id")
LEFT OUTER JOIN "book_order"
        ON ("book"."id" = "book_order"."book_id")
GROUP BY "book_rating"."id", 3
ORDER BY "book_rating"."id" ASC
LIMIT 10 OFFSET 50000;
+-------+--------+-----------------+---------------+
|  id   | rating |      name       | total_revenue |
+-------+--------+-----------------+---------------+
| 50001 |      3 | 7vpPz7iymGQwFHz |        209.00 |
| 50002 |      4 | MsjncKx1KD32dRG |        164.00 |
| 50003 |      2 | tf4TYvrVXEJr2Zu |        268.00 |
| 50004 |      3 | 8ZHr2AVXDJhqIVS |        337.00 |
| 50005 |      1 | ScY0nNLn12lc18L |        118.00 |
| 50006 |      1 | kdvRYxl2VrOB7Ft |        352.00 |
| 50007 |      5 | zkeowCN1d83I17h |        202.00 |
| 50008 |      1 | YN9Wb2xR9m3n0FZ |        243.00 |
| 50009 |      2 | X07SIjFQ7J4TCB2 |        146.00 |
| 50010 |      1 | qDn3zOzAbPGXDN9 |        169.00 |
+-------+--------+-----------------+---------------+
(10 rows)

Time: 996,773 ms

Ajajaj čo sa to stalo?

Tým, že je použitý offset musí databázový systém zase skenovať celú tabuľku, aby sa dostal na konkrétny záznam. Podobne ako v prípade počtu tu neexistuje žiadna skratka na zrýchlenie. Jednoducho offset je pomalý a bude pomalý ak má databázový systém dodržiavať izoláciu transakcií.

Keyset stránkovanie

Čo tak stránkovať pomocou primárneho kľúča?

SELECT
	"book_rating"."id",
	"book_rating"."rating",
	"book"."name" AS "name",
	(SELECT
		SUM(U0."total_price") AS "total"
		FROM "book_order" U0
		WHERE U0."book_id" = ("book_rating"."book_id")
		GROUP BY U0."book_id"
		LIMIT 1
	) AS "total_revenue"
FROM "book_rating"
INNER JOIN "book"
	ON ("book_rating"."book_id" = "book"."id")
WHERE "book_rating"."id" > 50000
ORDER BY "book_rating"."id" ASC
LIMIT 10;

Výsledok je rovnaký, ako v predchádzajúcom príklade, ale čas je diametrálne odlišný:

+-------+--------+-----------------+---------------+
|  id   | rating |      name       | total_revenue |
+-------+--------+-----------------+---------------+
| 50001 |      3 | 7vpPz7iymGQwFHz |        209.00 |
| 50002 |      4 | MsjncKx1KD32dRG |        164.00 |
| 50003 |      2 | tf4TYvrVXEJr2Zu |        268.00 |
| 50004 |      3 | 8ZHr2AVXDJhqIVS |        337.00 |
| 50005 |      1 | ScY0nNLn12lc18L |        118.00 |
| 50006 |      1 | kdvRYxl2VrOB7Ft |        352.00 |
| 50007 |      5 | zkeowCN1d83I17h |        202.00 |
| 50008 |      1 | YN9Wb2xR9m3n0FZ |        243.00 |
| 50009 |      2 | X07SIjFQ7J4TCB2 |        146.00 |
| 50010 |      1 | qDn3zOzAbPGXDN9 |        169.00 |
+-------+--------+-----------------+---------------+
(10 rows)

Time: 1,875 ms

V reálnom svete sa nestáva moc často s tým, aby tabuľky mali kľúče perfektne usporiadané bez akejkoľvek medzery. Na druhej strane samotná myšlienka začať s výpisom od určitého prvku nie je vôbec zlá.

Stránkovanie sa dá jednoducho implementovať tým, že namiesto čísla stránky sa zakóduje do URL adresy unikátny kľúč posledného prvku. Týmto spôsobom sa dá stránkovať tabuľka s miliardami riadkov rovnako rýchlo, ako tabuľka s 10 riadkami.

django-universal-paginator

Pôvodný stránkovač djanga nemal možnosť vynechať čísla stránok. Ak bolo napríklad 100 položiek v stránkovaní, vrátených bolo všetkých 100. Preto som si napísal vlastný interne používaný stránkovač - django-simple-paginator.

Medzitým django doplnilo podporu vynechávanie stránok a ja som svoj jednocuhý stránkovač vykastroval o túto funkciu. Zostali už len pomocné funkcie pre generovanie URL adries a šablóny pre django a jinja2.

Premýšľal som čo so svojim stránkovačom. Hodiť ho do archívneho režimu na githube? Premenovať na django-pagination-templates? Nakoniec som sa rozhodol implementovať keyset stránkovanie (nazývané niekedy aj cursor pagination). Preto som mu zmenil názov zo simple na universal, pretože podporuje obe metódy stránkovania - bežné a keyset.

Prečo ďalší stránkovač

Existuje množstvo podobných stránkovačov. Všetky sú však implementované zle. Moje stránkovanie má niektoré zásadné vlastnosti, ktoré inde chýbajú:

Zistenie prítomnosti nasledujúcej / predchádzajúcej stránky

Ostatné stránkovače používajú 2 rôzne prístupy. Buď nevedia, či sú na prvej / poslednej stránke a vrátia stále stránkovanie aj keď nasledujúca stránka bude prázdna, alebo okrem hlavného dotazu robia 2 dodatočné kvôli existencii nasledujúceho a predchádzajúceho riadku.

Môj prístup je odlišný. Na nasledujúcom obrázku je ukážka stránkovania s 5 stránkami. Ja robím select, ktorý začína riadkom z predchádzajúcej stránky vďaka čomu viem, že existuje predchádzajúca stránka a pokračujem až po riadok na nasledujúcej stránke. V iterátore odstránim prvý a posledný riadok, čím zároveň zistím existenciu nasledujúcej a predchádzajúcej strany.

Stránkovanie
Obrázok 2: Stránkovanie

Kódovanie kľúčov do URL adresy

Ako malú implementačnú pikošku ešte spomeniem kódovanie kľúčov. Kľúče sú kódované v binárnom formáte. Kóduje sa zoznam kľúčov (keďže kľúč môže byť zložený z viacerých zložiek). Každý argument začína 1-bytovou hlavičkou nasledovanou obsahom.

Hodnoty null, true a false majú vlastný typ a nulovú veľkosť. Preto sa kódujú do 1 bytu.

Typ text je trochu špeciálny, pretože jeho definícia zaberá 6 bitov z 8-bitovej hlavičky. Texty do dĺžky 64 bytov sa preto zakódujú do sekvencie dlhšej o jediný byte. Dlhšie texty do 320 bytov sa zakódujú do dĺžky textu + 2 byty. Nakoniec texty do 65856 B vyžadujú 3 dodatočné byty (16-bitová dĺžka + 1-bytová hlavička).

Celé čísla sú zakódované do 1-bytovej hlavičky nasledovanej 1, 2, 4, 8, alebo variabilnou dĺžkou ak je číslo dlhšie než 64 bytov. Čísla s pohyblivou desatinnou čiarkou sa kódujú do 9 bytov.

Čas sa kóduje do 3 - 12 bytov podľa typu, presnosti a časovej zóny.

Celý binárny reťazec sa zabalí do upraveného base64 a doplní sa príznakom smeru.

Príklad kódovaného kľúča: nBgo (podľa ID), bCABL (veľké ID, spätný chod), nHAAAADF6GpIgBgc (dátum, čas, id).

Môj balík je zverejnený v repozitári pypi.

Prílohy