12 ms·

CRDTs have been on HN a lot recently. I'm working on a database that deals in events rather than raw data. Application developers specify event handlers in Java

CRDTs have been on HN a lot recently. I'm working on a database that deals in events rather than raw data. Application developers specify event handlers in JavaScript. The database layer then takes the event handlers and distributes them to the clients. Clients receive the raw stream of events and reconcile the final data state independently. The key aspect is all the event handlers are reversible. This allows clients to insert locally generated events immediately. If any remote events are received out-of-order, the client can undo events, insert the new events, and reapply everything on top of the new state. I'm curious how many people have a need for solving the real-time multi-player use case. The database I'm working on was inspired by the networking code used in fighting games (rollback netcode), but I'm always curious to learn about additional use cases.

no_wizard 4y ago
I think the most common outside of gaming is collaboration software. Think whiteboards, docs (e.g. Google Docs) and other collaborative tools.
josephg 4y ago
I want most software on my computer to be transparently collaboratively editable. Like, I want to open a draft blog post on my desktop, go out, open my phone, keep editing the post, share it with susan, then get home and see her proposed changes and merge them like I would in a code editor. And I want to be able to do that same workflow when editing video. Or when drawing. Or recording music. Or when configuring a server on AWS.
- nobu-mori 4y ago
  I agree. Everything should be collaborative. Feel free to reach out if you're interested in collaborating (email in my HN profile). I'm trying to get a v0 of this database out now, and building desirable use-cases is super important.
  - josephg 4y ago
    I'm working on a CRDT to solve this problem too[1]. How do you plan on implementing collaborative text editing on top of your event-reordering system? Off the top of my head I can't think of a way to implement text on your proposed system which would be performant and simple. [1] https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types
    - nobu-mori 4y ago
      The basic prototype I have right now works like this: The data model has this type in TypeScript: { text: string; cursors: { [userId]: { offset: number; } }; } Basically, the data model is a string of text and a set of cursors, one for each user. The cursors contain an offset into the text where each user is editing. When a user connects, the `user-connected` event is handled by setting the cursor position for that user to offset 0. When a user presses a key, an `insert-text` event is sent. The event handler for `insert-text` looks at the user's cursor position and inserts the text at that position and increases the user's cursor. Then, the event handler looks at all the cursors. Each cursor that has an offset greater than the location of the inserted text gets incremented by the length of the inserted text. Removal works the same way, but it removes text and decrements cursor offsets instead. When a user disconnects, the `user-disconnected` event handler removes the cursor to keep the total data size bounded. As an example, let's say the text was "cat boy" and User A has cursor offset 0 and User B has cursor offset 4. Imagine User A inserts "dog" just a moment before User B inserts "girl", e.g. User B sends `insert-text: "girl"`. The first time this event gets applied, "girl" gets inserted at offset 4. When User A's insertion of "dog" arrives, the insertion of "girl" gets undone and then "dog" is inserted. After "dog" is inserted, User B's cursor is now at offset 7. So when `insert-text: "girl"` is re-applied, "girl" gets inserted at offset 7 and the final text is the same. One thing I like about this system is that it's very simple. My prototype is like a collaborative notepad. The logic for state updates is only 100 lines long, including a lot of boiler plate for the event handlers (each is an interface implementation).
      - toomim 4y ago

no_wizard 4y ago

I think the most common outside of gaming is collaboration software. Think whiteboards, docs (e.g. Google Docs) and other collaborative tools.

josephg 4y ago

I want most software on my computer to be transparently collaboratively editable. Like, I want to open a draft blog post on my desktop, go out, open my phone, keep editing the post, share it with susan, then get home and see her proposed changes and merge them like I would in a code editor. And I want to be able to do that same workflow when editing video. Or when drawing. Or recording music. Or when configuring a server on AWS.

nobu-mori 4y ago
I agree. Everything should be collaborative. Feel free to reach out if you're interested in collaborating (email in my HN profile). I'm trying to get a v0 of this database out now, and building desirable use-cases is super important.
- josephg 4y ago
  I'm working on a CRDT to solve this problem too[1]. How do you plan on implementing collaborative text editing on top of your event-reordering system? Off the top of my head I can't think of a way to implement text on your proposed system which would be performant and simple. [1] https://github.com/josephg/diamond-types https://github.com/josephg/diamond-types
  - nobu-mori 4y ago
    The basic prototype I have right now works like this: The data model has this type in TypeScript: { text: string; cursors: { [userId]: { offset: number; } }; } Basically, the data model is a string of text and a set of cursors, one for each user. The cursors contain an offset into the text where each user is editing. When a user connects, the `user-connected` event is handled by setting the cursor position for that user to offset 0. When a user presses a key, an `insert-text` event is sent. The event handler for `insert-text` looks at the user's cursor position and inserts the text at that position and increases the user's cursor. Then, the event handler looks at all the cursors. Each cursor that has an offset greater than the location of the inserted text gets incremented by the length of the inserted text. Removal works the same way, but it removes text and decrements cursor offsets instead. When a user disconnects, the `user-disconnected` event handler removes the cursor to keep the total data size bounded. As an example, let's say the text was "cat boy" and User A has cursor offset 0 and User B has cursor offset 4. Imagine User A inserts "dog" just a moment before User B inserts "girl", e.g. User B sends `insert-text: "girl"`. The first time this event gets applied, "girl" gets inserted at offset 4. When User A's insertion of "dog" arrives, the insertion of "girl" gets undone and then "dog" is inserted. After "dog" is inserted, User B's cursor is now at offset 7. So when `insert-text: "girl"` is re-applied, "girl" gets inserted at offset 7 and the final text is the same. One thing I like about this system is that it's very simple. My prototype is like a collaborative notepad. The logic for state updates is only 100 lines long, including a lot of boiler plate for the event handlers (each is an interface implementation).
    - toomim 4y ago