dotJS 2019 - James Long - CRDTs for Mortals

dotJS 2019 - James Long - CRDTs for Mortals — dotconferences

dotconferences

AI-assisted summary of dotJS 2019 - James Long - CRDTs for Mortals — original source. Check the original for full context.

Source published:

Key ideas

  • Local-first applications require treating client devices as independent nodes in a distributed system, rendering naive offline request-queuing strategies ineffective under real-world conditions. (0:09)
  • By modeling database tables as Grow-Only Sets of Last-Write-Wins Maps (LWW-Maps), developers can layer CRDT synchronization directly onto standard SQLite databases without sacrificing sub-millisecond local read performance. (16:03)
  • A robust local-first synchronization engine does not require massive frameworks: James Long implemented Hybrid Logical Clocks in 256 lines of dependency-free JavaScript, while Actual's complete production client sync layer spans only 630 lines. (9:39)
  • Manual conflict resolution hooks pushed to application developers inevitably fail; conflict freedom must be baked directly into the data structures and domain shapes themselves via commutativity and idempotence. (11:23)

Detailed notes

## Background Published on YouTube by dotconferences on January 9, 2020, this presentation was recorded at dotJS 2019 in Paris. According to the page description, speaker James Long explores the intersection of frontends and Conflict-Free Replicated Data Types (CRDTs), demonstrating how simple CRDT implementations deliver on the promise of robust, local-first applications with superior user experience.

## TL;DR James Long argues that reliable offline software requires treating client devices as distributed systems and adopting a local-first architecture powered by on-device storage like SQLite. To overcome the synchronization hurdles of unreliable ordering and concurrent edits, he introduces Hybrid Logical Clocks for causal ordering and CRDTs—specifically Last-Write-Wins Maps and Grow-Only Sets—to achieve automatic, deterministic convergence. By modeling database mutations as an append-only stream of cell-level messages and soft deletes, systems eliminate the need for error-prone manual conflict resolution. Demonstrating that his production sync engine in Actual Budget requires only a few hundred lines of dependency-free JavaScript, Long emphasizes that simplicity is the true prerequisite for distributed reliability.

## Atmosphere & style The talk carries an energetic, pragmatic, and candidly irreverent tone, playfully puncturing the intimidating academic jargon that usually surrounds distributed systems theory. Long speaks with the reassuring confidence of a builder who implemented these primitives in production, balancing technical rigor with lighthearted humor about developer habits and dependency bloat. Watching the talk feels both demystifying and empowering, turning an esoteric computer science concept into an approachable, elegant blueprint for everyday engineering.

## Bulletin - [00:09](https://www.youtube.com/watch?v=DEcwa68f-jY&t=9s) Local-first applications require treating client devices as independent nodes in a distributed system, rendering naive offline request-queuing strategies ineffective under real-world conditions. - [16:03](https://www.youtube.com/watch?v=DEcwa68f-jY&t=963s) By modeling database tables as Grow-Only Sets of Last-Write-Wins Maps (LWW-Maps), developers can layer CRDT synchronization directly onto standard SQLite databases without sacrificing sub-millisecond local read performance. - [09:39](https://www.youtube.com/watch?v=DEcwa68f-jY&t=579s) A robust local-first synchronization engine does not require massive frameworks: James Long implemented Hybrid Logical Clocks in 256 lines of dependency-free JavaScript, while Actual's complete production client sync layer spans only 630 lines. - [11:23](https://www.youtube.com/watch?v=DEcwa68f-jY&t=683s) Manual conflict resolution hooks pushed to application developers inevitably fail; conflict freedom must be baked directly into the data structures and domain shapes themselves via commutativity and idempotence.

## Key takeaways - [00:09](https://www.youtube.com/watch?v=DEcwa68f-jY&t=9s) Local-first architecture represents a complete paradigm shift over offline-first progressive enhancement, running full application code and data directly on the client machine. - [00:09](https://www.youtube.com/watch?v=DEcwa68f-jY&t=9s) Queueing offline API calls into an array to push upon reconnecting fails because intermittent clients inherently form an asynchronous distributed system. - [02:12](https://www.youtube.com/watch?v=DEcwa68f-jY&t=132s) Keeping application data strictly client-side enables safe, open-ended ad-hoc queries—like Mongo-style queries compiled to raw SQLite—without exposing servers to injection or denial-of-service risks. - [02:12](https://www.youtube.com/watch?v=DEcwa68f-jY&t=132s) Synchronization engines should live as decoupled abstraction layers above standard relational databases rather than forcing developers to abandon battle-tested storage like SQLite. - [04:58](https://www.youtube.com/watch?v=DEcwa68f-jY&t=298s) Distributed synchronization faces two fundamental hurdles: unpredictable arrival ordering across peers and simultaneous write conflicts. - [04:58](https://www.youtube.com/watch?v=DEcwa68f-jY&t=298s) Offline-capable systems must abandon strong consistency models requiring synchronous network locks and instead embrace eventual consistency. - [07:25](https://www.youtube.com/watch?v=DEcwa68f-jY&t=445s) Physical device clocks cannot determine causal order across machines due to drift, while global incremental sequence IDs require unavailable central coordinators. - [09:39](https://www.youtube.com/watch?v=DEcwa68f-jY&t=579s) Hybrid Logical Clocks (HLCs) combine physical time and monotonic counters into compact strings that can be compared lexicographically to establish deterministic ordering across devices. - [09:39](https://www.youtube.com/watch?v=DEcwa68f-jY&t=579s) Simplicity is a prerequisite for distributed systems reliability, proven by a fully functional HLC implementation fitting into 256 lines of dependency-free JavaScript. - [11:23](https://www.youtube.com/watch?v=DEcwa68f-jY&t=683s) Delegating conflict resolution to user-defined hooks or manual callbacks fails due to the insurmountable edge cases of distributed state spaces. - [12:26](https://www.youtube.com/watch?v=DEcwa68f-jY&t=746s) CRDTs rely on two core mathematical properties—commutativity (order independence) and idempotence (duplication safety)—allowing clients to blindly broadcast changes until convergence. - [16:03](https://www.youtube.com/watch?v=DEcwa68f-jY&t=963s) SQLite can be converted into a distributed CRDT engine using an auxiliary `messages_crdt` table that tracks timestamp, dataset, row, column, and value for every atomic change. - [16:03](https://www.youtube.com/watch?v=DEcwa68f-jY&t=963s) Because Grow-Only Sets cannot physically delete records without creating distributed write anomalies, deletions must be modeled using tombstone flags. - [19:02](https://www.youtube.com/watch?v=DEcwa68f-jY&t=1142s) Intentional data modeling, such as dedicated mapping tables for category changes, eliminates merge conflicts before they can mechanically occur. - [19:02](https://www.youtube.com/watch?v=DEcwa68f-jY&t=1142s) A full production-grade synchronization engine can remain extremely lightweight, requiring only 630 lines of client JavaScript in Actual and 132 lines on the relay server.

## Detailed walkthrough ### [00:09](https://www.youtube.com/watch?v=DEcwa68f-jY&t=9s) The Promise and Pain of Local-First Apps

James Long opens by asking why offline-first applications have never truly taken off across the software industry. The web fundamentally suffers from an inability to work without network access, and even when a network is present, high latency and patchy connections degrade the user experience into something that feels sluggish and unpleasant. The logical architectural response is to design software for offline operation from day one, which essentially requires building a fully local application where all code and application data reside directly on the client machine. Long emphasizes that he prefers the term “local-first apps” over offline-first, because local execution represents a complete architectural paradigm shift rather than just a progressive enhancement.

However, once an application keeps all of its data locally across multiple devices, synchronization becomes a massive, unavoidable hurdle. Many software teams attempt naive approaches that fall apart immediately under real-world conditions. When web applications attempt to paste offline capabilities onto traditional cloud architectures, users inevitably run into anxiety-inducing user interface errors when the network drops.

> “You cannot just queue up changes into an array when you are offline and then when you come back on online push them out to the server that does not work.”

To make genuine progress, developers have to shed these naive client-server mental models and confront what they are actually building.

> “The first thing we need to do is we have to admit that local apps they are a distributed system there's no way around that.”

- **The broken offline experience:** Mainstream web apps often flash warning banners stating, *“Attempting to restore a connection; changes may not be saved,”* leaving the user uncertain about their data’s fate. - **Distributed reality:** Every client running on an isolated phone, tablet, or desktop acts as an independent node that executes arbitrary operations before reconciling state with the rest of the network.

