5 ms·

Faster: Fast persistent recoverable log and key-value store

94 points by LAC-Tech 3y ago

withinboredom 3y ago
FASTER is awesome! I just wish the C version was as feature complete as the C# version. I know how to use FFI to call C stuff, but I have no idea how to call C# stuff. It's the only reason I haven't used it in real life.
- neonsunset 3y ago
  You could, in theory, export certain methods with [UnmanagedCallersOnly] and AOT* compile it - those become plain C exports. Alternatively, you can host .NET runtime within C++ process and call arbitrary methods from the loaded assemblies. Or you could not deal with all that and just use C# :) (which comes with an advantage of not using something worse) * - I don't know if it uses anything requiring JIT but likely no or limited to certain features.
  - withinboredom 3y ago
    I’ve specifically gone hunting for this documentation and never found it. Thanks for the tip! I love C#, but I’ve been in PHP/Go land for awhile now. PHP is an interesting language, I’d have never thought I’d like it as much as I do. It’d also be cool to see a Go implementation, but there’s also cgo.
    - neonsunset 3y ago
      :( But on occasion you go the first route, the docs are here: - https://learn.microsoft.com/en-us/dotnet/core/deploying/native-aot/interop#native-exports https://learn.microsoft.com/en-us/dotnet/core/deploying/nati... +adjacent sections - https://learn.microsoft.com/en-us/dotnet/api/system.runtime.interopservices.unmanagedcallersonlyattribute https://learn.microsoft.com/en-us/dotnet/api/system.runtime.... This pretty much comes down to writing glue exports the way you would do in Rust and then 'dotnet publish'ing it as .dll/.so (you could also produce .lib/.a for static linking but it is trickier). Overall, I feel like the ungodly amount of projects of this kind (albeit of lower complexity) written in Go (which is a weaker platform) could have benefitted from using C# instead - it has zero-cost abstractions through struct generics like Rust and allows expressing complex data structures in a terser way.
      - withinboredom 3y ago
        I think a lot of what go has going for it is in static compilation. Things just work. The C# community leans a lot further from open source (paid libraries vs. free).
        neonsunset 3y ago
        Go receives so much unjustified good will it is almost unbelievable... Either way, if you do look at current state of .NET ecosystem, you may get surprised. But I guess, such is the perception of the public that may have read a bit too much into Go's promises (it would have abysmal performance should FASTER have been written in Go) - C#, seen as less popular weird Java, is now an underdog after all (look at Github LOC statistics).
        withinboredom 3y ago
        > Go receives so much unjustified good will it is almost unbelievable... Yes. Yes it does and it really is annoying. I can't tell if it is the language or just people not deeply understand the abstractions it provides because it doesn't use sane defaults (or the defaults are geared towards high-throughput, google scale nonsense). I help out a lot on FrankenPHP, and lately I've been digging into a weird bug, deep in Go, that causes FIN_ACK packets to get delayed by hundreds and hundreds of ms. There are so many layers of abstractions (nearly 100) to dig through. I know for a fact in the C# there are less than 10 to the CLR, then after you can rule out the language, you are just tracing IR. But no, I'm digging through hand-written asm, hunting for a bug or at least figure out how to report it with enough information that it doesn't sound like "my email can't be sent more than 500 miles" (google that one btw).
        apgwoz 3y ago
        > I've been digging into a weird bug, deep in Go, that causes FIN_ACK packets to get delayed by hundreds and hundreds of ms. Just going to put it out there: have you considered the problem might actually be [Nagle’s Algorithm](https://en.wikipedia.org/wiki/Nagle's_algorithm) https://en.wikipedia.org/wiki/Nagle's_algorithm)? This algorithm is the source of 10s of thousands of hours of wasted debugging time of “weird bugs related to latency of networking.” Even the “greats” have wasted time debugging something that ended up being “I forgot about Nagle.”
