Home

Awesome

CROWDs

Conflict-free Reinterpretable Ordered Washed Data (Secure) - Delta based CRDT with additional abilities.

Key Properties

Conflict-free

Reinterpretable

Ordered

Washed

Data

Secure

Real World Usages

Articles

Vocabulary

Internals

State/Delta Format

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:

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

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

field_head = hash_62bit( field_name, struct_self )

So each Peer writes to the same Node when uses the same key.

$hyoo_crowd_struct

CROWD Ordered List

Properties

Ordering Algorithm

$hyoo_crowd_list

CROWD Ordered Dictionary

It's both Struct and List:

$hyoo_crowd_dict

CROWD JSON

It's recursive version of Dictionary. Special values which marks inner structures:

$hyoo_crowd_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.

Properties

Online sandbox

Write Algorithm

$hyoo_crowd_text

CROWD Rich Text

Under the hood, tokens are stored in the same form as in plain text. There may be elements between them in form ["div"], which can contain the same content. Every token is represented as SPAN. Every DOM element has id equal to Self. This id is using to reuse existing Units and track Nodes moving.

$hyoo_crowd_dom

CROWD Document

Delta Algorithm

Example with SQL:

SELECT *
FROM Unit
WHERE
	NOT( peer = 1 AND time <= 123 )
	AND NOT( peer = 2 AND time <= 456 )
	AND NOT( peer = 3 AND time <= 789 )
	...
ORDER BY
	time ASC,
	peer ASC

Apply Algorithm

$hyoo_crowd_land

Reinterpretations

need update

What\AsAtomStructListDictionaryTextDOM
Atom✅ Same⭕ Nullish fields✅ As single item✅ As key✅ String as tokens, other ignored✅ String as tokens, other ignored
Struct⭕ first field value✅ Same⭕ Field values❌ Field values as keys⭕ Empty⭕ Empty
List⭕ fist item⭕ Nullish fields✅ Same✅ Items as keys⭕ Strings as tokens, other ignored⭕ Items as spans
Dictionary⭕ first key✅ keys values as fields values✅ Keys✅ Same✅ Keys as tokens✅ Keys as tokens
Text❌ first token⭕ Nullish fields✅ Tokens❌ Tokens as keys✅ Same✅ Tokens as spans
DOM❌ first token⭕ Nullish fields✅ Top level items❌ Tokens as keys⭕ Text from top level tokens✅ Same

Usage Example

// // Usage from NPM. Isn't required in MAM.
// import {
//   $hyoo_crowd_land,
//   $hyoo_crowd_reg,
//   $hyoo_crowd_list,
//   $hyoo_crowd_text,
// } from 'hyoo_crowd_lib'

// Create document
const base = new $hyoo_crowd_land;

// Make independent forks for testng
const alice = base.fork({ id: '1_1' });
const bob = base.fork({ id: '2_2' });
const carol = base.fork({ id: '3_3' });

// Twice change register named "foo"
alice.chief.sub("foo", $hyoo_crowd_reg).str("A1");
alice.chief.sub("foo", $hyoo_crowd_reg).str("A2");

// Change register named "foo"
// Then converts it to sequence and insert some values
bob.chief.sub("foo", $hyoo_crowd_reg).str("B1");
bob.chief.sub("foo", $hyoo_crowd_list).insert(["B2", "B3"]);

// Replace text named "foo"
carol.chief.sub("foo", $hyoo_crowd_text).str("C1 C2");

// Make deltas
const alice_delta = alice.delta(base.clock);
const bob_delta = bob.delta(base.clock);
const carol_delta = carol.delta(base.clock);

// Cross merge all of them
alice.apply(bob_delta).apply(carol_delta);
bob.apply(alice_delta).apply(carol_delta);
carol.apply(bob_delta).apply(alice_delta);

console.log(
  ["A2", "C1", " C2", "B1", "B2", "B3"],
  alice.chief.sub("foo", $hyoo_crowd_list).list(),
  bob.chief.sub("foo", $hyoo_crowd_list).list(),
  carol.chief.sub("foo", $hyoo_crowd_list).list()
);

Sandbox

Comparison of CRDT Libraries

$hyoo_crowdAutomergeYJSdelta-crdt
Approachdelta-stateop-logdelta-statedelta-state
Garbage CollectionDoesn't requiredStores full historyEnabled by default❓
Changes signing✅ Support❌❌❓
Merge without decrypt✅ Support❌❌❓
Gzipped Bundle Size15 KB46 KB24 KB43 KB
Sequence: 500 Push + 500 Shift Perf17 ms420 ms21 ms
Sequence: 500 Push + 500 Shift Mem84 KB986 KB3.84 KB
Text: 500 Append + 500 Crop Perf21 ms480 ms18 ms
Text: 500 Append + 500 Crop Mem86 KB1_080 KB5 KB

Benchmarks

Sequence: Push + Shift

Chrome 104

FireFox 104

Text: Append + Crop

Chrome 104

FireFox 104

crdt-benchmarks

Support the Project