[02:12](https://www.youtube.com/watch?v=DEcwa68f-jY&t=132s) Building Actual Budget and Keeping SQLite

Long introduces his background as the creator of Prettier before discussing his project: Actual, a personal finance desktop and mobile app built around a local-first architecture. When designing Actual, the non-negotiable requirements were offline availability, blistering speed, strong user privacy, and support for arbitrary ad-hoc queries. Storing everything on-device immediately delivers extreme responsiveness without complex caching layers. Because user data is kept strictly client-side, the application can safely allow users to execute open-ended data explorations—featuring a MongoDB-like query syntax that compiles directly into raw SQLite—without exposing an application server to arbitrary code execution or injection exploits.

```mermaid flowchart TD accTitle: Local-First Application Architecture in Actual accDescr: Shows the relationship between client UI, SQLite storage, and the layered sync engine.

subgraph ClientDevice["Local Client (Desktop / Mobile)"] UI["Application UI / Custom Reports"] QueryEngine["Query Compiler (Mongo-like Syntax)"] DB[(Local SQLite DB)] SyncEngine["Sync Engine Layer"] end

RemoteServer["Minimal Relay / Storage Server"]

UI --> QueryEngine QueryEngine -->|"Sub-millisecond reads"| DB UI -->|"Local writes"| DB DB <--> SyncEngine SyncEngine <-->|"Propagates changes"| RemoteServer ```

To support entering transactions on the go, Long needed a mobile client that could synchronize with the desktop app. He was unwilling to adopt existing third-party syncing ecosystems because they forced developers to abandon standard relational databases and hand over control of their persistence layer. SQLite provided reliable, sub-millisecond local read queries that powered the entire UI, meaning any synchronization solution had to live strictly as an abstraction layer decoupled from the storage engine itself.

> “I did not want to give up SQLite; it gives me sub-millisecond read queries, which is absolutely amazing, it's the whole reason why the app is fast.”

- **Data scale:** Personal financial databases typically run between 5 and 10 megabytes, making multi-terabyte distributed database techniques overkill. - **Client safety:** Exposing raw querying capabilities like aggregate sums locally is completely safe, whereas cloud APIs like GraphQL strictly avoid arbitrary aggregates for security and denial-of-service reasons. - **Seamless synchronization:** Desktop and mobile clients must support concurrent updates, category creation, merges, and deletions, converging on the exact same state without data loss.

[04:58](https://www.youtube.com/watch?v=DEcwa68f-jY&t=298s) The Two Synchronization Hurdles: Unreliable Ordering and Conflicts

Building a custom synchronization engine brings developers face-to-face with two fundamental distributed systems problems: unreliable ordering and conflicts. In a local-first application, reliability must be absolute; users cannot simply refresh the browser tab to resolve broken states or recover corrupted data. When two independent clients mutate state over time, developers naturally want to imagine a single linear timeline where every change happened in a strict sequence. In practice, latency, physical network boundaries, and intermittent connectivity mean that events arrive at different peers in completely different sequences.

If Client A performs actions $A$, $C$, and $D$ while Client B performs action $B$, Client A might observe the stream of changes as $A \rightarrow C \rightarrow D \rightarrow B$, whereas Client B might receive and process them as $B \rightarrow A \rightarrow D \rightarrow C$. Naively executing state mutations upon receipt guarantees state divergence. While traditional backend systems rely on strong consistency models with intensive multi-node coordination, such mechanisms fail when devices are offline. Local-first architectures must instead embrace eventual consistency by accepting that concurrent timelines exist simultaneously.

> “A recent trend is to do eventual consistency, and this is a technique where you embrace the fact that there are multiple timelines, you embrace the fact that you are a distributed system, you admit that and then you find solutions that mesh well with that instead of trying to go against that.”

- **Strong consistency drawbacks:** Requires constant network roundtrips, locks, and strict global coordination—making it fundamentally incompatible with offline clients. - **The eventual consistency guarantee:** So long as all clients eventually observe the same set of operations, regardless of the order in which those operations are received, every client must deterministically converge on identical state.

[07:25](https://www.youtube.com/watch?v=DEcwa68f-jY&t=445s) Taming Time with Hybrid Logical Clocks

To solve unreliable ordering without a central coordinator, changes must be tagged with robust timestamps that establish causal relationships rather than physical clock time. Relying on physical system time via primitives like JavaScript's `Date.now()` is disastrous because device clocks drift, jump backwards, and cannot be trusted across disparate hardware. Furthermore, assigning an incremental integer sequence ID is impossible without a centralized authority granting numbers sequentially.

Instead, distributed systems use specialized logical timekeeping mechanisms. While vector clocks track causality by keeping an entry for every known peer, Long opts for a Hybrid Logical Clock (HLC). An HLC combines physical clock readings with a monotonically increasing logical counter into a single compact structure that can be easily serialized into a standard string. Running locally on each device without coordinating with a central server, an HLC produces timestamps that allow any syncing peer to compare two disparate mutations and determine their relative causal order.

> “All that we care about is when you assign a timestamp to a change, the clock is smart enough to give us—us being the ephemeral whoever is trying to sync some data—so that we can compare changes and say, ‘Did this change, when it happened on this machine, did it come after all of these other things that the machine has already seen?’”

- **Why physical clocks fail:** Client clocks fluctuate wildly across different hardware, meaning wall-clock timestamps cannot guarantee causal order or resolve concurrency. - **Why global sequence IDs fail:** Generating global sequential IDs ($1, 2, 3\dots$) requires strict real-time locking and network availability, which directly contradicts local-first operation. - **HLC advantages:** Encapsulates physical and logical progression, serializes into a comparable string representation, and operates independently on each device.

[09:39](https://www.youtube.com/watch?v=DEcwa68f-jY&t=579s) Hybrid Logical Clocks and the Value of Simplicity

James Long explains that when ordering operations, such as determining whether setting `x` to `3` wins over an earlier write in a last-write-wins strategy, systems rely on timestamps. However, developers should not be confused by timestamps that merely look like conventional dates. The underlying mechanism is a Hybrid Logical Clock (HLC). While there is an entire academic paper detailing the algorithm, the core practical concept is straightforward: an HLC produces a formatted string that can be compared lexicographically using simple standard operators (such as string `<` string) to reliably determine causality and order across devices.

Channeling Edsger W. Dijkstra's famous maxim that simplicity is a prerequisite for reliability, Long emphasizes that distributed systems are inherently intricate, but their solutions must not be. To build a system that achieves 100% reliability—surviving intermittent network conditions or recovering cleanly after a user leaves their phone in a drawer for two weeks—the codebase must remain as small and concise as possible. As proof, he showcases an implementation of Hybrid Logical Clocks that requires no external dependencies and fits in just 256 lines of JavaScript. He argues that developers frequently overcomplicate problems by trying to take on too much at once, rather than distilling the core challenge into a minimal, dependency-free implementation.

> “Dijkstra said simplicity is a prerequisite for reliability. This is a complex problem, distributed apps and distributed systems is a complex problem, and the way to have it reliable is to have a simple solution.” — James Long

- HLCs format timestamps into strings that are directly comparable to determine which event came first. - The presented HLC implementation is completely standalone: 0 dependencies and 256 lines of JavaScript. - Long cautions against over-engineering: “Dependencies suck,” so distilling the problem into a small, auditable footprint is vital.

---

[11:23](https://www.youtube.com/watch?v=DEcwa68f-jY&t=683s) Why Manual Conflict Resolution Fails

Establishing a reliable ordering mechanism still does not erase the reality of conflicting edits when two offline clients modify the same data field simultaneously before reconnecting. Long strongly criticizes traditional architectural approaches that delegate conflict resolution to user-written hooks or manual callbacks. In his view, pushing manual conflict resolution onto application developers is unfair and doomed to fail because the state space has far too many edge cases for even talented engineers to handle correctly.

Instead of treating conflict management as an afterthought or a cleanup step that runs after a sync cycle finishes, systems must handle conflicts inherently at the data modeling layer. Resolving conflicts must be baked directly into the data structures and shapes used by the application from the start.

> “Manual conflict resolution does not work; it's basically just issuing one of the hardest parts of this whole thing on to you, and as a developer, you are not gonna write correct manual conflict resolvers.” — James Long

---

[12:26](https://www.youtube.com/watch?v=DEcwa68f-jY&t=746s) Demystifying CRDTs: Commutativity and Idempotence

To solve synchronization without manual intervention, Long introduces Conflict-Free Replicated Data Types (CRDTs). He jokes about the academic jargon that often intimidates developers—parodying explanations that describe them as “a partially ordered monoid in the category of endofunctors with a least upper bound, so it's a semilattice essentially”—before assuring the audience that production systems require only a small fraction of the academic theory.

At their core, CRDTs are data structures characterized by two fundamental mathematical properties: commutativity and idempotence. Together, these properties grant a system extraordinary resilience under hostile network conditions, allowing clients to blindly broadcast updates until states converge.

```mermaid flowchart LR accTitle: CRDT Mathematical Properties accDescr: Diagram showing commutativity and idempotence leading to network resilience. subgraph Properties["Core Properties"] C["Commutative: Order does not matter"] I["Idempotent: Re-applying changes does not alter state"] end subgraph Outcome["System Result"] R["Superpower: Blindly send messages until states converge"] end C --> R I --> R ```

> “If it doesn't matter what order you apply changes, and it doesn't matter how many times you apply that change, you can essentially just throw changes over the wall, and if the state is not what you think it should be, then you just throw some more changes; I mean, it's essentially a superpower, right?” — James Long

- **Commutative**: Changes can be applied in any sequence and yield the identical state. - **Idempotent**: Applying the exact same change multiple times produces no additional side effects. - **Last-Write-Wins Map (LWW-Map)**: Demonstrated by setting values on keys (e.g., `x`, `y`, `z`). When a write of `x = 8` arrives after `x = 300` but bears an older HLC timestamp, the update is ignored. If updates arrive out of order, the higher timestamp ultimately overwrites the lower timestamp once received, converging on the exact same result regardless of receipt order. - **Grow-Only Set (G-Set)**: A collection where elements can only be added, never deleted. Because removing an item locally risks conflicts with incoming edits targeting that removed item, items in distributed sets can never be physically purged.

---

[16:03](https://www.youtube.com/watch?v=DEcwa68f-jY&t=963s) Turning SQLite into a Distributed CRDT Database

To translate these abstract concepts into real-world application storage, Long models a standard SQLite database table as a G-Set of LWW-Maps. He implements this mechanism using a single auxiliary table named `messages_crdt`. This table tracks every atomic change ever observed by the local node, regardless of whether the change was authored locally or synced from a remote peer.

```mermaid flowchart TD accTitle: SQLite CRDT Message Sync Flow accDescr: Flowchart illustrating how local and remote mutations pass through the messages table to update SQLite state. subgraph Input["Operations"] Local["Local Update / Delete"] Remote["Remote Sync Messages"] end subgraph SyncLayer["CRDT Sync Engine"] MsgTable["messages_crdt Table: dataset, row, column, value, timestamp"] end subgraph Storage["SQLite Target Tables"] CellUpdate["Update cell if timestamp > existing timestamp"] end Local --> MsgTable Remote --> MsgTable MsgTable --> CellUpdate ```

The `messages_crdt` table schema contains five primary fields: `timestamp` (the HLC timestamp), `dataset` (the target table name), `row` (the target row ID), `column` (the target column name), and `value` (the payload). As changes stream in, the engine updates the specific table cell if the incoming message's timestamp is newer than what currently resides in that position. If the row does not yet exist, SQLite inserts the row and populates that initial cell, gradually assembling the full record as subsequent column messages arrive.

- **Fast Local Reads**: Queries execute as raw, high-performance SQLite reads against local tables without any sync overhead during query execution. - **Unified Writes**: The application writes locally via helper functions such as `update(table, id, fields)`. Local mutations follow the identical code path as inbound sync events: both construct discrete message envelopes and process them through the syncing layer. - **Tombstones for Deletion**: Because G-Sets forbid physical deletion, a dedicated `delete(table, id)` function writes an update message setting a `tombstone` column to `1`. Read queries subsequently filter out tombstoned rows. - **Additional Capabilities**: Long notes that overall dataset consistency across clients can be validated using a Merkle tree (a tree of hashes tracking applied timestamps), and the entire architecture can be end-to-end encrypted across an untrusted sync relay server. - **Offline Category Demo**: Long demonstrates killing the sync server while continuing to add data offline, such as adding an item under a new category on one device while deleting that category on another. Through pre-mapped fallback logic (e.g., mapping obsolete categories into "Personal"), the clients smoothly reconcile their view hierarchies as messages sync upon reconnecting.

> “To change my local data, it's exactly the same way as syncing: when I get messages from other people, it syncs it through, it pushes it through the syncing layer; when I change stuff myself, I just call update, generates the messages, and it pushes it through the syncing layer—it's all the exact same thing.” — James Long

[19:02](https://www.youtube.com/watch?v=DEcwa68f-jY&t=1142s) Data Shaping and the Tiny Footprint of CRDTs

While conflict resolution often dominates discussions around distributed data, James Long explains that clever data modeling can prevent conflicts from happening in the first place. He notes that while he cannot explore every single technique in the talk, the core strategy is to intentionally shape your data model so that you “just bypass them altogether and that there doesn't exist a conflict.” In his own application, Actual, he uses approaches like a dedicated mapping table to handle categories automatically, ensuring that common conflicting states simply cannot arise mechanically.

```mermaid flowchart LR accTitle: Client-Server Sync Architecture accDescr: Diagram illustrating the minimal architecture and line counts of the sync implementation.

subgraph Client ["Client (Actual App)"] CL["Client Sync Layer<br/>(630 lines of JS)"] DB["Local Database Layer"] CL <--> DB end

subgraph Server ["Sync Server"] SRV["Message Relay Server<br/>(132 lines of JS)"] end

CL <-->|"Send / Receive Messages"| SRV ```

Beyond eliminating conflicts through structure, Long reveals just how lightweight a production-grade CRDT sync implementation can actually be. In his open-source sample repository, the entire client-side syncing layer and database logic fit into a mere 250 lines of JavaScript, while the backend server requires only 132 lines because its job is merely to receive messages and forward them back out. Even in his commercial personal finance product, Actual, the complete client sync layer totals only 630 lines of JavaScript. Putting that into perspective, he jokes that it amounts to about 65 tweets: “How long does it take you to tweet 65 times? Friday in bed tweet like 20 times so it's like three nights.” Crucially, this small footprint does not rely on massive, hidden third-party libraries. Its only dependencies are standard utilities for UUID generation and MurmurHash, avoiding the trap—referenced by speaker Christian Heilmann earlier in the conference—of stuffing complexity away into massive dependencies:

> “The only dependency is that it has our UUID and MurmurHash, right? You're not I'm not shoving garbage into the closet and then it's actually you're pulling in like a 150 megabyte dependency like Chris Heilmann said yesterday; this is the real code.”

- **Sample sync implementation:** 250 lines of client-side JavaScript (syncing + database) and 132 lines of server-side JavaScript. - **Production app (Actual):** 630 lines of client-side JavaScript for the entire synchronization engine. - **External dependencies:** Only `uuid` and `murmurhash`, ensuring no bloated dependency graph hides behind the low line count.

[20:09](https://www.youtube.com/watch?v=DEcwa68f-jY&t=1209s) The Local-First Future: Keep It Simple

Long wraps up by returning to the central motivation behind this architectural shift: delivering unmatched speed, resilience, and reliability to end users. Applications built local-first provide an inherently superior user experience because operations are instant and independent of network availability. He urges frontend and full-stack developers to demystify distributed systems concepts and embrace simple implementations of logical clocks and CRDT primitives instead of reaching for bloated frameworks or assuming offline sync is too complex for mortal engineers.

Long leaves the audience with a direct call to resist unnecessary software bloat:

> “We've got to start simplifying our solutions and not take on so much code which makes things more complex.”

## Notable quotes > [00:09](https://www.youtube.com/watch?v=DEcwa68f-jY&t=9s) The first thing we need to do is we have to admit that local apps they are a distributed system there's no way around that. — James Long

> [11:23](https://www.youtube.com/watch?v=DEcwa68f-jY&t=683s) Manual conflict resolution does not work; it's basically just issuing one of the hardest parts of this whole thing on to you, and as a developer, you are not gonna write correct manual conflict resolvers. — James Long

> [00:09](https://www.youtube.com/watch?v=DEcwa68f-jY&t=9s) You cannot just queue up changes into an array when you are offline and then when you come back on online push them out to the server that does not work. — James Long

## Mentioned James Long, Prettier, Actual, SQLite, MongoDB, GraphQL, Edsger W. Dijkstra, Christian Heilmann, Hybrid Logical Clock, CRDT, Merkle tree, MurmurHash, UUID

## Video description Filmed at https://2019.dotjs.io on December 5-6, 2019 in Paris. More talks on https://dotconferences.com/talks

What do CRDTs and frontends have to do with each other? James talks about how CRDTs finally deliver on the promise of local-first apps, which provide superior user experience, and explains how simple CRDTs can be and how to leverage them to create robust local-first apps.

[Source](https://www.youtube.com/watch?v=DEcwa68f-jY)

中文简报

dotJS 2019 - James Long:凡人也能懂的 CRDT James Long 认为,可靠的离线软件需要将客户端设备视为分布式系统,并采用由 SQLite 等端上存储驱动的本地优先(local-first)架构。为克服不可靠排序与并发编辑带来的同步难题,他引入混合逻辑时钟(HLC)来实现因果排序,并利用 CRDT——特别是最后写入者获胜映射(LWW-Map)和只增集合(G-Set)——来达成自动且确定性的数据收敛。通过将数据库变更建模为由单元格级别消息和软删除构成的仅追加流,系统便无需进行易出错的人工冲突解决。Long 展示了他在 Actual Budget 中的生产级同步引擎仅需几百行无依赖的 JavaScript 代码,借此强调极简才是分布式可靠性的真正前提。 本地优先应用需要将客户端设备视为分布式系统中的独立节点,这使得简单的离线请求排队策略在真实场景下失去效用。 (0:09) 通过将数据库表建模为由最后写入者获胜映射(LWW-Map)组成的只增集合(G-Set),开发者可以在标准 SQLite 数据库之上直接叠加 CRDT 同步机制,同时丝毫不牺牲亚毫秒级的本地读取性能。 (16:03) 健壮的本地优先同步引擎无需庞大的框架:James Long 用 256 行无外部依赖的 JavaScript 实现了混合逻辑时钟,而 Actual 的完整生产级客户端同步层也仅有 630 行代码。 (9:39) 交由应用开发者处理的人工冲突解决钩子注定会失败;无冲突特性必须通过可交换性与幂等性,直接融入数据结构和领域形态本身。 (11:23)

Reading summary

James Long argues that developers should build offline-capable software as local-first distributed systems, using lightweight Conflict-Free Replicated Data Types (CRDTs) and logical clocks rather than bloated frameworks or manual conflict handlers. The Local-First Shift and SQLite Storage (0:09) Long distinguishes local-first architecture from progressive offline enhancements, noting that web apps attempting to queue requests naively leave users stranded with connection errors. In building his personal finance application, Actual, Long required sub-millisecond local reads, strong privacy, and arbitrary aggregate querying over personal financial datasets (typically 5 to 10 megabytes). These needs led him to retain a local SQLite database rather than hand persistence over to third-party sync platforms. Ordering Mutations with Hybrid Logical Clocks (7:25) Because concurrent operations across separate devices do not follow a single timeline, strong consistency models fail when nodes are offline. Physical wall clocks like JavaScript's Date.now() drift, and global integer sequences require unavailable centralized authorities. Long addresses unreliable ordering through Hybrid Logical Clocks (HLCs), which blend physical time and a monotonic logical counter into serializable strings that can be compared lexicographically using basic string operators. CRDT Properties and Data Model Conflicts (11:23) Long rejects delegating synchronization conflicts to user-written manual resolvers or callbacks, arguing that developers cannot anticipate the full state space of distributed edge cases. Instead, conflicts must be eliminated by data modeling or handled mathematically by CRDTs through commutativity (operations apply in any order) and idempotence (re-applying an operation causes no extra side effects). Techniques like Last-Write-Wins Maps (LWW-Maps) and Grow-Only Sets (G-Sets) allow clients to broadcast updates repeatedly until state converges deterministically. Implementing Distributed Sync Inside SQLite Tables (16:03) To adapt SQLite to a distributed CRDT model, Long structures tables as G-Sets of LWW-Maps using a messages_crdt auxiliary table with five fields: timestamp, dataset, row, column, and value. Writes, whether local or remote, follow an identical code path, updating a specific cell only if the incoming message's HLC timestamp exceeds the existing value. Because G-Sets forbid physical row deletions, the engine records tombstones by setting a dedicated column to 1, while read queries filter out marked rows. Minimal Code Footprint and System Simplicity (19:02) Invoking Edsger W. Dijkstra's dictum that simplicity is a prerequisite for reliability, Long argues that distributed sync does not require heavyweight libraries. His standalone HLC implementation spans 256 lines of JavaScript with zero dependencies. In Actual, the entire client sync layer comprises 630 lines of JavaScript relying only on uuid and murmurhash, while an open-source sample implementation fits the client database and syncing code in 250 lines and a relay server in 132 lines. Long urges developers to strip away software bloat and embrace simple local-first primitives, demonstrating that reliable offline synchronization can be achieved with concise, auditable implementations.

精炼阅读摘要

James Long在dotJS 2019演讲中指出,本地优先(local-first)架构的本质是分布式系统,开发者无需依赖庞大框架或复杂的学术理论,仅凭极简的代码与基础CRDT(无冲突复制数据类型)即可在常规关系型数据库上实现高可靠的多端同步。 本地优先架构的范式转变与SQLite优势 (0:09) Long认为传统Web应用将离线功能视作渐进增强是错误的,离线网络中断时弹出的警告条暴露出客户端-服务端思维的缺陷。单纯在离线时把变更排队并在联网后推送无法解决同步问题,因为每一个在手机、平板或桌面上运行的应用都是一个完全独立的分布式节点。他在构建个人记账软件Actual时,确立了绝对离线可用、亚毫秒级响应、用户隐私以及支持即席查询的原则。个人财务数据规模通常在5到10兆字节,完全不需要多TB级分布式架构的复杂缓存层。 为了兼顾极速查询与多端同步,Long拒绝放弃SQLite。在本地执行类似MongoDB语法的复杂聚合查询完全安全,不会引发云端API面临的代码注入或拒绝服务攻击。UI直接依赖本地SQLite的亚毫秒级读取,因此同步机制必须设计为完全独立于存储引擎之上的抽象层,既保留标准关系数据库的控制权,又实现桌面与移动设备间的并发更新合并。 混合逻辑时钟:解耦中心协调的时序判定 (7:25) 分布式本地应用面临无序到达与编辑冲突两大核心障碍。由于网络延迟与离线隔离,各节点接收操作事件的顺序常常完全不同,而强一致性所需的实时全局锁定和网络往返与本地优先模式根本冲突。系统必须转向最终一致性模型。然而,物理时钟(如JavaScript的Date.now())存在漂移和回拨,无法用于因果排序;在缺乏中央协调者的情况下,也无法分配单调递增的全局序列号。 Long采用混合逻辑时钟(Hybrid Logical Clock, HLC)作为替代方案。HLC将物理时间与单调递增的逻辑计数器结合成紧凑结构,序列化为普通字符串后,即可直接通过标准字符串比较运算符进行字典序比较,无需联网就能判断两次变更的因果先后。Long援引Dijkstra关于“简单是可靠性先决条件”的名言,展示了一个仅用256行JavaScript且零依赖的HLC独立实现,证明分布式时序方案完全可以摆脱臃肿的代码库。 废弃手动合并:CRDT数学属性与数据塑形 (11:23) Long批评将冲突解决交由应用层回调或用户自定义钩子的做法,认为这把系统中最复杂的边缘场景转嫁给开发者,注定会导致状态损坏。真正的解法必须内嵌在数据模型中。CRDT(无冲突复制数据类型)虽然充斥着抽象学术术语,但实际生产系统核心只依赖两个数学属性:可交换性(操作应用顺序无关)和幂等性(重复执行相同变更无额外副作用)。拥有这两项特性的系统可以无序、重复地广播消息,直至最终状态确定性收敛。 在此基础上,Long结合最后写入胜出映射(LWW-Map)和只增集合(G-Set)来构造数据层。在分布式集合中,直接物理删除元素会引发与后续传入编辑的冲突,因此物理删除被禁止,转而采用墓碑机制(Tombstones)。此外,Long强调巧妙的数据建模能从根源上规避冲突,例如在Actual中设计专用的分类映射表,使并发修改在结构上无法产生冲突状态。 基于SQLite的CRDT落地与极简代码实现 (16:03) 在工程实现上,Long将SQLite数据表建模为由LWW-Map组成的G-Set,核心依赖一张包含五列的辅助表messages_crdt:timestamp(HLC时钟)、dataset(目标表)、row(行ID)、column(列名)和value(数据值)。本地修改与远程同步采用完全一致的代码路径:本地调用update函数时会构造消息并推入同步层;一旦传入消息的HLC时间戳更新,SQLite便更新对应单元格,若目标行不存在则逐步插入补全。删除操作则通过delete函数将tombstone列标记为1,读查询自动过滤墓碑数据。 该方案不仅支持通过Merkle树校验多端一致性以及在中继服务器上实施端到端加密,更展现出极小的代码体积。开源演示中,客户端同步与数据库逻辑仅250行JavaScript,中继服务端仅132行;商业产品Actual的客户端同步核心也仅有630行代码,且除uuid和murmurhash外无任何外部依赖。Long借此强调,开发者应停止向项目中堆砌庞大依赖,用精炼透明的代码同样能构建出高韧性的分布式应用。 Long认为本地优先架构能为最终用户带来立即可用与无视网络波动的优异体验,但如何将这种以单元格为粒度的LWW-Map和墓碑清理机制推广到更大规模的数据集与更复杂的协同文档场景,仍是该模式在工程实践中需要持续权衡的问题。

Detailed notes — zh

## Background 该视频由 dotconferences 于 2020 年 1 月 9 日发布在 YouTube 平台上,记录了 James Long 于 2019 年 12 月在巴黎 dotJS 大会上的演讲。官方简介指出,本次演讲深入探讨了 CRDT 与前端开发的紧密关联,展示了 CRDT 如何真正兑现“本地优先(Local-first)”应用提供卓越用户体验的承诺,并阐述了利用轻量极简的 CRDT 构建稳健应用的实现路径。 ## TL;DR Prettier 创作者 James Long 结合其记账软件 Actual 的研发实践,直击传统 Web 应用因依赖网络而体验欠佳的痛点,主张采用数据与逻辑 100% 常驻本地的“本地优先(Local-first)”架构,以充分发挥本地 SQLite 的亚毫秒级响应优势。面对多设备协同这一天然的分布式难题,他指出手动冲突合并注定失败,并引入了仅用 256 行纯 JavaScript 实现的混合逻辑时钟(HLC)来确定因果相对时序。通过将 SQLite 数据表抽象为由最后写入胜出映射(LWW-Map)构成的只增集合(G-Set),系统借助消息审计日志、墓碑机制与默克尔树实现了无冲突自动收敛。最后,他展示了生产环境中仅用 630 行代码且几无外部依赖的极简实现,呼吁开发者摒弃庞大臃肿的代码库,以极简工程哲学拥抱本地优先未来。 ## Atmosphere & style 演讲整体风格幽默犀利、务实而极具极客精神,James Long 凭借资深系统构建者的沉稳与松弛感,频频用梗图与大白话无情吐槽“手动处理冲突”等业界盲区,轻松化解了观众对分布式理论与学术黑话的畏难情绪。现场从痛陈弱网恶劣体验的现实困境,层层推进到剖析极简代码并实机断网演示数据无缝收敛,节奏紧凑明快,充满解构技术复杂度的爽快感。整场分享传递出一种返璞归真的工程力量,让听众不仅领略到本地优先架构的优雅潜力,更能深刻共情“简单是可靠性先决条件”的设计之美。 ## Bulletin - [00:00](https://www.youtube.com/watch?v=DEcwa68f-jY&t=0s) Web 应用依赖网络导致离线与弱网体验恶劣,本地优先(local-first)架构将代码与数据全部常驻本地,但其实质是分布式系统,必须解决乱序与数据冲突难题。 - [02:12](https://www.youtube.com/watch?v=DEcwa68f-jY&t=132s) Actual 记账应用通过在本地原生 SQLite 之上构筑轻量同步层,实现亚毫秒级读取并支持任意本地查询,规避了传统后端防范 SQL 注入与高危查询的权限限制。 - [09:39](https://www.youtube.com/watch?v=DEcwa68f-jY&t=579s) 基于混合逻辑时钟(HLC)与 CRDT 的组合,通过 256 行零依赖的 HLC 算法实现字典序因果排序,替代了不可靠的物理时钟与中心化全局序列号。 - [16:03](https://www.youtube.com/watch?v=DEcwa68f-jY&t=963s) 关系型数据库表可被建模为由 LWW-Map 构成的 G-Set,结合墓碑删除机制与 Merkle Tree 校验,Actual 在生产环境中仅用 630 行核心 JavaScript 代码即落地了高可靠同步层。 ## Key takeaways - [00:00](https://www.youtube.com/watch?v=DEcwa68f-jY&t=0s) 本地优先(Local-first)应用将全部代码与数据常驻客户端,天然获得极速响应和离线能力,但也意味着客户端进入了分布式系统架构。 - [00:00](https://www.youtube.com/watch?v=DEcwa68f-jY&t=0s) 简单的离线数组缓存上报方案在多端并发时完全失效,因网络延迟会导致事件乱序投递,直接覆盖写入会导致状态永久分歧。 - [02:12](https://www.youtube.com/watch?v=DEcwa68f-jY&t=132s) Actual 坚持采用本地 SQLite(5-10MB)作为存储引擎,保持亚毫秒级读取,同步引擎以叠加层形式运行而非强行替换数据库。 - [02:12](https://www.youtube.com/watch?v=DEcwa68f-jY&t=132s) 本地优先架构消除了 SQL 注入等云端安全顾虑,客户端可以安全地执行任意复杂的聚合与报表查询。 - [04:58](https://www.youtube.com/watch?v=DEcwa68f-jY&t=298s) 强一致性在离线场景下不可行,本地应用必须拥抱最终一致性,保证所有设备收到相同的乱序变更集后能收敛至确定结果。 - [07:25](https://www.youtube.com/watch?v=DEcwa68f-jY&t=445s) 单机物理时钟(如 Date.now())易受漂移影响,而全局递增序列号依赖中心节点,二者均不适用于离线因果排序。 - [09:39](https://www.youtube.com/watch?v=DEcwa68f-jY&t=579s) 混合逻辑时钟(HLC)融合物理时间与逻辑计数,生成的复合字符串可通过字典序直接比较,无需中心协调即可确定事件相对先后顺序。 - [11:23](https://www.youtube.com/watch?v=DEcwa68f-jY&t=683s) 手动编写冲突解决函数将分布式系统的复杂性转嫁给业务开发者,不仅极其脆弱,而且注定无法覆盖全部边缘场景。 - [11:23](https://www.youtube.com/watch?v=DEcwa68f-jY&t=683s) 工程化落地 CRDT 关键在于满足交换律(执行顺序无关)与幂等律(重复执行无副作用),从而获得对抗不可靠网络的容错能力。 - [13:54](https://www.youtube.com/watch?v=DEcwa68f-jY&t=834s) LWW-Map 通过比较字段级别的 HLC 时间戳保留最新值,成为表达具体实体字段状态的核心数据结构。 - [13:54](https://www.youtube.com/watch?v=DEcwa68f-jY&t=834s) 只增集合(G-Set)严禁物理删除元素,必须配合墓碑机制(Tombstones)标记逻辑删除,以保证后续到达的历史更新不丢失因果链条。 - [16:03](https://www.youtube.com/watch?v=DEcwa68f-jY&t=963s) SQLite 表可映射为由 LWW-Map 组成的 G-Set,通过 messages_crdt 日志表统一驱动本地操作与远程同步消息入库。 - [16:03](https://www.youtube.com/watch?v=DEcwa68f-jY&t=963s) 利用默克尔树(Merkle Tree)对时间戳哈希进行组织,节点无需全量拉取历史日志即可在毫秒级内比对出数据差异区间。 - [19:02](https://www.youtube.com/watch?v=DEcwa68f-jY&t=1142s) 在数据建模阶段精巧设计表结构与关系映射,往往能从根源上直接规避并发业务冲突的产生。 - [19:02](https://www.youtube.com/watch?v=DEcwa68f-jY&t=1142s) Actual 生产级客户端同步层仅 630 行纯 JavaScript 代码,服务端仅 132 行,仅依赖 uuid 与 murmurhash,证明了极简方案足以支撑复杂分布式同步。 ## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=DEcwa68f-jY&t=0s) 为什么“离线优先”应用没有普及与分布式系统的现实 演讲伊始,James Long 抛出了一个核心问题:为什么离线优先(offline-first)应用至今没有真正流行起来?Web 应用最大的痛点之一就是无法离线工作;即使处于联网状态,只要遇到糟糕的网络环境,整个应用的体验就会变得极其恶劣。从更高的视角审视,这其实是软件开发领域一个非常沉重的限制。如果从一开始就把离线场景纳入考量,最终的架构方向必然会演变为开发完全的本地应用(local app)——应用的所有代码和全部数据完全常驻在本地设备上。相比“离线优先”,James Long 更倾向于使用“本地优先(local-first)应用”这一概念。 然而,本地优先应用之所以难以普及,根本原因在于数据同步极度困难。一旦应用分布在不同设备之间,就必须面对跨设备同步数据的挑战,这绝非在离线时把变更暂存到数组、联网后再一并推送到服务器那么简单。许多声称支持离线的应用往往会在断网时弹出一个令人生畏的红色警告框,提示“正在尝试恢复连接,所做的更改可能无法保存”。James Long 吐槽道,这种提示与其模棱两可,不如干脆直接告诉用户数据不会被保存。 这一切的症结在于,本地应用本质上就是一个分布式系统。多台设备上的应用实例可以各自独立运行、修改数据,之后再合并同步。分布式系统本身就极难保证正确性,必须从架构上正视这一事实。 “The big problem with the web is that it does not work offline and even if you are online, if you're on a slow internet connection, your app feels terrible. That sucks.” —— James Long - **Web 应用的核心缺陷**:依赖恒定网络,断网完全不可用,弱网环境下响应迟缓。 - **本地优先(Local-first)的核心定义**:代码与数据 100% 运行并保存在本地客户端,启动即用。 - **离线数组队列方案的失效**:简单在客户端缓存变更数组并在连网时推送,无法解决多端乱序与冲突。 - **分布式系统现实**:多个客户端并行写入后再同步,天然属于分布式系统架构。 --- ### [02:12](https://www.youtube.com/watch?v=DEcwa68f-jY&t=132s) Actual 个人记账应用与本地 SQLite 架构 作为知名开源代码格式化工具 Prettier 的创建者,James Long 介绍了他近期的工作重点——Actual(一款个人记账应用,官网为 actualbudget.com)。Actual 被设计为完全的本地优先应用,同时支持跨设备的无缝数据同步。在立项之初,他对这款应用提出了几项核心诉求:离线可用、极致的运行速度、高度保护隐私,以及支持对数据执行任意查询。因为所有数据都在本地,极高的响应速度几乎不费吹灰之力就自然达成了。 关于任意查询能力,James Long 展示了一个正在开发但尚未正式发布的自定义报表功能。该功能采用类似 MongoDB 风格的语法,但在底层会直接编译成针对 SQLite 的本地查询语句。在传统的云端应用架构中,开发者绝对不敢让客户端直接向服务器提交任意代码或原始查询执行,这也是诸如 GraphQL 这类规范甚至不原生提供简单的 `SUM` 聚合函数的原因之一。但在本地应用中,由于数据仅归用户自己所有,用户哪怕“SQL 注入”自己也完全无所谓。 然而,记账应用必须配备移动端,以便用户在外出时随时记录交易。为了实现移动端与桌面端的数据同步,James Long 不得不暂停产品本身的开发,亲手从零构建了一套同步引擎。他在现场演示了两个客户端之间的实时同步:在一台客户端输入预算数值、合并或删除分类,同步到另一台桌面客户端后,两端迅速收敛到完全一致的状态。 在数据规模上,Actual 处理的是 5MB 到 10MB 左右的 SQLite 本地数据库,而非云端动辄 TB 级的后端数据库。James Long 明确表示,自己坚决不愿意放弃 SQLite,因为 SQLite 能够提供亚毫秒级(sub-millisecond)的读取速度,这也是应用极致流畅的关键。因此,这套同步机制必须作为附加层(layer on top)直接构筑在 SQLite 之上,而不是像市面上其他方案那样强迫用户更换数据库系统。 “I was not willing to give up SQLite; it gives me sub-millisecond read queries, which is absolutely amazing, it's the whole reason why the app is fast.” —— James Long ```mermaid flowchart TD accTitle: Actual's Local-First SQLite Architecture accDescr: Diagram showing how queries and the sync engine sit on top of the local SQLite database. subgraph ClientApp["本地优先客户端 (Actual)"] UI["用户界面 / 报表查询"] Engine["自定义同步引擎 (Sync Layer)"] SQLite[("本地 SQLite 数据库\n(5-10 MB, 亚毫秒读取)")] UI -->|"任意类 Mongo 查询\n(编译为 SQL)"| SQLite UI -->|"写入交易 / 预算变更"| Engine Engine -->|"读写与应用变更"| SQLite end subgraph Remote["同步网络"] OtherClient["其他设备 / 服务端中继"] end Engine <-->|"跨设备交换变更"| OtherClient ``` - **数据隐私与权限模型**:本地执行查询,彻底规避传统后端需要防范的 SQL 注入和高危查询问题。 - **本地存储规模**:单用户数据库规模通常在 5–10MB 之间,侧重轻量级客户端而非云端海量吞吐。 - **性能优势**:本地 SQLite 读取耗时小于 1 毫秒(sub-millisecond),UI 无网络等待开销。 - **设计原则**:坚持保留原生 SQLite,同步机制必须做成轻量叠加层,不依赖特定闭源或一体化数据库方案。 --- ### [04:58](https://www.youtube.com/watch?v=DEcwa68f-jY&t=298s) 同步的核心困境:乱序与最终一致性 跨设备同步之所以极其困难,本质上在于两大难题:**不可靠的时序(Unreliable Ordering)**与**数据冲突(Conflicts)**。作为一款本地应用,同步逻辑必须做到 100% 可靠,绝不能发生数据丢失或使本地状态陷入不可恢复的损坏——在本地应用中,用户可没办法简单地“刷新一下页面”来逃避错误。 以不可靠的时序为例:假设有两个客户端在各自的设备上修改同一个对象的属性。人们通常习惯将所有操作想象为发生在一条单一的线性时间轴上,期望事件按照绝对的先后顺序排开。但在分布式系统中,由于网络延迟和断网的存在,两台设备完全是独立演进的。当变更在网络中来回传播时,各个客户端接收到操作的先后顺序很可能是颠倒的。如果客户端在收到变更时直接盲目就地修改(mutate)本地数据,客户端 A 可能会按照 `A -> C -> D -> B` 的顺序应用,而客户端 B 则可能按照 `B -> A -> D -> C` 的顺序应用,两端最终的数据状态就会分道扬镳。 传统后端数据库往往采用“强一致性(Strong Consistency)”,这需要跨节点进行极其复杂的协调机制,甚至很多系统本身都很难完全做对。而现代分布式系统的演化趋势是拥抱“最终一致性(Eventual Consistency)”。最终一致性不再与网络物理规律对抗,而是主动承认并拥抱系统中存在多条并存的时间线。其核心诉求是:无论变更以何种乱序到达设备,只要所有客户端最终都接收到了相同的变更集,每个设备就必须能收敛并推导出完全一致的最终状态。 “A recent trend is to do eventual consistency, and this is a technique where you embrace the fact that there are multiple timelines, you embrace the fact that you are a distributed system, you admit that and then you find solutions that mesh well with that instead of trying to go against that.” —— James Long - **可靠性硬指标**:无网络刷新机制可用,同步层必须做到 100% 无数据丢失、无状态锁死。 - **单时间轴幻觉**:现实中没有全局统一的时间流动,无法依赖像量子纠缠般瞬间同步的状态。 - **盲目修改的恶果**:乱序接收变更如果直接执行状态覆盖,会导致不同设备最终状态永久分歧。 - **最终一致性定义**:只要所有节点见证过相同的无序变更集合,最终就能计算出相同的确定性结果。 --- ### [07:25](https://www.youtube.com/watch?v=DEcwa68f-jY&t=445s) 解决时序混乱:逻辑时钟与混合逻辑时钟(HLC) 要解决乱序问题,第一步就是给每一个数据变更分配时间戳。爱因斯坦曾指出时间是相对的,在分布式系统里同样如此:系统并不需要类似 JavaScript 的 `Date.now()` 这类绝对物理时间戳。现实中的物理时钟经常发生漂移、跳变或不同步,完全不可靠;系统真正需要的是一个能够反映因果先后次序的“相对顺序(relative order)”。 人们可能会联想到递增的全局序号(如 1, 2, 3, 4),但维护全局唯一递增序列必须依赖强一致性的中心化节点,这彻底违背了离线本地优先的原则。因此,系统必须能够在每个独立设备上分别生成有效的时间戳。这便需要引入专门的分布式时钟机制。 分布式领域常见的时钟有向量时钟(Vector Clock)以及**混合逻辑时钟(Hybrid Logical Clock, HLC)**。James Long 在 Actual 中所采用的正是混合逻辑时钟。HLC 具备非常优秀的工程特性:它运行在每个客户端设备本地,无需中心化服务器实时协调;并且 HLC 可以直接序列化为常规的文本字符串进行传输与存储。无论时钟内部结构如何复杂,对于同步引擎而言,HLC 的核心价值在于它具备足够的因果感知能力。通过比较两个 HLC 生成的时间戳,引擎可以明确裁决出某次变更是否晚于当前设备此前见过的所有其他变更,从而在没有全局调度中心的前提下,为分布在各端的事件赋予稳定的相对先后顺序。 “We don't need like a Date.now() timestamp, obviously there's clocks are horrible and we can't actually rely on Date.now(). What we want is just some order of events, so we just want some relative order.” —— James Long - **物理时钟失效**:设备本地的绝对时间戳(如 `Date.now()`)极易受到时钟漂移、手动修改系统时间影响,不可作为分布式仲裁依据。 - **全局序列号的缺陷**:依赖集中分配器,设备离线时无法分配编号,破坏本地优先原则。 - **混合逻辑时钟(HLC)**: - 结合了物理时钟与逻辑时钟的优点,部署于客户端本地。 - 支持直接序列化为标准字符串格式。 - 能够跨不同设备精确表达事件之间的相对因果顺序。 ### [09:39](https://www.youtube.com/watch?v=DEcwa68f-jY&t=579s) 混合逻辑时钟(HLC)与简单的力量 James Long 解释了时间戳在解决并发变更时的作用机制:如果采用最后写入胜出(Last-Write-Wins, LWW)策略,当两个修改同时提交时,时间戳更新的那一条变更(例如将 X 改为 3)便会胜出。他提醒大家不要被其外观迷惑,虽然这串标记看起来很像真实的日期格式,但它实际上采用了混合逻辑时钟(Hybrid Logical Clocks, HLC)算法。学术界对此有一整篇完整的论文进行论述,其核心机制在于生成一种可以做字典序大小比较的字符串——只要一个字符串小于另一个字符串,就代表其生成的时间戳排在前面。 ```mermaid flowchart LR accTitle: HLC String Comparison accDescr: 混合逻辑时钟生成包含物理时间与逻辑计数的字符串,通过字符串字典序直接确定先后顺序。 subgraph S1["本地生成"] A["物理时间 (Physical Time)"] B["逻辑计数 (Logical Counter)"] end subgraph S2["HLC 格式化"] C["复合时间戳字符串<br/>'2019-12-05T...-0001'"] end subgraph S3["全局比较"] D{"字符串大小比较<br/>StrA < StrB?"} E["判定发生顺序与胜出者"] end A --> C B --> C C --> D D --> E ``` 围绕分布式系统设计的哲学,James 引用了计算机科学家 Edsger W. Dijkstra 的名言:“Simplicity is a prerequisite for reliability.”(简单是可靠性的先决条件)。分布式系统与应用本身就是一个极其复杂的领域,但面对复杂问题并不必然要采用复杂的解决方案。在面对恶劣网络条件、或者用户把手机扔下两周后再拿起来同步大量复杂变更的极端场景下,要做到 100% 可靠,系统就必须保持极低的代码量。James 展示了 HLC 的完整实现代码,全篇只有 256 行纯 JavaScript,没有任何外部依赖。 - HLC 摆脱了完全依赖单机物理时钟带来的漂移问题,通过将物理时钟与逻辑计数结合,使时间比较退化为简单的字符串比较。 - 该 HLC 库保持了零依赖(zero dependencies),整个实现仅有 256 行 JavaScript 代码,一个周末就能完全吃透。 - 软件工程中常见的问题是开发者容易把事情搞复杂、承担过多不必要的范畴,而将其精简为单一核心问题能带来极致的稳定性。 ### [11:23](https://www.youtube.com/watch?v=DEcwa68f-jY&t=683s) 告别手动冲突解决:引入 CRDT 解决了变更的排序问题后,真正的难题落在了数据冲突上。两个设备完全可以在离线状态下修改同一份数据,随后重新上线同步。针对这种冲突,现有的许多框架给出的建议往往是“编写手动冲突解决代码”(manual conflict resolution)。James 对此表达了强烈的反对与嘲讽,借用梗图台词直接吐槽,并指出这种做法根本行不通。手动编写冲突解决逻辑,实质上是将分布式系统中最困难的包袱全甩给了普通业务开发者。 James 坦言自己根本写不出完美的手动冲突合并函数,任何认为自己聪明到能搞定所有边界情况的人都在自欺欺人。冲突处理绝不能是一个在数据同步完毕之后才去执行的“后处理步骤”(post-processing step),它必须在最初设计与组织数据结构时就被内化考虑。随后他引出了化解冲突的关键工具——CRDT(Conflict-free Replicated Data Types,无冲突复制数据类型)。为了缓解台下对学术黑话的恐惧,他还开玩笑用“范畴论里的偏序幺半群、包含最小上界(半格)”等高深数学词汇来逗弄观众,接着话锋一转,说明工程实践中真正需要掌握的 CRDT 核心概念其实只有两项数学性质: 1. **交换律(Commutative)**:应用变更的先后顺序不会影响最终结果。 2. **幂等律(Idempotent)**:同一条变更被重复应用任意多次,系统的最终状态保持不变。 关于为什么手动冲突处理注定失败,James Long 犀利地指出:“Dealing with conflicts is something you need to be thinking about while you are structuring and shaping your data; it's not a post-processing step.” - 传统基于合并函数(merge function)的方案在多设备复杂交叉修改时极易产生无法预料的边缘 Case 和数据丢失。 - 只要系统具备了交换律和幂等律,就等于获得了分布式环境下的“超能力”:客户端可以放心地把操作数据直接甩给网络,状态不对时哪怕重复重发数据包也不会导致逻辑损坏。 ### [13:54](https://www.youtube.com/watch?v=DEcwa68f-jY&t=834s) 生产级核心组件:LWW-Map 与 G-Set James 演示了一个最基础也是生产中最实用的 CRDT 实现——最后写入胜出映射(Last-Write-Wins Map,简称 LWW-Map)。假设系统接收一组针对对象字段的修改消息:先将 $X$ 设为 300,再将 $Y$ 设为 73,随后收到一条将 $X$ 改为 8 的旧消息。由于将 $X$ 改为 8 的消息所附带的 HLC 时间戳更老,该操作被判定无效并直接忽略。即便网络以完全相反的乱序投递这些消息(例如先收到 $X=8$,再收到 $Y=73$,最后收到 $X=300$),只要依据时间戳对比,最新时间戳的数据终究会覆盖旧数据,使得两端最终呈现出完全一致的对象状态 $\{X: 300, Y: 73, Z: 114\}$。 ```mermaid flowchart TD accTitle: LWW-Map Update Logic accDescr: 演示 LWW-Map 在收到字段更新消息时,如何依据 HLC 时间戳决定写入或丢弃。 subgraph Input["接收变更消息"] M["收到消息: set(column, value, timestamp)"] end subgraph Decision["冲突比较"] Cond{"消息 timestamp ><br/>当前单元格 timestamp?"} end subgraph Action["执行操作"] Write["写入新值并更新单元格时间戳<br/>(Apply Update)"] Ignore["忽略并丢弃该变更<br/>(Ignore Old Write)"] end Input --> Decision Decision -->|"大于 (Later)"| Write Decision -->|"小于或等于 (Earlier)"| Ignore ``` 为了构建真实可用的应用,除了表示单个实体属性的“映射(Map)”,还需要表示实体集合的“集合(Set)”。在 CRDT 中,最简单的集合模型是“只增集合”(Grow-only Set,简称 G-Set)。向 G-Set 中追加元素时,重复添加相同的 ID 不会产生任何副作用(满足幂等)。但 G-Set 存在一个根本约束:一旦加入,就绝不能从中真正物理删除任何元素。因为在分布式网络中,若一端删除了某条数据,另一端若随后传来了针对该实体的修改更新,已被删除的节点将无法正确处理这些变更。 - LWW-Map 是前端业务对象的理想载体(例如一条 Todo 事项的标题、完成状态等属性)。 - G-Set 构成了对象的集合管理逻辑,杜绝物理删除保证了跨设备同步时历史因果链条的完整。 - 结合 LWW-Map 与 G-Set,就足以覆盖大多数常规单机本地应用向分布式数据模型迁移的需求。 ### [16:03](https://www.youtube.com/watch?v=DEcwa68f-jY&t=963s) 用 SQLite 落地 CRDT:表结构设计与实机演示 将关系型数据库无缝转换为 CRDT 系统的方法出人意料地优雅:直接把 SQLite 数据表视为一个“由 LWW-Map 构成的 G-Set”。为了实现这套机制,James 在本地 SQLite 中引入了一张名为 `messages_crdt` 的日志表,记录该节点产生或接收到的所有同步消息。该表包含五个关键字段:`timestamp`(HLC 时间戳)、`dataset`(目标数据表名)、`row`(行数据 ID)、`column`(列字段名)以及 `value`(具体的更新值)。 ```mermaid flowchart LR accTitle: SQLite Table as G-Set of LWW-Maps accDescr: 消息流进入 messages_crdt 审计日志后,原子化映射为 SQLite 实际业务表的单元格写入。 subgraph Msg["消息层 (CRDT Messages)"] M1["timestamp: HLC<br/>dataset: 'todos'<br/>row: 'id-1'<br/>column: 'title'<br/>value: 'Buy Milk'"] end subgraph Storage["SQLite 本地存储层"] T1[("messages_crdt 消息表")] T2[("业务表: todos<br/>(G-Set of LWW-Maps)")] end Msg --> T1 T1 -->|"如果消息时间戳更新,则更新单元格"| T2 ``` 当一条消息到达时,系统只需像在表格中点选对应单元格一样,若时间戳比当前单元格的时间戳更新,便覆写其数值;如果该行的 ID 尚不存在,SQLite 会自动创建该行并填入对应列的值,让整张表随着消息的持续汇入而平滑生长。读取端仍然保留极速的原生 SQL 查询能力;写入端则抽象出 `update(table, id, fields)` 函数,本地更新与远程同步均走完全相同的消息管道。针对删除操作,James 采用了墓碑机制(Tombstones),通过 `delete(table, id)` 生成一条将实体的 `tombstone` 字段置为 1 的消息,物理记录永不抹除,业务读取时则直接通过 `WHERE tombstone = 0` 进行过滤。 在演讲尾声,James 还提到了利用默克尔树(Merkle Tree)组织所有历史时间戳哈希值,从而高效比对客户端之间数据一致性的设计,以及端到端加密(E2EE)在云端中继同步服务中的应用。在实机演示中,他断开本地网络并关闭服务端进程,在离线客户端 A 添加归属于新分类的条目,在客户端 B 上删除该分类并将引用重映射为“Personal”;当网络重连后,消息在两端自动回放并合并收敛,所有数据无缝对齐,验证了这套基于极简 CRDT 的本地优先架构的可用性。 - 数据同步架构完全对称:本地 UI 触发的写操作不是直接修改数据库,而是生成 CRDT 消息,与外来同步消息走完全一样的入库与广播流程。 - 墓碑机制完美兼顾了 G-Set “永不物理删除”的要求与应用层对“删除数据”的真实业务诉求。 - 借助 Merkle Tree,多端设备不需要全量拉取历史日志,便可在几毫秒内精确比对出彼此缺失的消息区间。 ### [19:02](https://www.youtube.com/watch?v=DEcwa68f-jY&t=1142s) 通过数据结构设计绕过冲突与极简的代码实现 在探讨冲突解决时,James Long 指出尽管时间有限无法深入所有细节技巧,但最聪明的做法往往是在设计之初就构思好数据结构,从而直接规避冲突。他介绍道,在自己的实现中,通过专门的数据表自动映射分类(Categories),并对数据结构进行精巧塑形,使得日常使用中常见的并发冲突从根本上就不可能发生。 为了证明基于 CRDT(无冲突复制数据类型)的 Local-first 同步层并非庞然大物,James 展示了极具冲击力的真实代码量统计:如果查看他开源的示例 GitHub 仓库,会发现客户端整个同步层加上底层数据库的实现仅有 250 行 JavaScript;而服务端代码更是只有 132 行,其职责极其纯粹,仅仅是接收消息并将消息原样转发广播。即使是在他研发的个人记账软件 Actual 实际生产环境中,包含完整同步机制的客户端代码也总共只有 630 行 JavaScript。 James 用幽默且形象的对比化解了开发者对分布式系统的畏难情绪。他调侃说,630 行代码相当于 65 条推特(Tweets)的字符量,以普通人周五躺在床上能发 20 条推特的频率计算,只要写上三个晚上的推特就能写出这套完整的同步系统。更重要的是,整个系统没有任何“虚胖”的隐藏包袱,唯一的外部依赖仅仅是 `uuid` 和 `murmurhash`。正如 Chris Ferdinandi(原演讲提及 Chris Harmon)前一天在大会上所警示的那样,这套架构并没有把垃圾塞进衣橱里,也不是表面看着代码少、底下却偷偷引入了 150MB 的依赖,而是货真价实的纯净代码。 - **GitHub 示例实现**:客户端同步层与数据库逻辑仅 250 行 JavaScript,服务端转发逻辑仅 132 行 JavaScript。 - **Actual 生产环境实现**:客户端完整同步层仅 630 行 JavaScript(相当于 65 条推特长度)。 - **外部依赖**:仅依赖 `uuid` 与 `murmurhash`,没有任何沉重的第三方库。 ```mermaid flowchart LR accTitle: 极简 Local-First 同步架构 accDescr: 展示了客户端与极简服务端之间仅靠消息接收与广播完成同步的高效轻量架构 subgraph ClientA ["客户端 A (630 行 JS)"] LocalDBA["本地数据库 / 状态"] SyncLayerA["CRDT 同步层 (HLC + 消息生成)"] LocalDBA <--> SyncLayerA end subgraph Server ["中央服务器 (132 行 JS)"] Relay["消息分发中心 (只接收并转发消息)"] end subgraph ClientB ["客户端 B (630 行 JS)"] SyncLayerB["CRDT 同步层 (HLC + 冲突合并)"] LocalDBB["本地数据库 / 状态"] SyncLayerB <--> LocalDBB end SyncLayerA -->|"推送变更消息"| Relay Relay -->|"广播消息"| SyncLayerB ``` ### [20:09](https://www.youtube.com/watch?v=DEcwa68f-jY&t=1209s) 呼吁拥抱 Local-first 与极简工程哲学 在演讲的结尾,James Long 再次重申了本地优先(Local-first)应用的核心价值。他坚定地认为,本地优先应用在响应速度、可靠性和离线可用性方面能够带来无与伦比的绝佳用户体验,并大力呼吁现场的开发者与前端社区重新审视并投入到这一方向的研究中。 James 总结强调,构建分布式协同与本地同步并不需要引入不可控的庞大框架或陷入深奥的学术泥潭。只要掌握了混合逻辑时钟(HLC)等轻量级算法与基础的 CRDT 理念,就能以极小的代码体积构建起坚如磐石的系统。在全场热烈的掌声中,他呼吁整个软件开发社区回归极简主义:“We've got to start simplifying our solutions and not take on so much code which makes things more complex.”(“我们必须开始简化我们的解决方案,不要再引入那么多只会让事情变得更加复杂的臃肿代码。”) ## Notable quotes > [11:23](https://www.youtube.com/watch?v=DEcwa68f-jY&t=683s) Dealing with conflicts is something you need to be thinking about while you are structuring and shaping your data; it's not a post-processing step. — James Long > [00:00](https://www.youtube.com/watch?v=DEcwa68f-jY&t=0s) The big problem with the web is that it does not work offline and even if you are online, if you're on a slow internet connection, your app feels terrible. That sucks. — James Long > [02:12](https://www.youtube.com/watch?v=DEcwa68f-jY&t=132s) I was not willing to give up SQLite; it gives me sub-millisecond read queries, which is absolutely amazing, it's the whole reason why the app is fast. — James Long ## Mentioned James Long, Edsger W. Dijkstra, Chris Ferdinandi, Prettier, Actual, SQLite, CRDT, Hybrid Logical Clock, LWW-Map, G-Set, Merkle Tree, MongoDB, GraphQL, uuid, murmurhash, Twitter ## Video description Filmed at https://2019.dotjs.io on December 5-6, 2019 in Paris. More talks on https://dotconferences.com/talks What do CRDTs and frontends have to do with each other? James talks about how CRDTs finally deliver on the promise of local-first apps, which provide superior user experience, and explains how simple CRDTs can be and how to leverage them to create robust local-first apps. [Source](https://www.youtube.com/watch?v=DEcwa68f-jY)

Source quotes

[11:23] James Long: Dealing with conflicts is something you need to be thinking about while you are structuring and shaping your data; it's not a post-processing step. [0:00] James Long: The big problem with the web is that it does not work offline and even if you are online, if you're on a slow internet connection, your app feels terrible. That sucks. [2:12] James Long: I was not willing to give up SQLite; it gives me sub-millisecond read queries, which is absolutely amazing, it's the whole reason why the app is fast.

Source quotes

[0:09] James Long: The first thing we need to do is we have to admit that local apps they are a distributed system there's no way around that. [11:23] James Long: Manual conflict resolution does not work; it's basically just issuing one of the hardest parts of this whole thing on to you, and as a developer, you are not gonna write correct manual conflict resolvers. [0:09] James Long: You cannot just queue up changes into an array when you are offline and then when you come back on online push them out to the server that does not work.

Original transcript

[0:00] yeah [0:00] [Applause] [0:03] [Music] [0:09] so I'm gonna start with a question [0:13] why haven't offline first apps taken off [0:16] the big problem with the web is that it [0:18] does not work offline and even if you [0:21] are online if you're on a slow internet [0:22] connection your app feels terrible that [0:26] sucks [0:27] take a step back that seems like a [0:29] really big limitation of writing apps so [0:33] there's this idea where you write apps [0:36] that are that work offline by taking [0:38] offline into consideration from the very [0:40] beginning and what where that really [0:42] leads to is basically just writing a [0:44] full local app so the entire apps code [0:47] and the entire and all your data is [0:50] completely local that's really what it [0:52] leads to you because to work on flying [0:53] and to boot it up offline you kind of [0:55] just have to do that so it's a complete [0:57] reaaahhr texture and personally I [0:59] actually like the term local first apps [1:01] better so the main problem why I think [1:04] they haven't taken off because syncing [1:05] is very very hard and if you're a full [1:09] local app you have to deal with syncing [1:11] where if you have these apps across [1:13] devices then you have to sync your data [1:15] across the devices and turns out this is [1:17] actually super super hard you cannot [1:19] just queue up changes into an array when [1:21] you are offline and then when you come [1:23] back on online push them out to the [1:25] server that does not work so a lot of [1:28] local apps they say that they have [1:30] offline support but you always end up [1:32] running into these situations you're [1:34] doing stuff offline and then suddenly [1:35] this big red scary box comes up and says [1:37] attempting to restore a connection [1:38] changes me now may not be saved I mean [1:42] come on why don't you just tell me they [1:43] won't be saved okay so let's take a step [1:50] back the first thing we need to do is we [1:52] have to admit that local apps they are a [1:55] distributed system there's no way around [1:57] that we have multiple Verte we have [2:00] multiple instances of your app on [2:01] different devices that they can go off [2:03] and do their thing and then they need to [2:05] come back and sync up that is a [2:06] distributed system and distributed [2:08] systems are very hard to get right so I [2:12] am James long I did I did create [2:14] prettier a lot of other people helped [2:16] push it to mainstream so I'm very [2:18] grateful for those these people are [2:20] recently I've been working on an app [2:21] called actual it's a personal finance [2:23] app you can go to actual budget comm if [2:25] you want to check it out this is a full [2:26] local app but it seamlessly syncs across [2:29] devices so when I started actual these [2:32] were my requirements these were the [2:33] features that I wanted were to really [2:35] have it had to be available offline and [2:37] it had to be fast turns out when all of [2:39] your data is local and it's just there [2:41] all the time you just end up getting a [2:44] super fast without much work focus on [2:46] privacy I was one of the ability to [2:48] provide arbitrary queries all of this [2:50] let led me to just build a local app [2:53] that felt way better than building a [2:55] normal web app so here's an example of [2:58] doing arbitrary queries this feature is [3:00] not actually released yet but if you [3:02] have a couple years or you know justjust [3:04] a little bit of your financial data you [3:05] can come in here and create a custom [3:06] report and it has like a MongoDB ish [3:09] style syntax that just compiles down to [3:11] a sequel like query I'm essentially [3:13] exposing a sequel Lite directly to you [3:15] you would never ever do this if you were [3:17] writing a cloud-based app you would [3:18] never imagine taking arbitrary code and [3:20] executing on executing it on your server [3:22] right this is reason why you don't do [3:24] that there's a reason why graph QL [3:25] doesn't even have a simple aggregate [3:26] function like some because all your data [3:29] is local sure you can see quite inject [3:31] yourself as much as you want whatever so [3:34] I realized though I need a mobile app [3:35] because you really do need to have your [3:37] transactions on the go so I was like [3:39] crap I need to figure out syncing so [3:42] this led me down a whole path of you [3:44] know building a sync engine pretty much [3:46] for better for worse I stopped on your [3:48] product and I built my own sync engine [3:50] but I did launch my product so at least [3:52] there's that so here's an example you [3:55] can fill in some budget values on one [3:56] client of course you can sync between [3:58] desktop apps to you so the second one [3:59] syncs and it got this budget values it [4:02] adds another one and then this one also [4:03] deletes a category and then when the [4:08] other one syncs up so you can merge [4:10] categories and do all this complicated [4:12] stuff the other one syncs up and it has [4:14] exactly the same state so he these were [4:18] my my use cases I have very simple data [4:21] we're talking about a five to ten [4:22] megabytes equal a database we're not [4:25] building a back-end database that has to [4:26] deal with a terabyte of data this is a [4:28] whole different world also I had to have [4:31] syncing on top of sequel Lite I was not [4:33] willing to switch [4:34] databases so if you have to if you [4:36] wanted to use a couple of the other [4:38] solutions out there they require you to [4:39] just trust them to take your data I did [4:42] not want to give up sequel I it gives me [4:43] sub sub-millisecond read queries which [4:47] is absolutely amazing it's a whole [4:48] reason why the app is fast so I was not [4:49] willing to give up sequel Lite this [4:51] thinking has to be a layer on top of it [4:53] to this day I still understand why [4:56] everything is so bundled together okay [4:58] so why is thinking so hard there are two [5:00] main problems unreliable ordering and [5:03] conflicts whatever we do here whatever [5:05] we do to solve this it has to work a [5:08] hundred percent of the time this has to [5:10] be seamless there can not be never know [5:12] no data loss or no state of the app that [5:15] gets into a case where it doesn't work [5:17] because remember this is a local lab you [5:19] can't just refresh the tab I'm accepting [5:21] the responsibility that this is going to [5:22] work on a percent of the time so let's [5:25] talk about unreliable ordering so say [5:28] you have two devices or two clients and [5:30] they do changes over time let's just say [5:35] that they are you know making setting [5:38] properties of an object we want to think [5:40] about this as if it's one timeline right [5:42] that there's a sequential order of [5:44] events the problem is though that we are [5:46] distributed we have two apps that are [5:48] doing two four things at different times [5:50] and when they try to sync up they are [5:52] going to receive the changes at [5:53] different times so B does not get a's [5:56] changes directly when they happen it's [5:58] not like quantum computing or something [5:59] like that and so as the changes are [6:01] propagated synced back and forth between [6:04] the devices it's gonna get them in [6:07] different order and so we can't just [6:08] naively mutate our data as we are seeing [6:11] changes otherwise the first the first [6:14] client would would apply a C D and B if [6:18] you can read that and then the second [6:19] client would apply B ad and C so [6:21] obviously we can't do out of order [6:22] mutations because the resulting state is [6:24] going to be different so back-end apps [6:29] or back in databases they do they have [6:31] this thing called strong consistency and [6:33] this requires a lot of coordination and [6:35] it's actually really complex and a lot [6:36] of them actually don't actually get it [6:38] right a recent trend is to do eventual [6:40] consistency and this is a technique [6:42] where you embrace the fact that there [6:44] are multiple timelines you embrace the [6:46] fact that you are a distributed system [6:48] you admit that and then you find [6:49] solutions that mesh well with that [6:51] instead of trying to go against that so [6:54] the idea here is is there a way to where [6:58] even if we get the changes in in [7:00] different order is there a way that we [7:02] can still produce the state the same [7:04] state on each device so this is the [7:07] problem if we can solve this and we have [7:08] eventual consistency as long as every [7:11] single client has seen the changes the [7:15] same changes even that even if they're [7:18] out of order then they will have the [7:19] same state so that is our goal that is [7:22] what we want to achieve so how do we [7:25] solve unreliable ordering and we need to [7:31] assign timestamps this is the first [7:33] thing that that we that we need to do to [7:36] do this we can go back to Einstein time [7:38] is relative it's only net worth depends [7:40] on upon what we do as it is passing so [7:43] we don't need like a date now timestamp [7:46] obviously there's a clock so horrible [7:48] and we can't actually rely on data now [7:50] what we want is just some order of [7:52] events so we just want some relative [7:55] order where when a change happens here [7:57] what changes has that device already [7:59] seeing that's what we really want so you [8:01] could think of you know if it's just a [8:02] suit like a sequence ID one two three [8:04] four but we obviously can't do this [8:05] because this would rely on some sort of [8:07] global sequence ID and requires strong [8:10] consistency and we we just can't do that [8:13] we need a we need a way to do this per [8:15] per device so to do that you need a [8:18] clock and you need a special kind of [8:20] clock so there's a couple different [8:22] types of clocks like a vector clock [8:24] fortunately I don't unfortunately I [8:27] don't have time to actually explain how [8:28] these clocks work but there's a vector [8:30] clock there's another kind of clock [8:31] called a hybrid logical clock which is a [8:33] Chelsea this is the kind of clock that I [8:35] use it's a super interesting clock and [8:37] what these clocks do is they exist per [8:39] device this is not something that exists [8:41] on some local or like on some [8:43] centralized server that everybody tries [8:45] to coordinate with these are per device [8:47] clocks [8:47] what they do is they generate time [8:49] stamps that we can assign to each change [8:53] so for example this is what a Chelsea is [8:55] look like a Chelsea s are super cool [8:57] because it can be see realized so just a [8:58] normal string again this the times that [9:00] can be any value the [9:02] clock is actually like a vector of like [9:04] multiple entries and stuff like that [9:06] all that we care about is when you [9:07] assign when you assign a timestamp to it [9:10] change the clock is smart enough to give [9:13] us us being the ephemeral like whoever [9:17] is trying to sync some data so that we [9:19] can compare changes and say did this [9:21] change when it happened on this machine [9:23] did it come after all of these other [9:25] things that the machine has already seen [9:26] right so it's just a relative ordering [9:29] so this is an example there's two [9:31] changes set X to three has a timestamp [9:33] set X to five set X set X to 3 has a [9:36] later time stamp so the HLC provided [9:39] this timestamp for us and so if we were [9:41] doing like a last-minute wins then [9:42] setting X - 3 would win in this case if [9:45] you were applying both these changes so [9:47] don't don't get tripped up by the fact [9:48] that it looks like were you actually [9:49] using like a real date like you see a [9:52] real dating here hyper logical clocks [9:54] there's a whole paper written about the [9:55] algorithm it's super interesting and I [9:58] don't have time to fully explain it [9:59] right now but just trust that we have [10:01] this string that we can say is the [10:02] string less than this other string then [10:05] that's the time stamp it came before [10:06] that string and that's what HLC is [10:10] enable you to do now Dykstra said [10:13] simplicity is a prerequisite for for [10:16] reliability this is a complex problem [10:19] just distributed apps and distribute [10:21] systems is a complex problem and the way [10:23] to have it reliable is to have a simple [10:26] solution complex problems do not [10:28] necessarily beget complex solutions we [10:31] want this to be super reliable 100% [10:34] reliable in the face of terrible [10:36] networks in the face of you putting your [10:38] phone down for two weeks picking it back [10:40] up and then it seems to all these [10:41] complicated changes right it has to work [10:43] 1% of the time for this to happen we [10:45] have to have the least amount of code [10:47] possible and that is what is so good [10:49] about hybrid logical clocks this is the [10:52] entire implementation of harbor logical [10:53] clocks zero dependencies here it's 256 [10:57] lines of lines of lines and JavaScript [11:00] right how cool is that I mean it seems [11:03] like you could sit down and learn that [11:04] in like a weekend right I feel like with [11:07] a lot of times as developers we over [11:11] complicate things we try to take on too [11:12] much of the problem let's try to distill [11:15] things down into a single [11:16] problem and solve that in 256 lines of [11:19] JavaScript with no dependencies because [11:20] dependencies suck all right so we've [11:23] solved C we've solved sort of solve the [11:25] ordering problem so what about conflicts [11:26] there's nothing around the fact that you [11:29] two devices can go offline set the same [11:31] piece of data and then come back off and [11:33] then come back online so we haven't [11:34] magically solved that somehow well what [11:39] do existing solutions do they say well [11:41] you got a right manual conflict [11:42] resolution code right and the only [11:44] response to that my opinion is you know [11:46] did you just happen to go screw myself I [11:47] mean I believe I did Bob because really [11:50] may no convict resolution does not work [11:52] it's basically just issuing one of the [11:54] hardest parts of this whole thing on to [11:56] you and as a developer you are not gonna [11:58] write correct manual conflict resolvers [12:01] I'm not going to and I think I'm smart [12:04] there's just too hard there's way too [12:06] many edge cases to resolve conflicts and [12:09] conflicts dealing with conflicts it's [12:11] something you need to be thinking about [12:12] while you are structuring and shaping [12:14] your data [12:15] it's not a post-processing step it's not [12:17] a post step that after everything seems [12:20] up and then you resolve the conflicts so [12:23] the question is how do we resolve [12:23] conflicts then there is an answer to [12:26] this this magical thing called CRD T's [12:29] okay okay I know what you're thinking [12:31] we're not gonna get into any math we're [12:33] not gonna do any complex stuff it's [12:36] really not as hard as it seems all it is [12:38] is a partially ordered Mahanoy D and the [12:40] category vender functors oh with at [12:42] least with at least upper bound so it's [12:44] a semi lattice essentially no but really [12:48] seriously 3d T's I'm just gonna pick out [12:50] the important parts for you the parts [12:52] that you need to build production apps [12:53] it's actually only a little bit of all [12:55] of that theory so C or D T stands for [12:58] conflict free replicated data types you [13:01] may if you're familiar with this world [13:03] you may have seen all of these terms [13:05] these are just implementations of CEO [13:07] duties so C R DT is just more of a broad [13:10] term [13:11] there's no canonical implementation of [13:12] them all that it is you don't have to [13:14] worry about these at all all that they [13:16] are are data structures that have [13:18] certain properties to properties to be [13:20] exact what is that they're commutative [13:23] which means the order doesn't matter in [13:25] which you apply the changes the second [13:27] is that they're idempotent which means [13:29] it doesn't matter [13:29] many times you apply that change think [13:32] about that for a second if it doesn't [13:34] matter what order you apply changes and [13:36] doesn't matter how many times you apply [13:37] that change you can essentially just [13:38] throw changes over the wall and if this [13:41] state is not what you think it should be [13:42] then you just throw some more changes [13:45] I mean it's essentially a superpower [13:46] right super reliable in the face of a [13:49] crappy Network or a distributed system [13:51] so let's just go through and look at [13:54] what it would be to implement a C or D T [13:57] let's say that we have this set of [13:59] changes X X set X to 300 and so we fill [14:04] out the prop so we're just going to fill [14:05] out this this object with with with [14:07] values as we apply these messages or [14:10] these changes so it's set X to 300 set Y [14:13] to 73 set X to 8 but wait setting X 8 [14:16] didn't do anything and that's because [14:18] the timestamp is older right so that x [14:20] thing the timestamp is a key part of [14:22] this because that's what enables this [14:23] commutative and idempotent properties of [14:26] these production-ready CR DT so I mean [14:29] you could do CRT T's in all sorts of [14:30] ways but these are the ones that all you [14:32] need to build production apps and then [14:34] we assign Z to 114 so this is the [14:36] resulting in state x y&z with these [14:39] numbers we could do this in any order so [14:41] set X to eight set Y to 73 so here X [14:44] does equal eight but it's because it [14:46] hasn't seen this other message yet so [14:48] set X to 300 that timestamp is later and [14:50] so now it actually does apply that [14:52] message congratulations you just [14:55] implemented your first theory DT this is [14:57] the last right winds map this is [14:59] basically just a set of messages that [15:00] when you apply them through and get this [15:02] object out you you have a last write [15:05] winds map this is now distributed you [15:07] could sync these changes across devices [15:10] so you have a map which is a basic [15:13] building block for building a an app [15:16] right let's just replace that map with [15:18] an L W map the only other thing you [15:20] really need is a set so a map is just [15:22] like an item like a to-do item and a set [15:25] is a collection of items right so those [15:27] are kind of the building blocks of [15:28] relapse for a set we can replace it with [15:31] what's called a grow only set a G set so [15:35] in example that would be you have a [15:36] bunch of messages there are two [15:38] duplicate IDs here so adding the same ID [15:40] to the same set it doesn't do anything [15:41] and the result is this set [15:43] so no it's aggro only set you can never [15:45] remove something from a set so when [15:47] something is distributed [15:48] you can never safely remove anything [15:50] right because you might get changes that [15:52] actually change that object but if [15:54] you've already actually removed it from [15:55] your local data then that's a problem so [15:57] you just never remove it okay so this is [16:01] a G set okay so how do I make basic [16:03] relational data into CRD keys we have [16:05] everything that we need to solve this so [16:08] remember I have this sequel Lite [16:10] database that I want to turn that I want [16:12] to treat as CEO DT is how do i implement [16:14] this well the answer is I can treat a [16:17] sequel Lite table as a G set of lww Maps [16:20] and so to implement this I have just one [16:23] new table in my sequel I'd database it's [16:26] called the messages ERD T table and this [16:29] basically just saved all of the messages [16:31] that I have ever seen whether I [16:34] generated them myself or I got them from [16:35] other devices it has a timestamp it has [16:38] a data set which is the table that it [16:40] applies to has a row which is the item [16:41] ID has a column and then and then the [16:44] value so as these messages are trickling [16:46] in it just think of it as like selecting [16:49] a cell in the sequel light table and [16:51] putting a value right there [16:53] if the timestamp is greater than [16:55] whatever value was there before that's [16:58] it that's all I do and I've built my [17:00] entire app on that note it's important [17:03] to note that if the item does not exist [17:04] yet like if there's no row for that ID [17:06] it just creates it and then it puts that [17:08] one value in that field so it just sort [17:10] of trickles down gradually expands and [17:13] I've built my entire app on this so how [17:17] does actually look like while [17:18] programming so I have a function so I [17:21] can do raw sequel queries to read my [17:24] data right that's the important part [17:25] that's what I really wanted in the first [17:27] place I can have super fast read queries [17:29] but to change the data it's a little [17:30] different I have a couple functions like [17:32] update which just takes the table the ID [17:35] and then some fields and it just [17:36] generates the messages to push through [17:38] the system so to change my local data [17:40] it's exactly the same way as syncing [17:42] when I get messages from other people it [17:44] syncs it through it pushes it through [17:46] the syncing layer when I changed up [17:48] myself I just call update generates the [17:50] messages and it pushes it through the [17:51] second layer it's all the exact same [17:53] thing so how do you delete stuff will [17:55] have a delete function which takes [17:56] table and NID and this generates a [17:59] message which changes the tombstone [18:01] field so it can never remove something [18:03] from this set everything just has a [18:04] tombstone field and I just set that [18:06] value to 1 and then I just ignore those [18:08] whenever I'm reading from them so other [18:12] features but I don't have time to time [18:13] to talk about you can ensure consistency [18:15] with a Merkel tree Merkel tree is a tree [18:16] of hashes that represents all the time [18:18] stands that time stamps that have been [18:20] applied that gives us something to [18:21] compare across clients you can do [18:24] end-to-end encryption here so I really [18:25] like I can host this like a Bennett like [18:27] a like a singing server so just a very [18:30] short quick demo I built this demo app [18:32] you can see that like I'm offline I've [18:35] killed a server I can add stuff and I'm [18:37] gonna add an item with a different [18:39] category and then and then I'm gonna [18:42] delete that category on the other client [18:44] so what's gonna happen here it's gonna [18:45] sink that date that category it's gonna [18:48] sink that item with a different category [18:49] so what should that first client have [18:52] well I've mapped that category onto [18:54] personal so once I've seen it a couple [18:56] of times it eventually catches up and [18:58] everything maps to personal so you you [19:00] when you're structuring your data I [19:02] can't go into all of the techniques [19:04] we're doing this but you think about [19:05] conflicts so that you just bypass them [19:08] altogether and that there doesn't exist [19:10] a conflict that I have a table that [19:12] map's the the categories automatically [19:15] and I shaped my data so that common [19:17] conflicts can't even ever occur so [19:19] that's sort of the additional layer [19:20] again super simple this is the [19:22] client-side implementation of the entire [19:24] syncing layer and all of the database [19:26] 250 lines JavaScript so for all of this [19:28] if you go to my sample get github repo [19:31] you can see the entire implementation of [19:33] all of this [19:34] 132 lines of JavaScript on a server it [19:36] just gets messages sends them back [19:38] the client is 630 lines of JavaScript [19:41] this is pretty much all of the code that [19:43] I use in actual to build the entire [19:44] syncing layer and I've had really no [19:46] problems with it it's 65 tweets how long [19:49] does it take you to tweet 65 times [19:51] Friday in bed tweet like 20 times so [19:54] it's like three nights so the only [19:56] dependency is that it has our UUID and [19:58] murmur hash right you're not I'm not [20:00] shoving garbage into the closet and then [20:03] it's actually you're pulling in like a [20:04] 150 megabyte dependency like Chris [20:06] Harmon said yesterday this is the real [20:08] code [20:09] okay so local apps have a very very [20:12] superior user experience and I really [20:13] want to encourage people to look into [20:15] this more and anybody who's working on [20:17] this I really encourage you to look into [20:18] CRT T's and sends simple methods to [20:22] implement clocks we've got to start [20:24] simplifying our solutions and not take [20:26] on so much code which come which come [20:29] like makes things more complex thank you [20:34] [Applause] [20:38] [Music]