探客时代
CROWD
Delta based CRDT with additional abilities
README
CROWDs
Conflict-free Reinterpretable Ordered Washed Data (Secure) - Delta based CRDT with additional abilities.
Key Properties
Conflict-free
- Any states can be merged without conflicts.
- Convergence (Strong Eventual Consistency).
- Merge result is independent of merge order (except auth units).
- Merge is semilattice.
Reinterpretable
- Same state can be reinterpreted as any Type (weak typing).
- Type of data can be changed dynamicaly without data migration.
- Cross-merge between different types is available.
Ordered
- Every data have a stable place in the document.
- Wiped data inside some Head stays tombstone to hold place.
- Interleaving-free.
Washed
- Wiped data comptely removed from state.
- Past state can't be reproduced. Snapshots/layers/changelog should be used for that.
- Garbage collection isn't required.
- But metadata size (binary, with signs) 28x of user data size (14x without signs).
Data
- All deltas are idempotent.
- Every token is just one unit.
- Delta is simply slice of full state (array of units).
- Deltas can be merged together to reduce transmit size.
Secure
- Every unit is crypto signed separately.
- Every peer checks signs and rights and rejects incorrect units.
- Every unit can be encrypted (not yet).
- Conflict-free merge without decrypt.
- Merging doesn't invalidate signs.
- Security features can be ommited if decentralization isn't required.
Real World Usages
- $hyoo_page - decentralized real-time wiki.
- $hyoo_talks - decentralized secure messanger.
- $hyoo_draw - infinity collaborative whiteboard.
- $hyoo_sketch - fast UI mockups.
- BenZen - Conflict-Free Version Control System
Articles
- The Whole Point of Conflict-Free Data Tyes (Coming soon).
- CROWD - Secure Universal CRDT (Coming soon).
Vocabulary
- World - Whole state as graph of Lands.
- Node - A single subtree which represented by few Units with same Self in different Heads.
- Unit - Minimal atomic unit of data with metadata. Actually it's edge between Nodes. And it's extended CvRDT LWW-Register.
- Land - Document direct graph which consists of (real) Units and (virtual) Nodes over them and syncs entirely.
- Self - Node id
- Head - Parent Node id.
- Prev - Previous Node id in the siblings list.
- Next - Next Node id in the siblings list.
- Auth - Global unique identifier of independent actor.
- Time - Monotonic time as count of 100ms intervals from Aeon start.
- Aeon - number of 7-year epochs from ~2022-08-04 (not yet).
- Data - Any JSON or Binary data. Size is limited by 32KB.
- Sign - Crypto sign of whole Unit data.
- kind - Type of unit (👑 grab, 🏅 give, 🔑 join, 📦 data) with different acceptance criterias.
- group - Priority of synchronization (auth, data).
- Level - Access level (law, mod, add, get).
- Peer - Any actor who have private key to make and sign Units.
- Lord - Any Peer who have law level for Land.
- King - Peer with same id as Land. He has law level in that Land by default.
- Knight - Temporary King to grab Land and grant level for current Peer and/or for all Peers.
- Home - Land where Peer is King (with same id).
- Delta - Difference of two Land states as list of Units.
- Clock - Vector clock. Dictionary which maps Peer to Time.
- Token - Minimal meaningfull part of text (space + single word / spaces / punctuation etc).
- Point - Place inside Unit. Usefull for caret position.
- Range - Range between two Points. Usefull for selection.
- Offset - Count of letters from beginning.
- Seat - Position in the list.
- Channel - Geter/Setter method. foo() - read. foo(123) - write and return written.
Internals
State/Delta Format
- ```typescript
- type Unit = Readonly<{
- land: int62
- auth: int62
- head: int62
- self: int62
- next: int62
- prev: int62
- time: int31
- data: json | bin
- sign: bin64
- }>
- type State = Unit[]
- type Delta = readonly Unit[]
- ```
Internally Units may be stored in RDBMS. Example:
- ```sql
- CREATE TABLE units (
- land int(8),
- auth int(8),
- head int(8),
- self int(8),
- next int(8),
- prev int(8),
- time int(4),
- data json,
- sign byte(64),
- )
- ```
Single Unit structure
Primary key for Units: [ Land, Head, Self ]
Sync Flow
Delta
Delta is array of 8-byte aligned binary serialized Units of same Land ordered by Aeon+Time.
Unit
Unit contains data, it global position, time of creation, authorship and sign of all of this.
Clocks
Contains last seen Times for each Peer+Group of already known Units.
Data Types Representation
Atomic CROWD Register
Single value store. Just CvRDT LWW-Register. Value is any JSON or Binary data with size <= 32KB.
$hyoo_crowd_reg
- value( next?: unknown ) Channel for raw value. Returns null by default.
- bool( next?: boolean ) Channel for boolean value. Returns false by default.
- numb( next?: number ) Channel for number value. Returns NaN by default.
- str( next?: string ) Channel for string value. Returns "" by default.
CROWD Struct
Struct is completely virtual thing. No one Unit is stored for it. Only for field values (except it's structs too, etc).
Lookup agorithm
- Make derived Head by formula:
- ``` js
- field_head = hash_62bit( field_name, struct_self )
- ```
So each Peer writes to the same Node when uses the same key.
$hyoo_crowd_struct
- sub( key: string ) Returns inner Node for field name.
- yoke( key: string, Node, king_level, base_level ) Makes or reuse Land which Self is stored inside register.
CROWD Ordered List
Properties
- New Unit is created for every item.
- Left precedence. Position of item relies on left item, then right.
- No interleaving. Sequence of left-to-right inserted items will stay together after merge.
- Removed item is remain as tombstone for ordering purposes.
Ordering Algorithm
- Input: Head value.
- Select all Units with given Head.
- Make queue as sorted found Units by Time asc, Peer asc.
- Make empty list for result.
- Iterate over all queue while it isn't empty.
- If Prev == 0, then place it at the begin.
- If Prev != 0, then locate existen Prev in the result list.
- If Prev is located, place after that.
- if Prev isn't located, then check Next:
- If Next == 0, then place it at the end.
- If Next != 0, then locate existen Prev in the result list.
- If Next is located, place before that.
- if Next isn't located, then skip unit and proceed followed.
- If unit is placed remove it from queue and start from begin of queue.
$hyoo_crowd_list
- list( next?: unknown[] ) Channel for list of raw values. Uses insert to replace content.
- set( next?: unknown[] ) Channel for list of unique raw values.
- insert( next?: unknown[], from?: number, to?: number ) Replaces range of items with reconciliation. Appends to the end when range isn't defined.
- move( from?: number, to?: number ) Moves item to another seat.
- cut( seat: number ) Removes item by seat.
- has( val: unknown ) Checks for value existence.
- add( val: unknown ) Adds value if doesn't exist.
- drop( val: unknown ) Removes value if exists.
CROWD Ordered Dictionary
It's both Struct and List:
- As list it contains keys.
- As struct it stores every key in Unit with derived Self. So, every key is Node for value.
$hyoo_crowd_dict
- keys() Channel for list of keys.
- sub( key: string, Node ) Returns inner Node for key.
- has( val: unknown ) Checks for value existence.
- add( val: unknown ) Adds value if doesn't exist.
- drop( val: unknown ) Removes value if exists.
CROWD JSON
It's recursive version of Dictionary. Special values which marks inner structures:
- {} - inner JSON.
- [] - inner List.
$hyoo_crowd_json
- json( json ) Channel for JSON.
CROWD Plain Text
Under the hood, String is just List of Tokens. So, entering word letter by letter changes same Unit instead of creating new. Text is the List of Strings which represents multiline text.