Node bindings release 0.8.0, now with Versionstamp support in the tuple layer!

Using FoundationDB
1

@josephg just released version 0.8.0 of the Node bindings, which are available on GitHub here: https://github.com/josephg/node-foundationdb

Important updates include bumping the supported FDB version to 600, improving the ergonomics of the Versionstamp API, and adding Versionstamp support to the tuple layer.

    import * as fdb from 'foundationdb'
    const db = fdb.openSync().withKeyEncoding(fdb.encoders.tuple)
	
    const key1 = [1,2,3, fdb.tuple.unboundVersionstamp()]
    const key2 = [1,2,3, fdb.tuple.unboundVersionstamp()]
	
    await db.doTn(async tn => {
        tn.setVersionstampedKey(key1, '1')
        tn.setVersionstampedKey(key2, '2') // Does not overwrite first insert!
    })

    // key1 is [1,2,3, {type: 'versionstamp', value: Buffer<10 bytes followed by 0x00, 0x00>}]
    // key2 is [1,2,3, {type: 'versionstamp', value: Buffer<10 bytes followed by 0x00, 0x01>}]

    // You can override this behaviour by baking an explicit code into your call to `tuple.unboundVersionstamp`:
    const key = [1,2,3, fdb.tuple.unboundVersionstamp(321)]

After the transaction commits the keys are modified to replace the unbound versionstamp with actual versionstamp.

1 Like
2

^_^ I’m very happy with how the API turned out, although the method names are all super huge for javascript. It also passes all the tests from the binding tester - well, at least until non-determinism bugs in the python bindings make it crash out.

I still haven’t ported / implemented the directory layer across. I was hoping someone else would do it, but that hasn’t happened. Once I do it’ll be feature complete with the Python and Java bindings, and I’ll release the binding library as 1.0.

2 Likes
3

What kind of arguments to the binding tester are producing this problem? I don’t think I’ve seen this behavior in the current bindings in our runs, but if you can lead me to a reproduction I can try to fix it.

4

FWIW this hasn’t happened to me when I updated my fork to 600 and ran the binding tester, but maybe it is a versionstamp thing (which I didn’t change at all)

5

Oops - I tried reproducing this from the latest master and the nondeterministic error I was seeing has become deterministic. I tracked it down to a bug in my javascript bindingtester implementation.

My mistake! Thanks anyway :sweat_smile:

6

For my own curiosity, how to you make setVersionStampedKey(...) recognize the offset of the versionstamp in the key?

Here it looks like your unbounded stamps are the versionstamp type header followed by a run of 10-12 zeroes . What would happen if another part of the key would contain the same byte sequence by chance (or would not use the tuple encoding, or mix the tuple encoding with a binary prefix/suffix?).

In my implementation, I used a random 10-byte marker - generated for each transaction - that is used for all “unbounded” version stamps generated from this transaction. The setVersionstamped(Key|Value)(..) methods then scan the key or value to look for that marker (and hopefully find exactly one).

If, by random chance, the key or value contains the same random byte sequence, I would find two or more occurrences of this marker, and I would throw a “fake” fdb exception, triggering the transaction to retry with a different random marker.

There is a very small chance of retrying again and again, which means this is not 100% safe by design, but I’m not sure if there is a generic solution that works with all encodings (not only tuples) and that does not require to handle the keys or values for stamped operation differently (having a dedicated set of types or methods to track the stamp location).

This solution has the added bonus of being able to locate multiple stamps in the same blob, but then you lose the protection against the situation disribed above (unless the caller specify exactly how many stamps are in the key/value, which is not really ideal).

7

This API relies on you using an existing key encoder. There are other APIs which you can use to set a versionstamp yourself or with a prefix/suffix.

8

I have been using the same approach outlined by you (found it on another thread). But why do you have to cancel the transaction when you find same marker inside the key? I would assume you could just generate a new marker and retry the procedure?

There is a very small chance of retrying again and again