- LAC-Tech 3y ago
  Which one have you used, the kv store or log? Reason I submitted this because I'm curious about peoples real world experience.
  - withinboredom 3y ago
    I was looking to use both. Actually. I discovered FASTER when looking to port durable functions to php (it’s called durable-php if you want to google it, though the implementation is nothing like it) and the netherite engine uses faster. It’s perfect for my use-case, more so now than when I originally researched it as a possibility. Back then, I didn’t even have threading solved for php. Now that’s all a solved problem (threads ftw) and I’m refactoring log storage now to better support things like faster.
    - adamretter 3y ago
      Have you considered Meta's RocksDB as an option?
      - withinboredom 3y ago
        I wrote a time-traveling database (where you can query a table/row as of a specific point in time and join it to data at another point in time; we used this for AI training to predict future behavior in users) completely from scratch (that was the coolest work project ever, btw) that was built on Hadoop/Hbase. I understand RocksDB is fairly similar ... however, I want to stay as far away from any of those kinds of APIs. I have scars from dealing with hbase and writing query planners and figuring out how to do performant joins in a white-room type environment. No. Thank. You. It was fun at the time, but I don't want to go near it ever again.
        apgwoz 3y ago
        [RocksDB](https://rocksdb.org/ https://rocksdb.org/) isn’t a distributed storage system, fwiw. It’s an embedded KV engine similar to LevelDB, LMDB, or really sqlite (though that’s full SQL, not just KV)
zokier 3y ago
Is this actually used anywhere by MS? Or is it just random research project (MSR?)
- withinboredom 3y ago
  Durable Functions uses it in Netherite, which is how I originally discovered this library.
- LAC-Tech 3y ago
  I'm curious about that too, appareantly it was created for their SimpleStore research project. https://www.microsoft.com/en-us/research/project/simplestore/ https://www.microsoft.com/en-us/research/project/simplestore...
Retr0id 3y ago
I think I know what they're getting at, but "can quickly saturate disk bandwidth" doesn't exactly sound like a selling point, on its own!
- lomereiter 3y ago
  Reminds me of a Russian joke. A secretary applies for a job; the interviewer asks her: "In your CV you claim that you can type 1000 characters per minute - for real?!" "Yes!", she replies, then adds in a low voice: "but such nonsense comes out..."
- ww520 3y ago
  SSD have very good bandwidth, in excessive of 10 GB/s. The bottleneck is often at the CPU. For a 10Ghz CPU, it can spend 1 cycle to process 1 byte. That’s the scale we’re at now. https://www.tomshardware.com/features/ssd-benchmarks-hierarchy https://www.tomshardware.com/features/ssd-benchmarks-hierarc...
- klysm 3y ago
  How is that not a selling point? You want the disk to be the bottleneck
  - cout 3y ago
    Not necessarily. For example, an uncompressed log will saturate disk more easily than a compressed log but if compression is fast enough the compressed log will write more data in the same amount of time. A more complex case: a column store might write in batches. Later an insert in the middle might require the entire batch to be read from disk and then rewritten. This makes queries faster later on but at the cost of more disk io up front. In this case disk bandwidth is also saturated but write performance might be worse than an append-only log that does not optimize at all for reads/queries.
    - klysm 3y ago
      Those are good points. Perhaps a better way to phrase it is you want the system to be able to utilize as much disk bandwidth as you give it.
avinassh 3y ago
How does this compare with RocksDB? Also, are there any performance benchmarks?
- emills 3y ago
  There’s a paper that does some benchmarking against other options here: https://www.microsoft.com/en-us/research/uploads/prod/2018/03/faster-sigmod18.pdf https://www.microsoft.com/en-us/research/uploads/prod/2018/0...
- welder 3y ago
  Looks like it's exponentially faster than RocksDB, but in most use cases the bottleneck would be the network and available sockets on the machine running FASTER. Unless you're doing high throughput embedded data ingestion. Maybe Neuralink could use this.
- ww520 3y ago
  RocksDB supports point query and range query. This only supports point query. Also I'm not sure whether FASTER supports transaction, as the paper didn't mention it.
  - yencabulator 3y ago
    My notes from 2018 say FASTER has no multi-key transactions.
CyberDildonics 3y ago
I wish people would push back against using a generic adjective as a name. Naming something "Faster" is just trying to get someone to remember by being intentionally confusing.
- hacknews20 3y ago
  What! Nonsense.
  - CyberDildonics 3y ago
    Well you do make a compelling argument.
bravura 3y ago
Are there Python bindings? I couldn't find any.
DenisM 3y ago
How does it compare to FoundationDB? Nether the paper nor the GitHub page mentioned it.
- _bohm 3y ago
  It would be a bit of an apples-to-oranges comparison. FoundationDB is a distributed KV database that supports range queries. FASTER is an embedded KV store that only supports point lookups. The use cases for each are rather different.
siliconc0w 3y ago
I really like the idea of tiering a log device such that you go from memory -> nvme -> object storage. You get some nice properties like fast low latency commit times from NVMe, read your own local writes (usually good enough), but have most of your cold data on cheaper durable object storage with some intelligence to pull down/warm up pages when you suspect you'll need them. It'd be nice if this had a more language-agnostic frontend like gRPC or something.
dang 3y ago
Related: Faster A fast concurrent persistent key-value store and log, in C# and C++ - https://news.ycombinator.com/item?id=25741670 https://news.ycombinator.com/item?id=25741670 - Jan 2021 (8 comments) Faster – Fast key-value store from Microsoft Research - https://news.ycombinator.com/item?id=17785002 https://news.ycombinator.com/item?id=17785002 - Aug 2018 (76 comments) Faster – A key-value store for large state management - https://news.ycombinator.com/item?id=17267403 https://news.ycombinator.com/item?id=17267403 - June 2018 (34 comments)
nimchimpsky 3y ago
[dead]

94 points by LAC-Tech 3y ago

FASTER is awesome! I just wish the C version was as feature complete as the C# version. I know how to use FFI to call C stuff, but I have no idea how to call C# stuff. It's the only reason I haven't used it in real life.

neonsunset 3y ago
You could, in theory, export certain methods with [UnmanagedCallersOnly] and AOT* compile it - those become plain C exports. Alternatively, you can host .NET runtime within C++ process and call arbitrary methods from the loaded assemblies. Or you could not deal with all that and just use C# :) (which comes with an advantage of not using something worse) * - I don't know if it uses anything requiring JIT but likely no or limited to certain features.
- withinboredom 3y ago
  I’ve specifically gone hunting for this documentation and never found it. Thanks for the tip! I love C#, but I’ve been in PHP/Go land for awhile now. PHP is an interesting language, I’d have never thought I’d like it as much as I do. It’d also be cool to see a Go implementation, but there’s also cgo.
  - neonsunset 3y ago
    :( But on occasion you go the first route, the docs are here: - https://learn.microsoft.com/en-us/dotnet/core/deploying/native-aot/interop#native-exports https://learn.microsoft.com/en-us/dotnet/core/deploying/nati... +adjacent sections - https://learn.microsoft.com/en-us/dotnet/api/system.runtime.interopservices.unmanagedcallersonlyattribute https://learn.microsoft.com/en-us/dotnet/api/system.runtime.... This pretty much comes down to writing glue exports the way you would do in Rust and then 'dotnet publish'ing it as .dll/.so (you could also produce .lib/.a for static linking but it is trickier). Overall, I feel like the ungodly amount of projects of this kind (albeit of lower complexity) written in Go (which is a weaker platform) could have benefitted from using C# instead - it has zero-cost abstractions through struct generics like Rust and allows expressing complex data structures in a terser way.
    - withinboredom 3y ago
      I think a lot of what go has going for it is in static compilation. Things just work. The C# community leans a lot further from open source (paid libraries vs. free).
      - neonsunset 3y ago
        Go receives so much unjustified good will it is almost unbelievable... Either way, if you do look at current state of .NET ecosystem, you may get surprised. But I guess, such is the perception of the public that may have read a bit too much into Go's promises (it would have abysmal performance should FASTER have been written in Go) - C#, seen as less popular weird Java, is now an underdog after all (look at Github LOC statistics).
        withinboredom 3y ago
        > Go receives so much unjustified good will it is almost unbelievable... Yes. Yes it does and it really is annoying. I can't tell if it is the language or just people not deeply understand the abstractions it provides because it doesn't use sane defaults (or the defaults are geared towards high-throughput, google scale nonsense). I help out a lot on FrankenPHP, and lately I've been digging into a weird bug, deep in Go, that causes FIN_ACK packets to get delayed by hundreds and hundreds of ms. There are so many layers of abstractions (nearly 100) to dig through. I know for a fact in the C# there are less than 10 to the CLR, then after you can rule out the language, you are just tracing IR. But no, I'm digging through hand-written asm, hunting for a bug or at least figure out how to report it with enough information that it doesn't sound like "my email can't be sent more than 500 miles" (google that one btw).
        apgwoz 3y ago
        > I've been digging into a weird bug, deep in Go, that causes FIN_ACK packets to get delayed by hundreds and hundreds of ms. Just going to put it out there: have you considered the problem might actually be [Nagle’s Algorithm](https://en.wikipedia.org/wiki/Nagle's_algorithm) https://en.wikipedia.org/wiki/Nagle's_algorithm)? This algorithm is the source of 10s of thousands of hours of wasted debugging time of “weird bugs related to latency of networking.” Even the “greats” have wasted time debugging something that ended up being “I forgot about Nagle.”
LAC-Tech 3y ago
Which one have you used, the kv store or log? Reason I submitted this because I'm curious about peoples real world experience.
- withinboredom 3y ago
  I was looking to use both. Actually. I discovered FASTER when looking to port durable functions to php (it’s called durable-php if you want to google it, though the implementation is nothing like it) and the netherite engine uses faster. It’s perfect for my use-case, more so now than when I originally researched it as a possibility. Back then, I didn’t even have threading solved for php. Now that’s all a solved problem (threads ftw) and I’m refactoring log storage now to better support things like faster.
  - adamretter 3y ago
    Have you considered Meta's RocksDB as an option?
    - withinboredom 3y ago
      I wrote a time-traveling database (where you can query a table/row as of a specific point in time and join it to data at another point in time; we used this for AI training to predict future behavior in users) completely from scratch (that was the coolest work project ever, btw) that was built on Hadoop/Hbase. I understand RocksDB is fairly similar ... however, I want to stay as far away from any of those kinds of APIs. I have scars from dealing with hbase and writing query planners and figuring out how to do performant joins in a white-room type environment. No. Thank. You. It was fun at the time, but I don't want to go near it ever again.
      - apgwoz 3y ago
        [RocksDB](https://rocksdb.org/ https://rocksdb.org/) isn’t a distributed storage system, fwiw. It’s an embedded KV engine similar to LevelDB, LMDB, or really sqlite (though that’s full SQL, not just KV)

zokier 3y ago

Is this actually used anywhere by MS? Or is it just random research project (MSR?)

withinboredom 3y ago
Durable Functions uses it in Netherite, which is how I originally discovered this library.
LAC-Tech 3y ago
I'm curious about that too, appareantly it was created for their SimpleStore research project. https://www.microsoft.com/en-us/research/project/simplestore/ https://www.microsoft.com/en-us/research/project/simplestore...

Retr0id 3y ago

I think I know what they're getting at, but "can quickly saturate disk bandwidth" doesn't exactly sound like a selling point, on its own!

lomereiter 3y ago
Reminds me of a Russian joke. A secretary applies for a job; the interviewer asks her: "In your CV you claim that you can type 1000 characters per minute - for real?!" "Yes!", she replies, then adds in a low voice: "but such nonsense comes out..."
ww520 3y ago
SSD have very good bandwidth, in excessive of 10 GB/s. The bottleneck is often at the CPU. For a 10Ghz CPU, it can spend 1 cycle to process 1 byte. That’s the scale we’re at now. https://www.tomshardware.com/features/ssd-benchmarks-hierarchy https://www.tomshardware.com/features/ssd-benchmarks-hierarc...
klysm 3y ago
How is that not a selling point? You want the disk to be the bottleneck
- cout 3y ago
  Not necessarily. For example, an uncompressed log will saturate disk more easily than a compressed log but if compression is fast enough the compressed log will write more data in the same amount of time. A more complex case: a column store might write in batches. Later an insert in the middle might require the entire batch to be read from disk and then rewritten. This makes queries faster later on but at the cost of more disk io up front. In this case disk bandwidth is also saturated but write performance might be worse than an append-only log that does not optimize at all for reads/queries.
  - klysm 3y ago
    Those are good points. Perhaps a better way to phrase it is you want the system to be able to utilize as much disk bandwidth as you give it.

avinassh 3y ago

How does this compare with RocksDB? Also, are there any performance benchmarks?

emills 3y ago
There’s a paper that does some benchmarking against other options here: https://www.microsoft.com/en-us/research/uploads/prod/2018/03/faster-sigmod18.pdf https://www.microsoft.com/en-us/research/uploads/prod/2018/0...
welder 3y ago
Looks like it's exponentially faster than RocksDB, but in most use cases the bottleneck would be the network and available sockets on the machine running FASTER. Unless you're doing high throughput embedded data ingestion. Maybe Neuralink could use this.
ww520 3y ago
RocksDB supports point query and range query. This only supports point query. Also I'm not sure whether FASTER supports transaction, as the paper didn't mention it.
- yencabulator 3y ago
  My notes from 2018 say FASTER has no multi-key transactions.

CyberDildonics 3y ago

I wish people would push back against using a generic adjective as a name. Naming something "Faster" is just trying to get someone to remember by being intentionally confusing.

hacknews20 3y ago
What! Nonsense.
- CyberDildonics 3y ago
  Well you do make a compelling argument.

bravura 3y ago

Are there Python bindings? I couldn't find any.

DenisM 3y ago

How does it compare to FoundationDB? Nether the paper nor the GitHub page mentioned it.

_bohm 3y ago
It would be a bit of an apples-to-oranges comparison. FoundationDB is a distributed KV database that supports range queries. FASTER is an embedded KV store that only supports point lookups. The use cases for each are rather different.

siliconc0w 3y ago

I really like the idea of tiering a log device such that you go from memory -> nvme -> object storage. You get some nice properties like fast low latency commit times from NVMe, read your own local writes (usually good enough), but have most of your cold data on cheaper durable object storage with some intelligence to pull down/warm up pages when you suspect you'll need them. It'd be nice if this had a more language-agnostic frontend like gRPC or something.

dang 3y ago

Related: Faster A fast concurrent persistent key-value store and log, in C# and C++ - https://news.ycombinator.com/item?id=25741670 https://news.ycombinator.com/item?id=25741670 - Jan 2021 (8 comments) Faster – Fast key-value store from Microsoft Research - https://news.ycombinator.com/item?id=17785002 https://news.ycombinator.com/item?id=17785002 - Aug 2018 (76 comments) Faster – A key-value store for large state management - https://news.ycombinator.com/item?id=17267403 https://news.ycombinator.com/item?id=17267403 - June 2018 (34 comments)

nimchimpsky 3y ago

[dead]