eliasdejong

standby, server is taking some load. should be back up soon

Creator here,

For those interested:

- ZERO CLIENT-SIDE OR INLINE JAVASCRIPT except Datastar & Datastar attributes

- real-time multiplayer powered by CQRS

- 45x45 characters chunks stored in LMDB

- all characters are read & written through FULL ACID TRANSACTIONS. no shortcuts. no relaxations

- chunk-based viewport culling

- LZ4 compression on chunk-basis to remove white space and repeating chars

- runs on a 5,52 euro/mo VPS in Germany, cheapest tier in public cloud

Stack: Datastar, Python/FastAPI, LMDB

check info tab on the top

Read your blogpost, I will need a code editor soon so I might have a stab at hacking something together.

but this doesn’t really work in mobile and it messes with the selection

I haven't tested it personally, but on the OverType they claim "excellect mobile support".

CodeMirror is great, but still requires a lot of clientside JavaScript. I wonder if it would be possible to create a code editor in the same style OverType[0], where the editor is basically just an HTML textarea. You would need 70% less JavaScript code to do exactly the same thing, and it supports syntax highlighting out of the box[1].

[0] https://github.com/panphora/overtype

[1] https://github.com/panphora/overtype/pull/35

Checkout DataStar, it's also a hypermedia web framework but it subsumes the functionality of htmx, is faster, more efficient and fits inside 11 KiB. It uses SSE + brotli streaming compression to achieve compression ratios up to 4000x. It makes the web client completely stateless. Building a webapp cannoy be simpler really.

To me this sentiment is silly. Programming was never about the act of writing, but about making the computer do something. Now we can ask computers to helps us write instructions for them. Great if you ask me. And no, your job is not going away because human maintainers will always be required to review changes, communicate with stakeholders and provide a vision for the projects. I have yet to see a chatbot that can REDUCE entropy inside a codebases rather than continuously increase it with more and more slop.

Very cool project! Being able to replay history is huge and makes it possible to look back in time without having to make full copies of the database. This is something that is very much lacking in many SQL systems where you need 'temporal tables' to achieve the same effect, but those are really limited as they have to be setup specifically and often duplicate data unnecessarily. If you are interested in this topic, I suggest you study Datomic and the EAVT data model. This is likely where database architecture in the future will be headed.

The database is stored in memory. So it must be small enough to fit in RAM, and the full journal has to be replayed from scratch when opening a file.

For larger datasets, you really want disk support. Using something like SQLite or DuckDB as an append-only store is another way to achieve this effect.

Also lack of a proper query language will be a problem for long term serious use. A simple hand-rolled program API can only get you so far, until you need more advanced querying.

Unlike XML or JSON, joedb is a binary file format that does not require any parsing. So, joedb files are much smaller, and processing data is much faster.

Some time ago I created a JSON-compatible serialization format that is zero-copy (no parsing required): https://github.com/fastserial/lite3

It doesn't do transactions or history versioning, but it is also very fast in memory. Something like jq or JSONPath on a disk-file version of this format could be interesting.

Performance of Protobuf is a joke. Why not use a zero copy format so that serialization is free? For example, my format Lite³ which outperforms Google Flatbuffers by 242x: https://github.com/fastserial/lite3

See also, RUM Conjecture: https://www.codementor.io/@arpitbhayani/the-rum-conjecture-1...

Conceptually similar to CAP, but with storage trade-offs. The idea is you can only pick 2 out of 3.

Really excellent research and well written, congrats. Shows that io_uring really brings extra performance when properly used, and not simply as a drop-in replacement.

With IOPOLL, completion events are polled directly from the NVMe device queue, either by the application or by the kernel SQPOLL thread (cf. Section 2), replacing interrupt-based signaling. This removes interrupt setup and handling overhead but disables non-polled I/O, such as sockets, within the same ring.

Treating io_uring as a drop-in replacement in a traditional I/O-worker design is inadequate. Instead, io_uring requires a ring-per-thread design that overlaps computation and I/O within the same thread.

1) So does this mean that if you want to take advantage of IOPOLL, you should use two rings per thread: one for network and one for storage?

2) SQPoll is shown in the graph as outperforming IOPoll. I assume both polling options are mutually exclusive?

3) I'd be interested in what the considerations are (if any) for using IOPoll over SQPoll.

4) Additional question: I assume for a modern DBMS you would want to run this as thread-per core?

The library contains iterator functions that can be used to recursively traverse a message from the root and discover the entire structure. Then every value can be checked for defined constraints appropriately while at the same time validating the traversal paths. Also a schema description format is needed, perhaps something like JSONSchema can be used.

Doing this by definition requires processing an entire message which can be a little slow, so it is best done in C and exposed through CPython bindings / CFFI.

