xavcochran
Joined 3 years ago
Karma
13
Submissions
22
Member since
Mar 13
Avid Rust developer and founder of HelixDB (YC X25)
View on Hacker NewsRecent submissions
Comment · 2 months ago
I made a byte-range cache for object storage.
For full hits it's zero copy. On a miss, it fetches only the missing bytes from object storage needed to serve the request.
It merges overlapping ranges and coalesces concurrent misses into one object storage request.
I use it primarily for a full-text search implementation that uses tantivy which was adapted to be transactional and run on object storage.
With our implementation, a full-text search only requires 2 round trips to object storage. The first trip gets the manifests so we know which blob files we need to fetch for the given search. The second trip gets the blobs determined by the manifests in parallel.
Each request first hits the range cache so that rather than downloading the whole split file (which can get large 100s MBs), it either gets a hit and returns, or has a miss and gets the specific bytes it needs.
If some of the data from an object storage request overlaps the data already in the range cache it merges it so you have continuous byte arrays to read from. e.g. let cache = {some_key: [0..100]} and a new request for `some_key` retrieves [50..200] from object storage, the new data in the cache would become {some_key: [0..200]}
Thought it was pretty neat and that it could be useful to some folks who are working with object storage.
Comment · 1 year ago
The benefit of baking in the dimension and size of individual elements (the precision) is the fact that the size will be known at compile time meaning it can be allocated on the stack instead of being heap allocated.
Comment · 1 year ago
We utilize some of LMDB's optimizations such as the APPEND put flags. We also make use of LMDB handling duplicates as a one-to-many key instead of duplicating keys. This means we can get all values for one key in one call rather than a call for each duplicate.
For keys we are using UUIDs, but using the v6 timestamped uuids so that they are easily lexicographically ordered at creation time. This means keys inserted into LMDB are inserted using the APPEND flag, meaning LMDB shortcuts to the rightmost leaf in its B-Tree (rather than starting at the root) and appends the new record. It can do this because the records are ordered by creation time meaning each new record is guaranteed to be larger (in terms of big-endian byte order) than the previous record.
We also store the UUIDs as u128 values for two reasons. The first is that a u128 takes up 16 bytes where as a string UUID takes up 36 bytes. This means we store 56% less data and LMDB has to decode 56% less bytes when doing code accesses.
For the outgoing/incoming edges for nodes, we store them as fixed sizes which means LMDB packs them in, removing the 8 byte header per Key-Value pair.
In the future, we are also going to separate the properties from the stored value as empty property objects still take up 8 bytes of space. We will also make it so nothing is inserted if the properties are empty.
You can see most of this in action in the storage core file: https://github.com/HelixDB/helix-db/blob/main/helixdb/src/he...
Comment · 1 year ago
Looking at your benchmarks you say for inserting 1k edges its around 500,000 ns/iteration. Is this 500,000 ns/per edge insertion or for all 1k of them?
Comment · 1 year ago
thank you! any feedback would be much appreciated
Comment · 1 year ago
SPALDE*
Comment · 1 year ago
there is also the fact that the more dimensions you have for embedded data the more diluted the embedding becomes so it is unusual to go anywhere near the limits of vector length!