I would consider finding a different 10 byte marker in the same key again and again as an impossibility unless the random generator is flawed

  defp encode_versionstamped(%Coder{module: module, opts: opts} = coder, value) do
    marker = :crypto.strong_rand_bytes(10)

    {count, transformed_value} =
      traverse(value, &Versionstamp.new(marker, Versionstamp.user_version(&1)))

    if count != 1 do
      {:error, count}
    else
      encoded = module.encode(transformed_value, opts)
      {start, 10} = :binary.match(encoded, marker)

      case :binary.match(encoded, marker, [{:scope, {start + 1, 10}}]) do
        :nomatch ->
          {:ok, encoded <> <<start::unsigned-little-integer-size(32)>>}

        _ ->
          encode_versionstamped(coder, value)
      end
    end
  end

  defp traverse(%Versionstamp{} = v, cb) do
    if Versionstamp.incomplete?(v) do
      {1, cb.(v)}
    else
      {0, v}
    end
  end

  defp traverse(value, cb) when is_tuple(value) do
    {count, list} = traverse(Tuple.to_list(value), cb)
    {count, List.to_tuple(list)}
  end

  defp traverse(value, cb) when is_map(value) do
    {count, list} = traverse(Map.to_list(value), cb)
    {count, Enum.into(list, %{})}
  end

  defp traverse(value, cb) when is_list(value) do
    {count, list} =
      Enum.reduce(value, {0, []}, fn item, {count, list} ->
        {c, item} = traverse(item, cb)
        {count + c, [item | list]}
      end)

    {count, Enum.reverse(list)}
  end

  defp traverse(value, _cb), do: {0, value}
9

The transaction is not cancelled. The exception thrown is designed to abort the transaction handler and is recognized by the retry-loop as a retry-able error, so that it calls the handler again (after renewing the random marker).

Using a cryptographic PRNG would probably be too slow for high-performance applications, and in this case we don’t need a strong source of randomness because the marker value does not “escape” (only used to recognized a location in a key), so a regular PRNG could be used instead with less entropy.

There is a tiny possibilty that both the transaction and the application create a random generator using the current unix time as the seed, and could generate the same sequence of bytes again. Would be highly timing rependant.

But the main source of retries would not be the random generator itself, but a bug in the application that would use a versionstamps twice in a key (or in both key and value at the same time). In this case, the handler would always retry until it hits the transaction retry limit.

In all cases, either the chances are tiny and would only introduce a couple of retries from time to time, or would infinitely retry and would be caught immediately by the devolepper during testing (hopefully).

10

But the main source of retries would not be the random generator itself, but a bug in the application that would use a versionstamps twice in a key (or in both key and value at the same time). In this case, the handler would always retry until it hits the transaction retry limit.

I think, this is probably the difference between our implementations. I actually traverse the key/value and replace incomplete version with marker, so if there are multiple keys, it can be found at that stage. The user never get to see the marker value anywhere

11

What if the user creates a new byte array, and generate keys manually? Or use an external serialization library that does not know about versionstamps? Or if the application is not using the Directory Layer for key prefixes?

All the solutions I’ve seen so far are done in the tuple layer or require a custom encoder, which is a bit limiting in some cases.

12

The more I am thinking about this, I guess one fundamental difference is whether we can look inside the key/value and locate the versionstamp. With lisp/erlang etc, it’s possible to look inside all the data structures. There is no class and users are limited to list, map, tuple and struct for containers (there are some specialized data structures like queue/graph etc, but I am assuming nobody would try to use it here or convert it to list/map before serialization)…

If we have that, then it doesn’t limit the use cases to tuple layer. All I have to do is replace incomplete versionstamp with a versionstamp with specific marker and call the encoding layer. Encoding layer has no idea about versionstamp position. They can output like tuple layer or just convert it to erlang term, msgpack etc. As long as the marker is present in the output bytes, we are good. we can later locate the position.

Of course, as you said, this is not completely foolproof. Some encoding layer could emit everything twice (like versioning), which would backfire in our case as there will be two markers now. Or, if somebody wants to encrypt/compress the data, that’s also a problem (but these use cases wouldn’t work anyways unless the versionstamp is handled specially)

13

I get what you say for languages/runtime that are somewhat dynamic in nature, when you can have some sort of introspection of what is going on before rendering the key into bytes.

Though even there, it would break if, for example, your application would need to interop into a C/C++/ASM third-party serialization library that is opaque to your runtime where all you see are bytes coming in or out.

This may be an uncommon scenario, and if your solution works for 95+% use cases, then I guess it’s perfectly fine, and people in the less common scenarios would have to do it the hard way (by calling the versions of setVersionstampedKey|Value that take an offset).

1 Like
14

I have none of that prng magic in my JS bindings!

The encoder (in this case, the tuple encoder) exposes a method called tuple.packUnboundVersionstamp(value) which returns a {data: Buffer, stampPos: number, codePos?: number} structure.

That method encodes the tuple, and on the way it looks out for a tuple item with {type: 'unbound versionstamp'}. When it sees that it encodes it into 10 empty bytes, and marks the location into stampPos. (The normal tuple.pack method will throw if it sees this marker in a tuple).

If you want to implement your own key / value encoding, you won’t be able to use setVersionstampedKey unless you implement that special packUnboundVersionstamp method for your own data type. But thats normally ok - you can just call tn.setVersionstampSuffixedKey(key, value, [suffix]) instead.