Imagine if you measured the speed of beer delivery by the rate at which beer cans can be packed/unpacked from truck pallets. But then somebody shows up with a tanker truck and starts pumping beer directly in and out. You might argue this is 'unfair' because the tanker is not doing any packing or unpacking. But then you realize it was never about packing speed in the first place. It was about delivering beer.

The primary motivations were performance requirements and frustration with schema formats.

The ability to mutate serialized data allows for 2 things:

1) Services exchanging messages and making small changes each time e.g. adding a timestamp without full reserialization overhead.

2) A message producer can keep a message 'template' ready and only change the necessary fields each time before sending. As a result, serializing becomes practically free from a performance perspective.

No, I have not benchmarked yet against other languages. Rkyv is Rust only.

One primary difference is that Rkyv does not support in-place mutation. So any modification of a message requires full reserialization, unlike Lite³.

A key feature of this code is that it skips CPU cache when copying

Are those numbers also measured while skipping the CPU cache?

Yes, any zero-copy format in general will have this advantage because reading a value is essentially just a pointer dereference. Most of the message data can be completely ignored, so the CPU never needs to see it. Only the actual data accessed counts towards the limit.

Btw: in my project README I have benchmarks against Cap'N Proto & Google Flatbuffers.

If the new value is equal size or smaller, it will overwrite the old value in-place. If it is larger, then the new value is appended to the buffer and the index structure is updated to point to the new location.

In the case of append, the old value still lives inside the buffer but is zeroed out. This means that if you keep replacing variable-sized elements, over time the buffer will fragment. You can vacuum a message by recursively writing it from the root to a new buffer. This will clear out the unused space. This operation can be delayed for as long as you like.

If you are only setting fixed-size values like integers or floats, then the buffer never grows as they are always updated in-place.

The limit is the number of outstanding cache line requests to the memory controller. CPUs have a fixed number of slots for this, around 10-12 usually. Intel calls them LFBs (Line Fill Buffers) and AMD MSHRs (Miss Status Holding Registers). When the slots are filled, the CPU can issue no more requests and has to wait for them to complete. Apple M chips (probably) have more slots and the memory is physically packaged together with the CPU, so they get better numbers.

Being schemaless is deliberate design decision as it eliminates the need for managing and building schema files. By not requiring schema, messages are always readable to arbitrary consumers.

If you want schema, it must be done by the application through runtime type checking. All messages contain type information. Though I do see the value of adding pydantic-like schema checking in the future.

EDIT: Regarding message size, Lite³ does demand a message size penalty for being schemaless and fully indexed at the same time. Though if you are using it in an RPC / streaming setting, this can be negated through brotli/zstd/dict compression.

14 GB/s

Yes, those numbers are real but only in very short bursts of strictly sequential reads, sustained speeds will be closer to 8-10 GB/s. And real workloads will be lower than that, because they contain random access.

Most NVMe drivers on Linux actually DMA the pages directly into host memory over the PCIe link, so it is not actually the CPU that is moving the data. Whenever the CPU is involved in any data movement, the 6 GB/s per core limit still applies.

Increasingly the performance limit for modern CPUs is the amount of data you can feed through a single core: basically memcpy() speed. On most x86 cores the limit is around 6 GB/s and about 20 GB/s for Apple M chips.

When you see advertised numbers like '200 GB/s' that is total memory bandwidth, or all cores combined. For individual cores, the limit will still be around 6 GB/s.

This means even if you write a perfect parser, you cannot go faster. This limit also applies to (de)serializing data like JSON and Protobuf, because those formats must typically be fully parsed before a single field can be read.

If however you use a zero-copy format, the CPU can skip data that it doesn't care about, so you can 'exceed' the 6 GB/s limit.

The Lite³ serialization format I am working on aims to exploit exactly this, and is able to outperform simdjson by 120x in some benchmarks as a result: https://github.com/fastserial/lite3

Yes, language ports are being worked on :)

You will be able to access the same data in different languages using APIs specific to your language.

Right now someone has already made a (private) Go port. And Rust is also in the works.

Hi, you are right in calling out the Postgres example in the context of DBs/MVCC. The purpose of JSONB is to be an indexable representation of JSON inside a Postgres database. It is not trying to be a standalone format for external interchange and therefore it is fulfilling very different requirements.

A serialization format does not care about versioning or rollbacks. It is simply trying to organize data such that it can be sent over a network. If updates can be made in-place without requiring re-serialization, then that is always a benefit.

Write amplification is still a fact however that I think deserves to be mentioned. To tackle this problem in the context of DBs/MVCC, you would have to use techniques other than in-place mutation like you mention: overlay/COW. Basically, LMDB-style.

And yes I think databases is where this technology will eventually have the greatest potential, so that is where I am also looking.

(author here)

The documentation page is out of date, the format now resolves collisions through quadratic probing.

Author here,

First of all, hello Hacker News :)

Many of the comments seem to address the design of key hashing. The reason for using hashed keys inside B-tree nodes instead of the string keys directly is threefold:

