4

In reliable collections (specifically IReliableDictionary), an approach for implementing 'common' queries is to update a secondary dictionary which structures the keys to be ordered a specific way in an enumeration. For large data sets, I would like to avoid shuttling a large amount of data around.

To achieve this I would like to implement some sort of continuation token which the caller can supply to me when requesting the data. I am currently implementing this by first generating an ordered enumeration and returning the first n items where n = the MAX_PAGE size. The continuation is essentially the last key in that list of n items. The next time the caller passes in the continuation token, I generate the ordered enumerable with the filter function specifying that the key should be greater than the continuation.

This has 2 problems (that I can see):

  1. The collection could change between when the caller first requests a page and a subsequent request. This, I'm not certain I can avoid since updates to the collection need to be able to occur at any time regardless of who is attempting to page through the data.
  2. I'm not certain how the filter function is used. I would assume that since a developer could filter on anything, the GetEnumerableAsync() method must supply all keys in the dictionary before returning the enumerable. For a sufficiently large data set, this seems slow.

Are there any prescribed approaches for paging data like this? I am beginning to feel like I might be barking up the wrong tree with Reliable Collections for some of my use cases.

Justin Blakley
  • 458
  • 4
  • 16

2 Answers2

5

One way to build secondary indicies is to use Notifications. Using notifications with a reference type TKey & TValue, you can maintain a secondary index without creating any copies of your TKey or TValue.

If you need the secondary index to provide snapshot isolation, then the data structure chosen for the secondary index must implement Multi-Version Concurrency Control.

If you do not have such a data structure to host the secondary index, another option is to keep the transaction and the enumeration live across the paged client calls. This way you can use Reliable Dictionary's built-in snapshot support to provide a paged consistent scan over the data without blocking writes. Token in this case would be the TransactionId allowing your service to find the relevant enumeration to MoveNextAsync on. The disadvantage of using this option is that Reliable Dictionary will not be able to trim old versions of the values that are kept visible by the potentially long running snapshot transactions.

To mitigate the above disadvantage, you would probably want to throttle the number of in-flight snapshot transactions and how long a client has to complete the paged enumeration before your service disposes the enumeration and the relevant read transaction.

When CreateEnumerableAsync with a key filter is used, Reliable Dictionary will invoke the filter for every key to see if it satisfies the custom filter. Since TKeys are always kept in-memory today, for most key filters we have not seen issues here. The most expensive part of an enumeration tends to be retrieving paged out values from disk.

Mert Coskun - MSFT
  • 316
  • 1
  • 5
  • When you say 'Token in this case would be the TransactionID', does that mean there is a mechanism to create a transaction from a transactionId, or are you simply saying that I can store the ITransaction/IAsyncEnumerable in a dictionary somewhere in the service? If the latter- would this withstand a replica going down? – Justin Blakley Dec 08 '16 at 22:45
  • I mean the latter @JustinBlakley : store the ITransaction and IAsyncEnumerable in a data-structure that allows you to use TransactionId to index. In-case of a failover, all in-flight transactions initiated on the replica that failed are aborted. – Mert Coskun - MSFT Dec 11 '16 at 20:48
  • That makes sense @MertCoskun, I guess one final optimization I could make is to also include the last key returned in the continuation token. That way in case of a replica failover I could pick up where I left off with a performance hit. - though given a sufficiently large key set it may be just better to return an error to the caller and let it determine what to do. – Justin Blakley Dec 12 '16 at 15:41
  • 2
    @JustinBlakley , Remember that the transaction on the initial replica was keeping track of what is visible in this enumeration (snapshot view) and ensuring old versions that are visible to this transaction are not garbage collected. The new replica trying to serve the next paged read will not have this transaction. Furthermore, the new transaction it created will have a different snapshot view (since it is taken at a different logical time). Hence, not only you cannot guarantee snapshot isolation to your client, you have to handle cases where the new replica might not have the last read key. – Mert Coskun - MSFT Dec 12 '16 at 18:26
0

I have a similar problem, and it also involves filtering and sorting on data from multiple partitions.

My plan is to build an indexed view in a non-partitioned stateful service by using notifications. Here I will have multiple dictionaries, with different keys, where each key is one or more properties that can be filtered on or sorted by, and the value is a sorted list of IDs.

Basically, I plan to search, sort and page on these keys, then on the last step, I go with the IDs for the page that needs to be returned to the original partitions and get the full data for these IDs from there (this can be done from a different stateless service as well).

This method does not provide data consistency, since the queried data can change between subsequent paging.

It must be slower than the one with snapshots and continuation tokens, but maybe its worth trying out.

Robert
  • 176
  • 7