Concurrent-Trees

Concurrent Trees is a Java library providing high-performance, concurrent implementations of Radix Trees and Suffix Trees. It is designed for high-concurrency scenarios where read operations are frequent and must be lock-free, while writes are handled as background or low-concurrency tasks.

Core Data Structures

• Radix Tree: A space-optimized prefix tree. Useful for hierarchical keys (file paths, nested categories), "starts with" lookups, and auto-complete features.
• Suffix Tree: An extension of the Radix Tree that allows looking up any suffix or fragment of a key. Useful for "contains" lookups and finding common substrings across documents.

Concurrency Model

• Lock-free Reads: Reading threads never block, even during active writes, ensuring consistent latency.
• Atomic Updates: Changes are assembled into a patch and applied in a single atomic operation, treating the tree as a mostly-immutable structure. This ensures readers see either the old version or the new version, but never an inconsistent state.
• Write Behavior: Writing threads block each other but do not block reading threads.

The project achieves lock-free reads during concurrent writes using a patching mechanism. Instead of mutating nodes directly, the tree calculates the necessary changes and assembles them into a patch. This patch is applied to the tree in a single atomic operation by replacing an existing node reference in its parent with a new reference to the patch (the new sub-tree).

Key Concurrency Guarantees:

• Consistent Views: Reading threads traversing the tree will always see either the complete old version or the complete new version of a sub-tree. Both versions are guaranteed to be consistent and preserve tree invariants.
• Lock-Free Reads: Because updates are atomic reference swaps, readers do not need to acquire locks to traverse the tree.
• Automatic Cleanup: Old nodes are reclaimed by the standard Java Garbage Collector once all reading threads have finished traversing them and released their references.

To ensure that patches can be applied atomically and remain immutable, the tree nodes follow strict design constraints:

• Mostly-Immutable Nodes: Most properties of a node cannot change once created.
• Edge Representation: Characters for an incoming "edge" (the part of the key associated with a transition from parent to child) are stored within the child node itself rather than in a separate Edge object.
• Immutable Edges: The characters representing an incoming edge and the reference to an associated value are immutable.
• Strict Radix Invariants: To ensure no two outgoing edges from a node share the same first character:
  • The number of outgoing edges from a node is immutable.
  • The only mutable aspect is that a reference to a child node for an existing outgoing edge can be updated to point to a new child node, provided the new child's edge starts with the same first character.
• Atomic Reference Updates: Updating a child node reference for an existing edge is an atomic operation.

Since version 2.0, Concurrent-Trees APIs return java.lang.Iterable instead of java.util.Collection or java.util.Set. This design choice implements Lazy Evaluation, which defers computation until the application actually requests the next element.

Benefits of Lazy Evaluation

• Reduced Latency: The application can access the first matching result immediately without waiting for the entire result set to be assembled.
• Lower Memory Overhead: Results are not pre-computed and stored in a large collection in memory; they are returned to the application as they are found.
• CPU Efficiency: If an application only needs the first few results (e.g., using a break in a loop), no CPU time is wasted computing the remaining matches.
• Efficient Filtering: You can apply additional filtering logic directly inside your iteration loop, which is as efficient as if the library's traversal algorithm performed the filtering.

Iterating through results

You can iterate through the returned Iterable using a standard enhanced for-loop:

Iterable<CharSequence> keysStartingWithFoo = tree.getKeysStartingWith("foo");
for (CharSequence key : keysStartingWithFoo) {
    // Do something with each key...
    System.out.println(key);
}

The project provides several built-in NodeFactory implementations. Choosing the correct one is essential for balancing memory usage and garbage collection behavior:

A ConcurrentSuffixTree<V> allows you to store keys (strings) associated with values of type V. It is optimized for suffix-based searches, including exact matches, suffix matching (keys ending with a pattern), and substring matching (keys containing a pattern).

Core Operations

• Insertion: Use put(String key, V value) to insert a key and its associated value.
• Exact Match: Use getValueForExactKey(String key) to retrieve the value associated with a specific key.
• Suffix Matching (Keys ending with a pattern):
  • getKeysEndingWith(String suffix): Returns an iterable of keys.
  • getValuesForKeysEndingWith(String suffix): Returns an iterable of values.
  • getKeyValuePairsForKeysEndingWith(String suffix): Returns an iterable of key-value pairs.
• Substring Matching (Keys containing a pattern):
  • getKeysContaining(String pattern): Returns an iterable of keys.
  • getValuesForKeysContaining(String pattern): Returns an iterable of values.
  • getKeyValuePairsForKeysContaining(String pattern): Returns an iterable of key-value pairs.

Initialization

To create a new instance, provide a NodeFactory. A common choice is DefaultCharArrayNodeFactory.

SuffixTree<Integer> tree = new ConcurrentSuffixTree<Integer>(new DefaultCharArrayNodeFactory());

SuffixTree<Integer> tree = new ConcurrentSuffixTree<Integer>(new DefaultCharArrayNodeFactory());

tree.put("TEST", 1);
tree.put("TOAST", 2);
tree.put("TEAM", 3);

// Exact match
Integer val = tree.getValueForExactKey("TEST");

// Suffix match (ends with)
Iterable<String> keys = tree.getKeysEndingWith("ST");

// Substring match (contains)
Iterable<String> contains = tree.getKeysContaining("A");