1) The implementation is simplified.

2) When performing a lookup, it is faster to compare fixed-sized elements than it is to do variable length string comparison.

3) The key length is unlimited.

I should say the documentation page is out of date regarding hash collisions. The format now supports probing thanks to a PR merged yesterday. So inserting colliding keys will actually work.

It is true that databases and other formats do store string keys directly in the nodes. However as a memory format, runtime performance is very important. There is no disk or IO latency to 'hide behind'.

Right now the hash function used is DJB2. It has the interesting property of somewhat preserving the lexicographical ordering of the key names. So hashes for keys like "item_0001", "item_0002" and "item_0003" are actually more likely to also be placed sequentially inside the B-tree nodes. This can be useful when doing a sequential scan on the semantic key names, otherwise you are doing a lot more random access. Also DJB2 is so simple that it can be calculated entirely by the C preprocessor at compile time, so you are not actually paying the runtime cost of hashing.

We will be doing a lot more testing before DJB2 is finalized in the spec, but might later end up with a 'better' hash function such as XXH32.

Finally, TRON/Lite³ compared to other binary JSON formats (BSON, MsgPack, CBOR, Amazon Ion) is different in that:

1) none of the formats mentioned provide direct zero-copy indexed access to the data

2) none of the formats mentioned allow for partial mutation of the data without rewriting most of the document

This last point 2) is especially significant. For example, JSONB in Postgres is immutable. When replacing or inserting one specific value inside an object or array, with JSONB you will rewrite the entire document as a result of this, even if it is several megabytes large. If you are performing frequent updates inside JSONB documents, this will cause severe write amplification. This is the case for all current Postgres versions.

TRON/Lite³ is designed to blur the line between memory and serialization format.

When overwriting fixed-sized values like integers or floats, the old value can simply be overwritten. Holes are only left if the overriding values do not fit in the old location (strings, byte arrays).

To clean up unused space, you start an iterator at the root of the document and recursively write to a new buffer. This will clean up all the unused space. This operation can be delayed by the application for as long as they wish, until the size trade-off outweighs the cost of rebuilding.

Lite³: a binary format encoding JSON documents as a serialized B-tree, making it possible to construct iterators on them directly and query internal fields at indexed speeds. It is still a serialized document (possible to send over a network), though now you don't need to do any parsing, since the document itself is already indexed.

https://github.com/fastserial/lite3

In general jq maps very well to any hierarchical datastructure. One of the maintainers has made 'fq' which supports BSON, MsgPack, Protobuf, CBOR and even media files png, jpg, mp4 etc.

SQLite when compiled for size is 590 kB. But I think a full jq database implementation based on Lite³ would be possible under 100 kB.

Lock-free shared state relies on algorithms that can make clever use of atomic instructions. But you should not have threads write to the same memory regions, because the hardware only allows for 1 core to have a cacheline in a writeable state. If another core attempts a write to the same line, this will immediately invalidate all the other copies. Under high contention the coherency penalty becomes so large that throughput falls through the floor. So basically the algorithms need to do most of the work in separate memory regions, then occasionally coordinate by 'committing' their work via a spinlock or similar.

Lite³ implements some settings for node alignment, but not for user data. It would be possible to create a bytes type with extra alignment guarantees.

The main difference between Lite³ and JSONB is that JSONB is not a standalone portable format, and therefore is not suitable for external interchange. Its purpose is to be an indexable representation of JSON inside a Postgres database. But sending it as standalone messages to arbitrary consumers does not really make sense. JSONB can only be interpreted in a Postgres context. This is different from for example BSON, which can be read and constructed as a standalone format without Mongo.

Another difference is that JSONB is immutable. Suppose you need to replace one specific value inside an object or array. With JSONB, you would rewrite the entire JSONB document as a result of this, even if it is several megabytes large. If you are performing frequent updates inside JSONB documents, this will cause severe write amplification. Despite the fact that offsets are grouped in chunks of 32, Postgres still rewrites the entire document. This is the case for all current Postgres versions.

On the other hand, Lite³ supports replacing of individual values where ONLY the changed value needs updating. For this to work, you need separate offsets. Postgres makes a tradeoff where they get some benefits in size, but as a result become completely read-only. This is the case in general for most types of compression.

Also JSONB is not suited to storing binary data. The user must use a separate bytea column. Lite³ directly implements a native bytes type.

JSONB was designed to sacrifice mutability in favor of read performance, but despite this, I still expect Lite³ to exceed it at read performance. Of course it is hard to back this up without benchmarks, but there are several reasons:

1) JSONB performs runtime string comparison loops to find keys. Lite³ uses fixed-size hash digests comparisons, where the hashes are computed at compile time.

2) JSONB must do 'walking back' because of the 32-grouped offset scheme.

3) Lite³ has none of the database overhead.

Again, the two formats serve a different purpose, but comparing just the raw byte layouts.