Faster tree build

[knutwannheden]

I was wondering if it would be possible to implement an optimized initial load of a ConcurrentRadixTree, where multiple mappings are supplied (maybe using a builder pattern).

I suppose the design with "mostly" immutable nodes would make this kind of difficult, as there is basically no way around the patching for every put(). Or is there? Only the locking could be skipped, but that probably doesn't make much of a difference.

Currently I just make sure to call put() in lexicographic order of the keys. I assume that should help a bit.

Regarding the patching I have a question. In the documentation it is stated that a thread reading will always see a consistent state, even with concurrent writes. I was assuming this meant the reads would basically be like "statement-level consistent reads" as provided by databases like Oracle. But looking at the implementation, this doesn't seem to be quite the case, as the patching doesn't go all the way up to the root node (as e.g. in Git I think). Did I understand this correctly.

[npgall]

Hi Knut,

I did think about options to construct the tree quickly, and posted some thoughts about Ukonnen’s algorithm and considerations for thread safety in the FAQ. Long story short, the need to support concurrent reads while the tree is being modified limits the options quite a lot. However it would for sure be possible to optimize the initial creation of the tree.

Since then though, the trees were also made Serializable, which might allow trees to be saved and recreated faster (YMMV!). It might also be possible to use a 3rd party Serializer such as Kryo (which is faster than Java’s built-in serialization) to reduce the time to save and recreate trees further.

I’m not sure I understand what you mean about the patching mechanism. The patching mechanism does apply to the root node as well, because all nodes including the root node have the same degree of immutability. The only difference is that the atomic reference to the root node is not in another Node object, as it’s in the RadixTree object instead. So reading threads should always find the root node in a consistent state, just like the non-root nodes.

[knutwannheden]

Hi Niall,

I thought about serialization as well, unfortunately I am not sure that is an option in my case, but I will double check.

What I meant with my question regarding the patching mechanism: In the code it looks like only the immediate parent node will be updated to include a reference to the new / updated child. I would have expected all the parents all the way up to the root to be replaced by new cloned nodes. Otherwise reads won't be "consistent reads" as implemented by RDBMS systems like Oracle. But I see I must just have interpreted the documentation wrong. Possibly it would make sense to make that a bit clearer. And possibly it would make sense to optionally provide this kind of read consistency as well. Of course updates would be much more expensive in an implementation supporting that level of consistency.

[npgall]

Hi Knut,

What do you mean by consistent reads? Using ACID terminology do you mean transaction isolation?

[knutwannheden]

I mean that a query sees a snapshot of the data as it was at the time the query / statement began executing. It is often described in conjunction with the isolation levels. See here how it is defined by some popular RDBMS implementations: http://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_consistent_read and https://docs.oracle.com/cd/B19306_01/server.102/b14220/consist.htm#i17841.

With ConcurrentRadixTree I get the impression that a reading thread which has already started iterating over the result returned by e.g. getValuesForKeysStartingWith() will see "most" updates performed by writing threads. It will see all those modifications it hasn't iterated over yet. Actually a few less, because the Iterator always adds all children to its internal stack in one go.

I just have a hard time wrapping my head around what actual kind of consistency is currently provided by ConcurrentRadixTree.

[npgall]

Hi Knut,

The current level of isolation provided is probably very similar and perhaps identical to READ_COMMITTED isolation as provided by an RDBMS.

There is no guarantee that an ongoing read will see the effects of all other writes which were applied while the read was ongoing. However the writes that it does see, are guaranteed to be fully consistent and atomic.

This seems almost identical to READ_COMMITTED isolation as provided by an RDBMS, because rows which had already been read at this isolation in an RDBMS are not locked, and can therefore be modified before the read completes. So only a subset of writes which occurred during the read may be visible, however those that are visible are also fully consistent and atomic.

[knutwannheden]

Hi Niall,

If you think of calling one of the query methods on ConcurrentRadixTree as opening a transaction and then every call to Iterator#next() on the returned Iterable as separate statement / query within that transaction, I would agree that this corresponds to the isolation level READ COMMITTED.

Intuitively I would rather have thought of a call to a query method on ConcurrentRadixTree as a statement / query and then to have the semantics of "statement-level read consistency" for all results returned by that Iterable. Just like you in a long running DB query don't see the effects of committed transactions which started after the query was started.

But obviously the current consistency semantics work well for your projects. And I now also understand what they are. Sorry for the noise!

[knutwannheden]

I suppose the semantics correspond to how Java defines "weakly consistent" in the java.util.concurrent package documentation: http://docs.oracle.com/javase/8/docs/api/java/util/concurrent/package-summary.html#Weakly. This is for instance what ConcurrentHashMap implements.

What I describe would correspond to the copy-on-write (or sometimes referred to as "fail-safe") as e.g. implemented by CopyOnWriteArrayList.

IMHO it would be great if the ConcurrentRadixTree documentation and Javadoc could include a reference to this terminology and its semantics.

Thanks for your answers!

Could it be interesting to include an implementation with copy-on-write semantics in the project? Maybe even one with fail-fast semantics (i.e. throwing ConcurrentModificationExceptions)?

I realize this discussion is now very much off-topic already!