How we improved APM Java startup by encoding a prefix trie as a JVM constant
Startup performance is critical for users, developers, and cloud costs, but Java APM instrumentation must balance observability against the overhead of transforming classes. Datadog reduced class-matching overhead by 30% over four years by optimizing the first filtering stage: matching class-name prefixes. Its main innovation was encoding a prefix trie as a single JVM string constant, avoiding the startup cost of constructing a conventional trie. ## Java Instrumentation and Class Matching - Java APM uses the Java Instrumentation API to intercept and transform classes as they load. - Instrumentation adds method advice that records method execution and propagates tracing context. - Instrumenting every method would be too expensive, so APM first identifies valuable classes. - Applications may load tens or hundreds of thousands of classes, making efficient filtering important. - Class-name and package-prefix checks are cheaper than structural or hierarchy-based checks because they avoid parsing class files. - Datadog therefore begins with a curated ignore list of class and package prefixes. ## Startup Constraints in `premain` - Agents register transformers in the JVM’s `premain` phase, before the application’s `main` method. - At this point: - Few classes have been loaded. - The JIT compiler is cold or unavailable, especially on Java 8. - Code runs interpreted and unoptimized. - Loading or calling certain JDK classes can have irreversible side effects. - For example, touching `java.util.logging` initializes `LogManager`, potentially preventing an application from configuring its own logging manager later. - These constraints make ordinary data loading, parsing, and object construction undesirable during startup. ## Replacing a Hand-Written Matcher with a Trie - Datadog’s earlier matcher used a complex nested code structure to represent prefixes. - Although flexible, it was difficult to maintain and required special optimizations for Java 8 startup. - A trie was a natural replacement because it shares common characters among prefixes and supports efficient lookup. - A conventional trie would require: - Locating and reading a resource. - Parsing its contents. - Constructing trie nodes. - Loading additional code or dependencies. - Those operations would impose unacceptable costs during `premain`. ## Encoding the Trie as a JVM Constant - Datadog created `ClassNameTrie`, which stores the entire prefix trie in a Java string constant. - The JVM loads the encoded data with a single `ldc` bytecode instruction. - This approach avoids resource I/O and runtime trie construction. - Embedding the data in the class also makes it resilient to repackaging. - The compact representation improves cache locality and reduces startup work. ## Compact Node Representation - Java strings contain 16-bit `char` values, allowing each character to encode one of 65,536 possible values. - Each trie node stores: - A character indicating the number of branches. - Sorted branch characters, enabling binary search. - One value character per branch. - Value characters encode different outcomes: - **Leaf:** returns a definitive result and ends the search. - **Bud:** records a possible result but permits further matching. - **Inline segment length:** indicates that additional prefix characters are stored directly. - Buds and leaves can include a **glob bit**, allowing a match to apply even when extra characters remain in the class name. - The encoding reserves the remaining value range for match results, with a maximum stored value of 8,191. The broader lesson is that startup-sensitive JVM code may benefit from moving computation into class-loading time and representing lookup structures in compact constants. For Java agents, precomputed, dependency-free data structures can deliver trie-like performance without the initialization and JIT costs of building them at runtime.
Read original(opens in new tab)
