Questions and remarks about supported types, missing types and named variables

[KrzysFR]

Great idea! I've used tuples for a long time, and always wished there was a standard for representing them and querying them. Hopefully this could be the one :)

I apologize for the flood, they are notes I took when implementing a parser for fql in C#/.NET

I have a few remarks, coming from a long time user of tuples, mostly in the context of writing complex layers in .NET/C#, and not 100% familiar with go conventions.

• Numbers: Why the distinction between int and uint? Is this a "go" thing, or is there an actual reason?
  • For -123 it is clear that it is not "uint", but what about 123? From my point of view it is both "int" and "uint"
  • What about 32-bit vs 64-bit?
  • Comparatively, there is no distinction with float between 32-bit and 64-bit IEEE numbers?
  • How do you handle NaN or infinities?
• Uuids: I find it difficult to parse a UUID that is not bounded by either {...} or any other character.
  • I frequently see uuids escaped as either {xxxx-xxx...} or "xxxx-xxxx-...". (or maybe it is a Windows thing?)
  • Using {...} for uuids would make it non-ambiguous for the parser
• Bytes: when parsing 0x1234, you first see the 0 which could the be start of a number, a uuid, or a byte sequence.
  • I don't have a nice solution for this, but maybe use [ 1234 ] or '\x12\x34' (single quote, like it was in the python 2 tuple encoder) for bytes?
  • Are hexa digits always upper? lower? either? the syntax definition is a bit ambiguous
  • For me, 0xFF and 0xFE is ambiguous, because they are the byte prefix for the System subspace and Directory Layer, which are a single byte, where here I think they would be encoded as 01 FF 00 and 01 FE 00 instead?
• Strings: How do you handle escaping of unicode characters? What about unicode text like "こんにちは世界" , high/low surrogates?
  • Could we define \uXXXX to encode any codepoint ?
• Tuples: does (...) means "any tuple, empy or not? For ex, in (1, <int>, (...), <int>), does the middle part means "any tuple" ?
• Ends With: is ("hello", 123, ..., <int>) supported? This would help with "variable sized" tuples in some layers, where you still need to parse the last one or two parts of a tuple.

There are a few types that I use frequently in tuples, and that are missing:

• Empty: most indexes have empty values. In the old python binding, it used '' (two single quotes) to define them. What would we use here? nil seems weird because it is different (for me) than the concept of "empy". Maybe add <empty> or <none> for values?
• Version Stamps: maybe add a new stamp or versionstamp or vs type in variables? ex: (1, <stamp>, ...)
  • There are two types of version stamps, 80-bits and 96-bits. They use prefix 0x32 and 0x33 in the tuple encoding, followed by 10 or 12 bytes.
  • I usually don't really distinguish between both sizes, they are all "stamps" for me.
• Dates: this is unfortunately not specified, but I usually represent times as days (float) since Unix Epoch
• Durations: same, I store them as seconds (float), but this may not be a standard representation.
• Custom types: The original spec had a way to define "custom types" for the application, which would have a custom header byte, followed by 0 or more bytes (custom to the app).
  • In practice, I only used them to define the Directory (0xFE) and System (0xFF) prefix, which are useful in tuples that have to query the system space, or inside the Directory Layer (each nested partition adds another 0xFE to the bytes).
  • It would help resolve the ambiguity in (0xFE, "hello") which for me reads as "the key 'hello' in the top-level Directory Layer" and encoded as FE 02 h e l l o 00, where I guess here it would be encoded as 01 FE 00 02 h e l l o 00 which is not the same.
• System subspace: how can I represent xFF/metadataVersion or other system keys? They usually don't use the tuple encoding for the keys.
• Regex/Patterns/Constraints: Would it make sense to be able to impose constraints on types? Like a regex on a string, a range on a number, a maximum/minimum/exact size for string/bytes?
  • could be useful for counters which are usually exactly or up to 4/8 bytes.
  • The uint vs int distinction could be emulated with a "must be positive" or "must be exactly 64-bits" constraint
  • Same for 80-bit vs 96-bit version stamps

