peritext
Permazen
Our great sponsors
peritext | Permazen | |
---|---|---|
20 | 10 | |
615 | 397 | |
2.6% | 0.8% | |
0.0 | 9.2 | |
over 1 year ago | 4 days ago | |
TypeScript | HTML | |
MIT License | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
peritext
-
Cola: A text CRDT for real-time collaborative editing
This doesn’t appear to support rich text formatting ranges like bold, italic, etc - unless I’m missing something in the API. AFAIK Peritext is still the state of the art in rich text CRDT algorithms https://www.inkandswitch.com/peritext/
I’d love to see this build the rich text stuff from the Peritext algorithm.
-
The Cloud Is a Prison. Can the Local-First Software Movement Set Us Free?
The work Ink & Switch (unaffiliated) do has been an inspiration to my with regard to local-first and decentralized software: https://www.inkandswitch.com
They have a quasi-manifesto on local-first (https://www.inkandswitch.com/local-first/) and have published the best rich text CRDT around, Peritext: https://www.inkandswitch.com/peritext/
Lots of interesting work happening in this space.
-
Figma Is a File Editor
Take a look at https://automerge.org/ and the stack those folks are building. You're exactly right that it's a difficult balance (specifically the trick is proving commutativity for the domain-specific data of your application). But automerge (and then https://github.com/inkandswitch/peritext) show it's at least possible. Good stuff.
-
Ask HN: What is new in Algorithms / Data Structures these days?
Yes - The BFT problem only matters when you have Byzantine actors. But I think users deserve and expect the system to be reasonably well behaved and predictable in all situations. Anything publically writable, for example, needs BFT resilience. Or any video game.
As for the prosemirror problem, I assume you’re talking about weird merges from users putting markdown in a text crdt? You’re totally right - this is a problem. Text CRDTs treat documents as a simple sequence of characters. And that confuses a lot of structured formats. For example, if two users concurrently bold the same word, the system should see that users agree that it should be bolded. But if that “bold” intent is translated into “insert double asterisks here and here”, you end up with 4 asterisks before and after the text, and that confused markdown parsers. The problem is that a text crdt doesn’t understand markdown.
JSON editing has similar problems. I’ve heard of plenty of people over the years putting json text into a text crdt, only to find that when concurrent edits happen, the json grows parse errors. Eg if two users concurrently insert “a” and “b” into an empty list. The result is [“a””b”] which can’t be parsed.
The answer to both of these problems is to use CRDTs which understand the shape of your data structure. Eg, use a json OT/crdt system for json data (like sharedb or automerge). Likewise, if the user is editing rich text in prosemirror then you want a rich text crdt like peritext. Rich text CRDTs add the concept of annotations - so if two users bold overlapping regions of text, the crdt understands that the result should be that the entire region is bolded. And that can be translated back to markdown if you want.
The ink & switch people did a great write up of how this sort of crdt works here: https://www.inkandswitch.com/peritext/
- Edge cases in collaborative rich text editing (2021)
-
You might not need a CRDT
> I'm looking out for practical CRDT ideas that works well with richtext.
Have you seen Peritext from Ink & Switch? https://www.inkandswitch.com/peritext/ It's relatively new, but is a CRDT aimed at rich text!
-
CRDTs make multiplayer text editing part of Zed's DNA
To put it in a different perspective, plain text editing has well-solved CRDT patterns. But, semantic data-structures like rich-text or syntax trees is what's tricky and has unsolved challenges.
Peritext[1] is the only one that came close to solving rich-text, but even that one left out important aspect of rich-text editing like handling list & table operations as "work to be done later".
For people interested on why it's difficult to build CRDTs for richtext, here's a piece I wrote a year back: https://writer.zohopublic.com/writer/published/grcwy5c699d67...
Related HN discussion: https://news.ycombinator.com/item?id=29433896
[1] https://github.com/inkandswitch/peritext
- Peritext – A CRDT for Rich-Text Collaboration
-
Evan Wallace CRDT Algorithms
Anyone unsure of what a CRDT is, this is the perfect intro: https://www.inkandswitch.com/peritext/
The two most widely used CRDT implementations (combining JSON like general purpose types and rich text editing types) are:
- Automerge https://github.com/automerge/automerge
- Yjs https://github.com/yjs/yjs
-
Is Svelte capable of a Google Docs & Sheets clone?
Svelte is, but that is your smallest problem. You want to look into CRDTs (conflict-free replicated data types) to offer true (offline) collaboration. A popular JS library to solve this complex problem is called [automerge](Conflict-free replicated data type). A rather recent development in that area specifically for text-based content is Peritext. Also check out this interactive tutorial about CRDTs.
Permazen
-
ORMs are nice but they are the wrong abstraction
The most interesting/fresh approach I've seen to this problem is Permazen.
https://github.com/permazen/permazen/
It starts by asking what the most natural way is to integrate persistence with a programming language (Java in this case, but the concepts are generic), and then goes ahead and implements the features of an RDBMS as an in-process library that can be given different storage backends as long as they implement a sorted K/V store. So it can sit on top of a simple in-process file based K/V store, RocksDB, FoundationDB, or any SQL database like PostgreSQL, SQLite, Spanner, etc (it just uses the RDBMS to store sorted key/value pairs in that case).
Essentially it's a way to map object graphs to key/value pairs but with the usual features you'd want like indexing, validation, transactions, and so on. The design is really nice and can scale from tiny tasks you'd normally use JSON or object serialization for, all the way up to large distributed clusters.
Because the native object model is mapped directly to storage there's no object/relational mismatch.
-
Permazen: Language-natural persistence to KV stores
Ok, let's change to that from https://permazen.io/ above.
Usually we go the other way and prefer the project page, but there's clearly not enough info there.
- How FoundationDB works and why it works
-
Figma Is a File Editor
You can use a scalable database that gives you serializable transactions whilst not requiring you to represent your document in the relational model.
A good example of this architecture would be using FoundationDB [1] with Permazen [2]. In this design there are three layers:
1. A horizontally scaling sorted transactional K/V store. This is provided by FoundationDB. Transactions are automatically ordered within the cluster.
2. A network protocol that can serialize database transactions. Permazen has the ability to do this, you can do things like cache reads, HTTP POST transactions and so on. Stuff you can't easily do with SQL databases.
3. A way to map in-memory objects to/from key/value pairs, with schema migration, indexing and other DB-like features. Permazen also does this.
Permazen can be thought of as an ORM for KV stores. It's an in-memory library intended to execute on trusted servers (because the KV store can't do any business logic validation). However, for something like Figma where it's basically trusting the client anyway that doesn't matter. Additionally you can do some tricks with the architecture to support untrusted clients; I've explored these topics with Archie (the Permazen designer) in the past.
The nice thing about this design is that it doesn't require sharding by "file", can scale to large numbers of simultaneous co-authors, and results in a very natural coding model. However, Permazen is a Java library. To use it from a browser would be awkward. That said it has fairly minimal reliance on the JDK. You could probably auto-convert it to Kotlin and then use Kotlin/JS or Kotlin/WASM. But frankly it'd be easier to do that architecture as a real desktop app where you aren't boxed in by the browser's limitations.
The writeup mentions a couple of reasons for not using a database:
1. Relational/object mismatch. Permazen+FDB solves this.
2. Cost of a database vs S3. This is mostly an artifact of cloud pricing. Cloud is highly profitable but most of the margin comes from managed databases and other very high level services, not commodity byte storage. Given that FDB is free you could eliminate the cost gap by just running the database yourself, and especially, running it on your own metal.
Because Permazen has a pluggable KV backend and because there are backends that write to files, you can have both worlds - a scalable DB in the cloud and also write to files for individual cases where people don't want to store data on your backend.
https://www.foundationdb.org/ [1]
https://permazen.io/ [2]
-
FoundationDB: A Distributed Key-Value Store
You can do online schema changes with FDB, it all depends on what you do with the FDB primitives.
A great example of how to best utilize FDB is Permazen [1], described well in its white paper [2].
Permazen is a Java library, so it can be utilized from any JVM language e.g. via Truffle you get Python, JavaScript, Ruby, WASM + any bytecode language. It supports any sorted K/V backend so you can build and test locally with a simple disk or in memory impl, or RocksDB, or even a regular SQL database. Then you can point it at FoundationDB later when you're ready for scaling.
Permazen is not a SQL implementation. Instead it's "language integrated" meaning you write queries using the Java collections library and some helpers, in particular, NavigableSet and NavigableMap. In effect you write and hard code your query plans. However, for this you get many of the same features an RDBMS would have and then some more, for example you get indexes, indexes with compound keys, strongly typed and enforced schemas with ONLINE updates, strong type safety during schema changes (which are allowed to be arbitrary), sophisticated transaction support, tight control over caching and transactional "copy out", constraints and the equivalent of foreign key constraints with better validation semantics than what JPA or SQL gives you, you can define any custom data derivation function for new kinds of "index", a CLI for ad-hoc querying, and a GUI for exploration of the data.
Oh yes, it also has a Raft implementation, so if you want multi-cluster FDB with Raft-driven failover you could do that too (iirc, FDB doesn't have this out of the box).
FDB has something a bit like this in its Record layer, but it's nowhere near as powerful or well thought out. Permazen is obscure and not widely used, but it's been deployed to production as part of a large US 911 dispatching system and is maintained.
Incremental schema evolution is possible because Permazen stores schema data in the K/V store, along with a version for each persisted object (row), and upgrades objects on the fly when they're first accessed.
[1] https://permazen.io/
[2] https://cdn.jsdelivr.net/gh/permazen/permazen@master/permaze...
- Warp: Lightweight Multi-Key Transactions for Key-Value Stores
-
Persism 1.0.1 released - A zero ceremony ORM for Java
Compare to https://github.com/permazen/permazen ?
-
Introducing Weightless, an extremely easy to use database mapping library for Java
Did you see https://github.com/permazen/permazen - it's in the same space
What are some alternatives?
automerge - A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.
Doma 2 - DAO oriented database mapping framework for Java 8+
y-crdt - Rust port of Yjs
ObjectiveSql - Writing SQL using Java syntax
dokieli - :bulb: dokieli is a clientside editor for decentralised article publishing, annotations and social interactions
Persism - A zero ceremony ORM for Java
threlte - 3D framework for Svelte
hyhac - A HyperDex Haskell Client
automerge-rs - Rust implementation of automerge [Moved to: https://github.com/automerge/automerge]
moditect - Tooling for the Java Module System
yjs - Shared data types for building collaborative software
QueryStream - Build JPA Criteria queries using a Stream-like API