Missing/Confusing references in docs and source code

(Wolf Dan) #1

I’ve been taking a look to the layer implementations in the foundation source code and checking out the docs, but I have found a missing reference in the layer implementation as well a confusing “reference” in the docs

The first one is the import simpledoc in the layers folder that is used in many files inside it, I tried to found where is that import with not success at all

The other one was when I was looking for a way to manage pagination in foundationdb, in the know limitations mention the RankedSet layer under the Key selectors with large offsets are slow topic, but is the only place in all the doc/source where is mentioned, is it a implemented layer? (Where is it?) or an specific data structure? (If so, which one is it?, the only one info about RankedSet I’ve found is the Ranked Set Sampling which I don’t see too much relation about the described there)

I’m not sure if this is the right place to post it or in github issues, if is the wrong one please tell me and I move the topic to github

Thank you

(Alec Grieser) #2

Oops, that looks like it is referencing some old sample code that we used to have. We didn’t release that as part of the initial open sourcing. Hopefully, we’ll be able to increase the sample code we have available in the future.

The simpledoc “layer” was really just a simple document-based sample layer designed to show how one might go about building something like a JSON document store. It uses some of the same techniques that we go through in how to build indexes (etc.).

The RankedSet mentioned in the docs is another such sample layer. In particular, it means a data structure that lets you quickly find the k’th element in a set. Naïvely, you could do this in FDB by performing a range scan over an index and returning the k’th element, but that’s Θ(k) in terms of amount of data read. You might also think you could use a key selector to just get the k’th result, but it turns out that that implementation is also Θ(k). (It actually has essentially the same implementation as the aformentioned range read.) The data structure in question could work in Θ(log k) by using a persistent skip list. I believe that the .Net bindings still have an example of a similar thing, if you’re interested:

(Ryan Worl) #3

I found that old code indexed on some random website!

Getting the number of key/value pairs
(Wolf Dan) #4

Thank you @alloc !

I found the simpledoc python implementation on some random repository:

Here the version in python 3.6 that I did

Thank you @ryanworl !