Hi,
I am currently implementing a growable array data model on foundationdb
regarding the push functionality, the current impl does something similar to the below psuedocode.
begin transaction; length = to_u64( get(subspace(name, "length"), no_snapshot) ) set(subspace(name, to_bytes(length)), value ) set(subspace(name, "length"), length + 1 ) commit;
The following is a little slow on my M2 pro, ssd and mem engine (didn’y try redwood).
Taking roughly ~9ms.
In addition, I am not certain it guarantees serial isolation.
That seems like about the data model I’d expect for an array list data structure. You can see it’s pretty similar to the “vector” data structure in the documentation: Vector — FoundationDB OFF documentation The docs omit a separate “length” field, but it does make sense to add one if you want to be able to retrieve the length in O(1) database keys read. Arguably, you could use atomic mutations here to update the length, but the main benefit of that is that it allows concurrent transactions to both modify the same key, but it’s clear that this array structure is actually amenable to that. (See: Atomic Operations.)
I believe the code guarantees serial isolation, assuming that “append” (above) and “truncate” (removing the last k elements) are the only operations. That’s because both operations will end up reading and updating the length key, so no two transactions can concurrently update the same element. If you add a “set” operation that takes an index and sets it to a value, you should also be okay as long as you also read the length for bounds checking purposes. In theory, this would allow two “set” operations to happen concurrently as long as nothing changes the length, even if they happen on the same key. Whether or not these semantics are desirable are up to the use case. If the key is also read during the transaction, this would stop two updates to the same key from being concurrently updated. (There are also modifications to be made if you wanted to support, say, an append and a set operation to both succeed, but you have to be a little careful not to allow, say, a truncate and a set to a now-deleted index to be allowed concurrently.)
I am a little surprised that this took 9 ms locally. There are a few things that could be going on.
For one, there’s some overhead with beginning and committing a transaction, so you’ll get better performance (per operation) by batching more work together in a single transaction. You can try and get insight into that by instrumenting timing the commit separately from the reads. You may also want to make an explicit call to get_read_version, which is a necessary part of transaction initialization that happens during the first read if not called separately, just to get insight into where the time is going.
There’s some amount of overhead during the initial set up when connecting a client to the server (e.g., the client needs to figure out the current configuration of the FDB cluster to start routing requests correctly). This can be compounded with things like JIT compilation if you’re using, say, the Java bindings. For that reason, it can make sense to give it time to warm up before making measurements.
That being said, I’m still a little surprised at 9 ms. I’d expect each read to take about 1 ms apiece (maybe a little faster given that there shouldn’t really be network delay). There’s only one read, so that’s 1 ms. Set operations are done locally in memory, so those are “free” (ish). The get-read-version at the beginning of the read can take 2-3 ms, especially if the cluster is busy, as that’s where FDB injects rate limiting. Commit taking 4 ms seems a little high, though not impossible