What's the difference between a KV store and a filesystem? (should those really be different APIs?)

[makoConstruct]

A filesystem maps names to arbitrary data. The data tends to support things like fast appends and partial reads but it's not clear why a good KV store shouldn't support those things as well.

The names in a filesystem are often "tree structured", but this is mostly just achieved by having a designated separator character in file path names (/). When I have used KV stores, I often ended up doing a similar thing.

A KV store allows any data as keys with no restrictions, but it's not clear that a filesystem shouldn't, and platform-specific implementations of a filesystem scheme could use an escaping scheme to provide that.

Filesystems also do things with permissioning and relative paths and aliasing/shortcuts, which I've never seen in a KV store, but integrating them wouldn't be difficult.

If there is a difference between a filesystem and a KV store, should there be?

[Mossaka]

I think the differences are in the implementation details. In general, a filesystem can be considered to be a key-value store, but not vice-versa. This is because a key-value store can be optimized for small key-value pair operations and taking advantage of the disk blocks. For example, multiple key-value pairs can be written to the same disk block.

Another difference is that many key-value stores have indexes and stores key-value pairs sorted in disk. This means that retriving a sequence of key value pairs is more efficient compared to a filesystem.

[makoConstruct]

For example, multiple key-value pairs can be written to the same disk block.

I'd thought that good filesystems did that, but apparently this was dropped by ext and ext4 never does it.

So we've identified an implementation difference, two different ways of storing things or indexing things.

This doesn't quite convince me that these things should be accessed with a separate APIs, it still seems like there's a very natural supertype that they share.

In practice, KV stores all exist within filesystems, and of course in linux a virtual filesystem could be mounted that is actually being managed by a KV store.

It kind of seems to me that maybe there should only be filesystems, and some of the nodes in the filesystem would maintain indexes on their child nodes by reacting to modification alerts (hooking up to FS events like that is totally a thing you can do in linux filesystems btw, and the need to index one's files is common), and store their contents in more compact ways, and other nodes have different policies that're more optimized around slightly larger values and different ways of reading and writing.

(I remind the project that WASI may end up essentially laying the foundational APIs of a new cross-platform computing environment, you should be willing to think a lot of assumptions over from scratch. Taking an uncommonly broad view of what a filesystem can be would be a good idea.)

[danbugs]

This is an interesting discussion~ It's important that we think about concepts and not just mirror infrastructure. Of course, filesystems and key-value stores have grown completely separate and that has yielded different APIs and implementations, BUUUT... Intrinsically, we are talking about simply naming data (i.e., something like a "store" superset (?))

In a perfect world, these could be the same thing, but, right now, as they aren't, combining them could result in tons of effort to make implementations work in the first place. HOWEVER, I feel like this could simply be addressed by having different interfaces inside the overall thing (e.g., similar to how wasi:kv/data/bulk-get and wasi:kv/data/bulk-put (#2) are different interfaces because not every kv implements both).

[devigned]

I'm also concerned about the transactional semantics of something like bulk-put. I believe there is an implicit promise in bulk-put that would imply some level of transactional behavior that may be greater than what would be offered by an FS.

[sunfishcode]

(I remind the project that WASI may end up essentially laying the foundational APIs of a new cross-platform computing environment, you should be willing to think a lot of assumptions over from scratch. Taking an uncommonly broad view of what a filesystem can be would be a good idea.)

Rethinking assumptions from scratch has turned out to lead many folks away from using filesystem APIs in this space. As @devigned points out, traditional filesystem APIs don't have any concept of transactions. Also, filesystem APIs come with a wide variety of baggage and limitations, such as saying that you can't have / in key names. And, filesystem APIs don't have KV-store features like time-to-live or atomic-increment. And filesystems do have a lot of their own features, like the ability to open the same file in multiple places and communicate through reads and writes to the file, that don't make sense for many KV stores.

There are ways we can work around all these limitations, but they all have tradeoffs. They make the API less efficient, less convenient, less featureful, or less robust. Some users will be ok with these tradoffs, but others won't want this effectively foreign abstraction layer sitting between them and their KV store.

This is where @lukewagner's Virtual Platform Layering concept can help. Instead of saying that the filesystem API is the fundamental thing that all KV store use cases use, we can give KV stores their own API specialized for the needs of users that know they're talking to a KV store. We could then define filesystem-API-compatible adapters for use cases where we want to use a KV store like a filesystem, or implement a KV store on top of a filesystem. The adapters would likely come with some tradeoffs and limitations, but in a sense, those would be the inherent costs of using filesystem APIs. Users can then chose whether they wish to pay these costs, in exchange for filesystem API compatibility.

[sunfishcode]

One additional observation: if we look at the underlying things that could be broadly modeled as files, eg. serial ports, kv store entries, sockets, PCM audio devices, or other things, a particularly interesting intersection for all those use cases is the ability to read and write streams of data. And the Wit typesystem is planned to have built in stream types, for this very purpose.

Stream types aren't implemented in wit-bindgen yet, but when they arrive, wasi-kv-store here will be able to define an API that hands out a stream for reading from a KV store, or accepts a stream for writing to one. That way, people could write libraries that operate on streams, which could be used with the KV store API, or any other API that uses streams.

[Mossaka]

Closing this issue due to inactivity