HN user
I'd absolutely love to play with this. one idea I had is to train another model to create bitmaps of sidewalks and roads and add a simulation for pedestrians and cars. day/night cycle would also be so cool!
switch to auto mode and it should still work!
Here's an interesting negative result.
After watching this video, my first thought was whether recent results from columnar compression (e.g. https://docs.vortex.dev/references#id1) applied "naively" like QOI would have good results.
I started with a 1.79MiB sprite file for a 2D game I've been hacking on, and here are the results:
PNG: 1.79 MiB
QOI: 2.18 MiB
BtrBlocks: 3.69 MiB
So, there's magic to being Quite OK that is more than just applying compression techniques than elsewhere :)
Deepseek is already using SSDs for their KV cache: https://github.com/deepseek-ai/3FS
I really love this space: Navarro's book is an excellent survey.
Erik Demaine has a few great lectures on succinct data structures too: L17 and L18 on https://courses.csail.mit.edu/6.851/spring12/lectures/
that's roughly what the wasm component model is aiming for!
https://hacks.mozilla.org/2019/11/announcing-the-bytecode-al...
can you specify the algorithm in more detail?
this looks to be solving a different problem than A*, which operates over discrete graphs. this looks to be operating in 2D continuous space instead.
so, what is the algorithm for finding the optimal point on the obstacle's outline for bypass (4)? is it finding the point on the outline nearest the destination?
then, how do you subsequently "backtrack" to a different bypass point on the obstacle if the first choice of bypass point doesn't work out?
there's something interesting here for trying to directly operate on 2D space rather than discretizing it into a graph, but I'm curious how the details shake out.
this is unbelievably cool. ~27ns overhead for searching for a u32 in a 4GB set in memory is unreal.
it's interesting that the wins for batching start diminishing at 8. I'm curious then how the subsequent optimizations fare with batch size 8 (rather than 128).
smaller batch sizes are nice since it determines how much request throughput we'd need to saturate this system. at batch size 8, we need 1s / ~30ns * 8 = 266M searches per second to fully utilize this algorithm.
the multithreading results are also interesting -- going from 1 to 6 threads only improves overhead by 4x. curious how this fares on a much higher core count machine.
I love playing with it at UltraHigh quality and 1 solver iterations. It reminds me of gradually incorporating one ingredient into another when cooking: like incorporating flour into eggs when making pasta.
+1. I'd be curious how much of a pessimization to uncontended workloads it'd be to just use `tokio::sync::RwLock`.
and, if we want to keep it as a spinlock, I'm curious how much the immediate wakeup compares to using `tokio::task::yield_now`: https://docs.rs/tokio/latest/tokio/task/fn.yield_now.html
looking forward to it!
I'd be curious if y'all end up supporting adding filter attributes to the inverted index that can then be pushed down into the posting list traversal.
for example, a restaurant search app may have (1) an embedding for each restaurant but also (2) a cuisine. then, if a restaurant has `cuisine = Italian`, we'd also store its ghost ID in a `cuisine:Italian` posting list.
at query time, the query planner could take a query like `SELECT * FROM t1 WHERE cuisine = 'Italian' ORDER BY DISTANCE(..)` and emit a plan that efficiently intersects the `cuisine:Italian` posting list with the union of the partitions' posting lists.
this feels to me like a potential strength of the inverted indexing approach compared to graph-based approaches, which struggle with general filtering (e.g. the Filtered-DiskANN paper).
very cool stuff! I just read the SPFresh paper a few days ago and was wondering if it's been implemented in industry (e.g. Turbopuffer's implementation of SPANN).
I'd be curious how y'all represent the posting lists for each partition in InnoDB:
- what IDs are you storing in the posting lists?
- how are the posting lists represented on disk? are they using compression and/or some form of skip indexing? the paper seemed to use a pretty simple block-based representation, but I'm curious what works well in practice.
- how do the posting list data structures themselves handle incremental updates and MVCC?
note that convex is open source! https://github.com/get-convex/convex-backend
if you don't want to manage your own infrastructure, you can use our hosted product, but otherwise it's totally fine to self-host the open source binary.
(convex cofounder here)
yeah! we were talking to the antithesis folks during this project, but it wasn't far enough along when we started the project in 2016.
we were heavily influenced by the original foundationdb testing talk from strange loop (wwilson, one of the antithesis founders): https://www.youtube.com/watch?v=4fFDFbi3toc
former area tech lead for dropbox (and frequent collaborator with isaac) here!
happy to answer any questions.
adding to the chorus here - this is great tech. we use it internally at convex for implementing OLTP full text search.
other than its runtime characteristics, the codebase is well organized and a great resource for learning about information retrieval.
we just open sourced the backend last month! https://news.convex.dev/convex-goes-open-source/
hey, sujay (the author) here! happy to answer any questions about the post or convex more generally.
this is a really cool idea.
one followup I was thinking of is whether this can generalize to queries other than key value point lookups. if I'm understanding correctly, the article is suggesting to take a key value store, and for every `(key, value)` in the system, split `value` into fragments that are stored on different shards with some `k` of `M` code. then at query time, we can split a query for `key` into `k` subqueries that we send to the relevant shards and reassemble the query results into `value`.
so, if we were to do the same business for an ordered map with range queries, we'd need to find a way to turn a query for `interval: [start, end]` into some number of subqueries that we could send to the different shards and reassemble into the final result. any ideas?
super cool stuff — such deep OS integration is refreshing when we mostly just see cross-platform electron apps these days.
the post calls out replication and durability, and I'd be curious to know more there too. do they replicate within a fly region? S3 replicates to multiple AZs within an AWS region -- is there an equivalent for fly?
I'd be curious how this is actually implemented on fly too. does the tigris block store use fly volumes (https://fly.io/docs/reference/volumes/)? this doesn't seem to add up since fly volumes are on NVMe SSDs and are $0.15/GB/month, compared to tigris which charges $0.02/GB/month. is there some secret sauce for attaching hard drives to fly instances?
It's a bit old and doesn't include recent microarchitectural changes, but Section 2 of the FlexSC paper from 2010 (https://www.usenix.org/legacy/event/osdi10/tech/full_papers/...) has a detailed discussion of these indirect effects. I especially like how they quantify the indirect effects by measuring user code's IPC after the syscall.
as someone who's followed along (in large production systems) from `eventual` to a large combinator-based `futures`-0.1 system to async/await today, I really enjoyed this post and all its historical context.
despite its complexity and slight ergonomic annoyances, async rust is a monumental achievement: safe userspace concurrency without heap allocation!
magic pocket's tech lead (disclaimer: my cofounder at convex) has a whole talk on this concept of "durability theater" [1]!
the tldr is that those numbers of 9s are just table stakes. no system should ever lose data due to routine disk failures. so then, as you mention, there's another whole art to mitigating those other sources of problems.
[1] https://www.facebook.com/atscaleevents/videos/17416916227706...
hi! sujay from convex here. I remember reading about your "reverse query engine" when we were getting started last year and really liking that framing of the broadcast problem here.
as james mentions, we entirely re-run the javascript function whenever we detect any of its inputs change. incrementality at this layer would be very difficult, since we're dealing with a general purpose programming language. also, since we fully sandbox and determinize these javascript "queries," the majority of the cost is in accessing the database.
eventually, I'd like to explore "reverse query execution" on the boundary between javascript and the underlying data using an approach like differential dataflow [1]. the materialize folks [2] have made a lot of progress applying it for OLAP and readyset [3] is using similar techniques for OLTP.
Navarro's book Compact Data Structures is an excellent survey of this literature! https://www.cambridge.org/core/books/compact-data-structures...
I love the perspective of computing the information theoretic lower bounds for a data structure and then trying to achieve that with as little overhead as possible while still supporting efficient operations on the structure.
I've been pretty happy with datadog's distribution type [1] that uses their own approximate histogram data structure [2]. I haven't evaluated their error bounds deeply in production yet, but I haven't had to tune any bucketing. The linked paper [3] claims a fixed percentage of relative error per percentile.
[1] https://docs.datadoghq.com/metrics/distributions/
[2] https://www.datadoghq.com/blog/engineering/computing-accurat...
I really enjoyed this talk.
How does a system with completely static resource allocation accommodate cases where the underlying hardware is actually dynamic? For example, consider hot-plugging USB devices or storage media.
Would there be a fixed "maximum number of USB devices," with resources reserved at compile time for the maximum? If so, does this preclude high resource utilization in the common case, where the user isn't hitting these limits?
Nonlinear Dynamic Systems and Chaos by Strogatz is amazing. It’s extraordinarily well-written and illustrated, and if you have some basic calculus and differential equations under your belt, it’s also quite accessible.
hey, sujay (one of the authors from the paper) here! happy to answer any questions about the paper/system.