Regarding directories:

• What if I use partitions/sub-partitions ? This is a way to "lock" an application into a specific prefix (ie: if "/foo" is a partition with prefix 15 2A (== (42, )), all keys will have this prefix, even sub-directories of this partition.
  • If the app is locked to sub-partition /foo/bar, then ALL keys would start with /foo/bar/... so in practice we represent them without the prefix, so something like .../my/dir (similar to a webapp that could be hosted under any path)
  • Since ... means "zero or more" in the tuples, maybe use ./my/dir or ~/my/dir to represent "from the root defined for this application" ?
• Directory names are string, and I also use strings 99%+ of the time, but technically, the names can be any sequence of bytes, in order to represent numbers, uuids, etc... I'm not sure if this is frequently used in the field, but if it is, maybe we would also need variables in directory names? like /foo/<string>/bar or /foo/<uuid>/bar ?

On top of querying, I see this as very useful to encoded the "schema" of a layer somehow, so that a UI could automatically decode data into an arbitrary subspace (using the optional Layer Id in directories).

For example, I used the following format to define the schema of a custom layer, like a typical "table with index + change log" mini layer:

• (..., <metadata_key>) = <metadata_value>
• (..., 0, <doc_id>) = <json_bytes>
• (..., 1, <index_id>, <value>, <doc_id>) = ''
• (..., 2, <index_id>, <value>) = <counter>
• (..., 3, <version_stamp>, <doc_id>) = <change_event>

Legend:

• ... means the prefix of the Directory where this layer is stored.
• <name> was a placeholder for a type of data, but the type was not specified

I think this could be adapted to use fql as the syntax, but this would required adding the support of named variables:

• either <foo:int> or <int:foo> would define foo to be a variable of type int
• would need a solution for "of any type", either <foo:any>/<any:foo> or <foo:>/<:foo>
• for counters (atomic add/increment), we need to specify a size, usually 32 or 64 bits: <uint32>/<uint64> ? <uint:32>/<uint:64> ? <uint,32>/<uint,64> ?

The above could become:

• ~/(<string:metadata_key>) = <any:metadata_value>
• ~/(0, <uint:index_id>, <uint:doc_id>) = <bytes:json>
• ~/(1, <uint:index_id>, <int|string|bytes:value>, <uint:doc_id>) = <empty>
• ~/(2, <uint:index_id>, <int|string|bytes:value>) = <uint64>
• ~/(3, <stamp:timestamp>, <uint:doc_id>) = <bytes:delta>

[janderland]

I'll answer all these questions in a follow up comment, but I'll start by saying that I'm almost done with a proper manual for FQL which may clarify a lot of these questions.

[janderland]

Why the distinction between int and uint?

It's modeled after Go's implementation of the tuple layer. Thanks for pointing this out. I will need to think about what I want to do with this. Go's tuple layer makes all the integers look like int64 or uint64.

How do you handle NaN or infinities?

I have not added support yet. This will be supported, most likely as the tokens like nan, inf, -inf.

I find it difficult to parse a UUID that is not bounded by either {...} or any other character.

I haven't encountered any problems with parsing UUIDs myself. The context of the FQL query provided me with enough information to parse them without additional bounding characters.

Bytes: when parsing 0x1234, you first see the 0 which could the be start of a number, a uuid, or a byte sequence.

Ah, this gives me a clue as to why you had problems parsing UUIDs. I allow my parser to look ahead, which allows me to see that the 0x is followed by hexadecimal digits, and hence I know it's a hex number.

Are hexa digits always upper? lower? either? the syntax definition is a bit ambiguous.

I currently use Go's standard library to parse the hex string, which allows for either. In the syntax definition I only allow for uppercase, but I'm planning on changing this. I prefer lower case myself.

For me, 0xFF and 0xFE is ambiguous, because they are the byte prefix for the System subspace and Directory Layer, which are a single byte, where here I think they would be encoded as 01 FF 00 and 01 FE 00 instead?

Yes, you are correct. (0xff) would be packed as 0x01ff00.

Also, FQL doesn't support reading/writing key-value outside of the directory layer. Therefore, it doesn't support reading/writing to the system subspace. I may change this in the future.

How do you handle escaping of unicode characters?

Unicode is not currently supported, only ASCII. I do plan to add unicode support in the future.

does (...) means "any tuple, empy or not?

Yes.

...is ("hello", 123, ..., <int>) supported?

Not currently supported, though I may add support for this in the future.

What would we use here? nil seems weird because it is different (for me) than the concept of "empty".

nil is what I'm using for empty values. This allows the empty value to logically mirror the empty element within a tuple: (nil). I don't plan to change this part, though I am glad you told me your opinion as it helps me see how other people's intuition works.

Version Stamps: maybe add a new stamp or versionstamp or vs type in variables?

Yes, version stamps will be supported sometime in the future. They are not supported yet.

Would it make sense to be able to impose constraints on types? Like a regex on a string, a range on a number, a maximum/minimum/exact size for string/bytes?

Yes, I've considered this. I may add this in the future.

What if I use partitions/sub-partitions ? This is a way to "lock" an application into a specific prefix (ie: if "/foo" is a partition with prefix 15 2A (== (42, )), all keys will have this prefix, even sub-directories of this partition.

I have not added support for partitions yet. I still need to look into this. When you set up an FQL instance, you must provide a root directory which would contain all queries to within that directory. I expect partition to work in a similar way.

Directory names are string, and I also use strings 99%+ of the time, but technically, the names can be any sequence of bytes...

I don't plan to support reading/writing all possible key-values right now. For the near future, I'm focused on supporting the 99% of use cases which only includes key-values encoded using a directory (made of strings) and a tuple. After I have this working, documented, and well tested, then I may implement support for other cases like this one.

This is similar to the question about system keys. Most user don't need to access these, so I will focus on the most common use cases first.

On top of querying, I see this as very useful to encoded the "schema" of a layer somehow, so that a UI could automatically decode data into an arbitrary subspace (using the optional Layer Id in directories).

Yes, this is one of the goals of the project.

named variables...

Yes, this is a feature which I will explain in the manual. The manual should be available within the next week or so.

[KrzysFR]

I've been able to write a very naive first version of a fql parser and query runner for range reads, and this is already VERY handy! In one of my tests, I used a schema for a very simple document+index layer I had, and simply by using fql queries, I was able to implement a query system on top of that, without much effort.

This could be a game changer when writing layers, where adding long running queries has always been the most difficult task! If a fql Layer could implement proper long range reads, it could be reused by a lot of other layers.

By the way, should it spelled "fql" or "FQL" for the "official" name?

It's modeled after Go's implementation of the tuple layer. Thanks for pointing this out. I will need to think about what I want to do with this. Go's tuple layer makes all the integers look like int64 or uint64.

I had the same issue when porting the original Tuple Layer from python to .NET. The layer has been mostly design in Python, so inherits its type system. I've been told that sorting python tuples or sorting the bytes from the packed tuples should yield the same order. I had to replicate this behavior in .NET, and it's probably that Go would have the same issue.

In practice, I treat all numbers are equivalent, whatever their types, and only treat signed/unsigned and 32/64 bits as a limitation in the domains. Meaning that <uint> would reject a negative number, while <int> would include ALL the integers (but not decimal numbers). And this would be independent of the size of the integer: .NET recently got 128-bit unsigned and signed integers which add another 2 combinations :)

For decimal numbers, this is a bit complicated, because for me "1.0" is the same a "1", but in Python floating point numbers where encoded with a different prefix in the tuple layer.

In my mind, the criteria for "is the same as" would be "do they produce the same bytes when encoded with the tuple layer" ?

Ah, this gives me a clue as to why you had problems parsing UUIDs. I allow my parser to look ahead, which allows me to see that the 0x is followed by hexadecimal digits, and hence I know it's a hex number.

My parser is also "look ahead", in fact it can see the whole statement. The remark was more regarding having a very noticeable visual queue when a human looks at the statement. This may vary from person to person, but for me, between these two strings, I can immediately spot the uuid in the second one:

• ("hello", 12456789, 4567, b8d02d81-6329-ef96-8a4d-55b376d8b25a, 0xabcdef, "world")
• ("hello", 12456789, 4567, {b8d02d81-6329-ef96-8a4d-55b376d8b25a}, 0xabcdef, "world")

Also, FQL doesn't support reading/writing key-value outside of the directory layer. Therefore, it doesn't support reading/writing to the system subspace. I may change this in the future.

I you want to add support for system keys (0xff) and the directory layer (0xfe), then you can use custom user types that exist in the current tuple layer spec. I don't know if they are implemented by the Go binding. They simply define an item with a byte header, followed by any number of bytes (so like any other pre-defined types).

In the .NET binding, I have the following "well known" custom types:

• Byte header 0xFF at the start of a tuple: this is a system key, defined as a custom type "FF" with payload being the rest of the tuple. So \xff/metadataVersion is a TupleCustomType(255, "/metadataVersion").
• Byte header 0xFE, here I only create custom type 254 with 0 payload bytes. The Directory Layer uses the tuple encoding, so the rest of the bytes would decode nicely anyway.

Unicode is not currently supported, only ASCII. I do plan to add unicode support in the future.

Whatever you do, I hope you will standardize on UTF-8 being the only encoding. It supports ASCII out of the box, and you could simply use the same syntax as in JSON (https://datatracker.ietf.org/doc/html/rfc8259#section-7)

[KrzysFR]

I have not added support for partitions yet. I still need to look into this. When you set up an FQL instance, you must provide a root directory which would contain all queries to within that directory. I expect partition to work in a similar way.

So, if you use '/foo' has the root directory, does this mean that the query /bar/baz means in that the absolute path /foo/bar/baz ? For me, I use the file system path analogy for paths in the Directory layer, so seeing '/something' means "go back to the root the filesystem/database", and would have expected either bar/baz or ./bar/baz to mean "from the current working directory".

Since I had to deal with this in my tests (they are automatically running in a dedicated test partition with a deep path, including the worker host name, process id, etc..) I temporarily used "./bar/bar" to differentiate with "/bar/baz".

I also need to be able to distinguish between "the root of the application" (which is fixed) and "the current directory", since I plan to add this to my command line shell, where you can cd into directories, like you would do in a file system, and so it must be clear to the user if the query would be relative to:

• the current path ("hello", <int>),
• a child directory: foo/bar("hello", <int>),
• a parent directory: ../../some/other/layer/("hello", <int>),
• or "the root": /tenants/ACME/foo/bar/...

[named variables] Yes, this is a feature which I will explain in the manual. The manual should be available within the next week or so.

One very frequent thing is using integer constants to sub-divide a directory subspace, without involving the Directory Layer. For ex, in pseudo code:

• (<metadata_key>) = <metadata_value>
• (0, <rid>) = <json>
• (1, <doc_id>) = <rid>
• (2, <artist>, <rid>) = ''
• (3, <genre>, <rid>) = ''
• (4, <year>, <rid>) = ''

If would be nice to be able to define constants to give names for 0, 1, 2, and 3, such as docs, 'pk', idx_artist, idx_genre, idx_year.

These could be encoded in some standardized JSON object that would be stored with a standard key at the root of a layer. Layers are supposed to have a non-empty layer_id with the name when created with the Directory Layer (which may not be a frequently used feature?), which make it easy to detect: You you enter a directory that has a non-empty "layer id", look for a "_schema" key (or something else), decode the JSON, and use the content to obtain a set of one or more "predefined" fql queries that would include named constants and variables:

pseudo code:

{
  /* ... */
  "queries": {
    "metadata": "(<key:string>) = <value:any>",
    "doc": "(0, <rid:int>) = <json:bytes>",
    "pk": "(1, <doc_id:string>) = <rid:int>",
    "idx_artist": "(2, <artist:string>, <rid:int>) = nil",
    "idx_genre": "(3, <genre:string>, <rid:int>) = nil",
    "idx_year": "(4, <year:uint>, <rid:int>) = nil"
  }
}

In a shell, the query short cut would be converted into an actual fql command:

• metadata to list all metadata => (<string>)
• metadata "count" to read a single value => ("count")
• pk "album123" to lookup a primary key into a record id => (1, "album123")
• doc 42 to get a document from its record id
• idx_genre "Metal" or idx_year 1999 to lookup values in an index => (3, "Metal", <int>) and (4, 1999, <int>).

Ideally, the value could also describe it's type, so that it could be decoded into a human readable format. Most values are usually counters, numbers, strings, json bytes, protobuf bytes, etc...

[janderland]

In one of my tests, I used a schema for a very simple document+index layer I had, and simply by using fql queries, I was able to implement a query system on top of that, without much effort.

Amazing. I'm glad these ideas are useful to you.

By the way, should it spelled "fql" or "FQL" for the "official" name?

I don't have a strong opinion. I usually write it as FQL.

I've been told that sorting python tuples or sorting the bytes from the packed tuples should yield the same order. I had to replicate this behavior in .NET, and it's probably that Go would have the same issue.

I don't think I've ever needed to replicate the ordering of tuples client side. I just allow FDB to order the tuples for me.

For decimal numbers, this is a bit complicated, because for me "1.0" is the same a "1", but in Python floating point numbers where encoded with a different prefix in the tuple layer.

According to FQL's specification, 1.0 is no the same as 1. All floating point number require a decimal point.

Whatever you do, I hope you will standardize on UTF-8 being the only encoding.

Yes, this is the plan.

So, if you use '/foo' has the root directory, does this mean that the query /bar/baz means in that the absolute path /foo/bar/baz ? For me, I use the file system path analogy for paths in the Directory layer, so seeing '/something' means "go back to the root the filesystem/database", and would have expected either bar/baz or ./bar/baz to mean "from the current working directory".

FQL doesn't currently have any concept of a "current directory". What I linked was the Go API for using FQL programmatically in Go without including query strings.

I do plan to add a meta language which allows you to alias snippets of a query for use in the queries. For example, the syntax may look something like this:

let dir -> /my/root/dir

${dir}/sub/dir("hello", "world")=nil

The let expression is the meta language. This would allow you to define snippets of a query for re-use in actual queries. I may change this in the future. Having a "current directory" could be useful.

If would be nice to be able to define constants to give names for 0, 1, 2, and 3, such as docs, 'pk', idx_artist, idx_genre, idx_year.

Yup. This could be handled by the meta language I describe above.

One very frequent thing is using integer constants to sub-divide a directory subspace, without involving the Directory Layer. For ex, in pseudo code...

I don't understand how this is better than using separate directories. Can you explain to me?

In a shell, the query short cut would be converted into an actual fql command...

Yes, the meta language would include macros which could do stuff like this. For instance:

let doc rid -> (0,rid)=<json:bytes>

# This would translate to /my/dir(0,22)=<json:bytes>
/my/dir${doc 22} 

I'm still working on this meta language syntax, so don't take any of these examples as law quite yet.

[KrzysFR]

I don't understand how this is better than using separate directories. Can you explain to me?

The directory layer has a non-trivial overhead: for each directory that you need to traverse, you need to perform sequential reads to the cluster. If you have a path of depth N, you need at least N round-trips to the database, before being able to read actual data! This can really add up ! (see below for a log of a transaction that opens the path /Foo/Bar/Baz !)

Directory subspaces are not safe to cache either, since they could be renamed/moved/deleted/re-created and get a new prefix. If /foo/bar/baz previously had prefix (7,), but was deleted/re-created and now has (42,), and one of your backend still uses the old cached prefix, it will read/write into a dead zone of the database. This delete/recreate or move/create is common when you do unit testing, or when you are upgrading the schema of some table in the database (create a temp directory, copy/upgrade the old data into it, once you are done, swap the names of the old/new tables, and then drop the old table).

I added a lot of infrastructure in the .NET binding just to try to solve this issue (deferred value-checks), but this is not magic, and I don't think this exists in the Go binding.

If you don't have a massive amount of data, the easiest solution is to have the minimum number of directories, and sub-divide them using a simple prefix like 0 (1 byte), or a small integer (2 bytes). In fact, this was how it was done before the Directory Layer was introduced, the notion of "subspaces" is adding a common prefix to a parent "subspace" to subdivide it. The Directory Layer only acts as a global map that translates long strings (directory names) into small integer + adding a hierarchy.

It could be argued that for example in /path/to/table/albums(1, <artist>, <rid>), the 1 is a surrogate for a sub-directory named "index_by_artists", but you don't need the extra round-trip to the database to find the prefix for the subspace.

The last small advantage, is that splitting a subspace "by hand" will ensure that the data stay collocated, while if you were using sub-directories, they could have very different prefix, and be separated by other data from other layers/tenant in between them.

Example log that shows the impact of the Directory Layer:

Transaction #133 (read/write, 22 operations, '#' = 250 µs, started 22:05:36.4199821Z [1729375536.419], ended 22:05:36.4261257Z [1729375536.426])
┌  oper. ┬──────────────────────────┬──── start ──── end ── duration ──┬─ sent  recv ┐
│ 0   G °│ #####&                   │ T+  0.010 ~   1.146 (  1,136 µs) │    22    12 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, `version`) => <01><00><00><00><00><00><00><00><00><00><00><00>
│ 1   G  │      ^:                  │ T+  1.151 ~   1.250 (    100 µs) │    20     4 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, `stamp`) => '\0\0\0\0'
│ 2   G  │       *                  │ T+  1.255 ~   1.354 (     99 µs) │    19     6 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, 0, "Foo") => <02>DL<00><15><16>
│ 3   G  │       ^x                 │ T+  1.358 ~   1.456 (     98 µs) │    21     0 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, `layer`) => ''
│ 4   G  │            ◦             │ T+  2.294 ~   2.329 (     35 µs) │    22    12 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, `version`) => <01><00><00><00><00><00><00><00><00><00><00><00>
│ 5   G  │            ^,            │ T+  2.336 ~   2.356 (     20 µs) │    19     6 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, 0, "Foo") => <02>DL<00><15><16>
│ 6   G  │             ·            │ T+  2.357 ~   2.368 (     11 µs) │    21     0 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, `layer`) => ''
│ 7   G  │             *            │ T+  2.369 ~   2.469 (    100 µs) │    20     6 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, 0, "Bar") => <02>DL<00><15><1A>
│ 8   G  │             x.           │ T+  2.473 ~   2.573 (    100 µs) │    21     0 │ Get ("DL", |Directory|, `<02>DL<00><15><1A>`, `layer`) => ''
│ 9   G  │               ◦          │ T+  2.828 ~   2.856 (     28 µs) │    22    12 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, `version`) => <01><00><00><00><00><00><00><00><00><00><00><00>
│ 10  G  │               ◦          │ T+  2.862 ~   2.881 (     19 µs) │    19     6 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, 0, "Foo") => <02>DL<00><15><16>
│ 11  G  │               ◦          │ T+  2.882 ~   2.906 (     24 µs) │    21     0 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, `layer`) => ''
│ 12  G  │               ◦          │ T+  2.911 ~   2.928 (     17 µs) │    20     6 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, 0, "Bar") => <02>DL<00><15><1A>
│ 13  G  │               `,         │ T+  2.929 ~   2.940 (     11 µs) │    21     0 │ Get ("DL", |Directory|, `<02>DL<00><15><1A>`, `layer`) => ''
│ 14  G  │                  ◦       │ T+  3.375 ~   3.411 (     35 µs) │    22    12 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, `version`) => <01><00><00><00><00><00><00><00><00><00><00><00>
│ 15  G  │                  •       │ T+  3.418 ~   3.468 (     51 µs) │    19     6 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, 0, "Foo") => <02>DL<00><15><16>
│ 16  G  │                  ◦       │ T+  3.473 ~   3.498 (     26 µs) │    21     0 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, `layer`) => ''
│ 17  G  │                  ^x      │ T+  3.501 ~   3.603 (    103 µs) │    20     0 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, 0, "Baz") => not_found
│ 18  G  │                        ◦ │ T+  4.608 ~   4.644 (     36 µs) │    22    12 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, `version`) => <01><00><00><00><00><00><00><00><00><00><00><00>
│ 19  G  │                        ◦ │ T+  4.651 ~   4.670 (     20 µs) │    19     6 │ Get ("DL", |Directory|, `<02>DL<00><FE>`, 0, "Foo") => <02>DL<00><15><16>
│ 20  G  │                        · │ T+  4.672 ~   4.683 (     11 µs) │    21     0 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, `layer`) => ''
│ 21  G  │                        , │ T+  4.684 ~   4.695 (     11 µs) │    20     0 │ Get ("DL", |Directory|, `<02>DL<00><15><16>`, 0, "Baz") => not_found
└────────┴──────────────────────────┴──────────────────────────────────┴─────────────┘
> Read 106 bytes in 6.143 ms and 1 attempt(s)

[janderland]

Directory subspaces are not safe to cache either, since they could be renamed/moved/deleted/re-created and get a new prefix.

I guess this is where our workloads differ. I have never used the directory rename/move feature, so on application start up we open all the directories we plan to use and cache them for the entire life of the application.

If you are not caching directories then I understand the concern.

[KrzysFR]

so on application start up we open all the directories we plan to use and cache them for the entire life of the application.

I used to do the same thing a long time ago and got bitten by this, so I encourage you to look into this.

Maybe now you are not using tools that do this, but maybe in the future you will have to use a third party tool, or change how you backup/restore in such a way that the directories could be recreated in a different order (with different prefixes, ...). You will also have to address the issue of in-place schema migration at some point.

You only need one rogue process somewhere in the cluster that was NOT properly killed or updated, or someone that resumes a paused VM, a network split that isolated part of the nodes, etc...

The bad news is that the data layout used by the Directory Layer is not very friendly for caching, so there is no easy solution. And this hasn't changed in ~10 years now, and likely never will. It was designed before VersionStamps and atomic operations existed, so today it would be very different I guess.

One solution I used was to cache all the prefixes of all the parents paths needed to traverse /foo/bar/baz (so 3 nodes in this case), and when you start a new transaction, issue an async read immediately to check that these keys are still there with the expected value, but don't wait for the result yet. Run the rest of the query, but before commit, you have to await the result of the async reads, and if there is even one difference, bust the cache, and retry. That's what I called "deferred value-check". The IFdbTransaction object has a map of pending reads, that it will have to inspect when Commit() is called, and simulate a conflict if this does not match.

You could use watches to maybe flush the cache when a directory key is changed, but watches are async, it is possible in some cases that they won't fire, and also there is a limited number of them.

Recently, I ended up with deeper and deeper directories, which made this too slow, so I took the bullet, and made a slight change to the DL, by adding a metadata key to each partition, that is atomically incremented every time a directory is deleted or renamed (not created). This way, I only need to check one key per partition (a single key if you only use the root partition), instead of N keys.

[janderland]

You only need one rogue process somewhere in the cluster that was NOT properly killed or updated, or someone that resumes a paused VM, a network split that isolated part of the nodes, etc...

Yea, we've accidentally recreated/moved directories, but because all our processes are stateless we just restarted them so that they cleared their cache and obtained the correct directory. So I agree it is a problem, just not a very bad problem in our case.

You will also have to address the issue of in-place schema migration at some point.

The way we address this at my job is by either using a new directory path or by supporting multiple KV schemas within a directory. In other words, we try to keep things backwards compatible as much as possible.

[janderland]

Anyhow, using a manual prefix for subspaces is supported by FQL as long as it's within a directory. It also sounds like your use case could be supported by simply allowing keys to only contain a tuple, without a directory.

Do you often use keys without the tuple layer?

[KrzysFR]

No, I've always used the Tuple layer because it's so much more easier to use when designing a layer, and is nicely printable in logs.

Though I've heard of people using keys encoded with raw uuids, with protobuf or some other binary protocol. There are APIs in the DL to register such a subspace by telling the DL to NOT allocate a prefix that would collide with it by random chance.

The only keys outside the DL I read are mostly system keys such as \xff/metadataVersion, or some other special keys that are there. But 99.9+% of my keys are encoded with tuples, and probably in a sub-partition (one per tenant) with paths with a very shallow depth to reduce the burden on the DL cache check.

Note that in 7.3 there is a new Tenant API that basically does the same thing as partitions in the DL, but at the native client level. I have not yet had the chance to play with it. I've added basic support for it in the .NET Binding, but the cluster needs to be specifically configured for it, and it seems tailored for big users.

I don't think this would impact FQL very much, except that the tool would need to select a tenant, and then it would be as if it was the only one in the cluster's keyspace (with its own Directory Layer instance). This makes path like /Prod/Tenants/ACME/tables/foo a bit shorter as /tables/foo, but prohibits you from doing cross-tenant queries.

[janderland]

By the way, your feedback has been very helpful. Online, it's difficult to see if the other person is enjoying the conversation, so I wanted to make it clear. You are helping me consider other workloads and use cases, which is good.

[KrzysFR]

Btw, I encourage you to go play with versiontamps: they are the one feature that most changed the way I design layers, and so I (ab)use them everywhere :)

They are usually used as sequential keys in change logs, or as out-of-the-box sequential uuid in data stores, or as a cache busting mechanism. This makes them usually present in the very first part of a tuple, which means that FQL queries would frequently have to "say their name". They can also be present in the value as a pointer to another key in another subspace.

And since I use them a lot, I'd vote for a shorter type name like <vs> or <stamp> instead of <versionstamp> :)

For their text representation, I'm not sure if there is a standard. I use @81985529216486895-123 and @81985529216486895-123#456 since it makes it easier to identify the readVersion, the commit batch, and the optional user version. They can be written in hex, but you lose the readability of the sequential ordering. Also, read versions are somewhat in sync with the clock, so by looking at the delta between two stamps, you can get a rough estimation of the wallclock time between the two events.

[janderland]

I encourage you to go play with versiontamps

Yes, we have used them at my job. At one point we implemented a message queue on top of Foundation DB and used the versionstamps to order the messages. They are very useful and will absolutely be included in FQL.

I'd vote for a shorter type name like or instead of

Yes, you may have noticed I preferred shorter type names. vstamp or vs is what I will use.

For their text representation, I'm not sure if there is a standard.

Yea, I think they should have their own unique textual form as you are saying. Simply using a hex string wouldn't be enough.

Also, read versions are somewhat in sync with the clock, so by looking at the delta between two stamps, you can get a rough estimation of the wallclock time between the two events.

At one point we were using versionstamps as a clock. Eventually we decided to use our own clock key. We have a clock client which basically updating the clock key once per second and we synchronize all our services against this clock value.