Problem:

The follower-mode layered-table truncate list is a flat in-memory linked list that is currently always traversed end-to-end (time complexity of N). The current concern is that as the number of entries grows, the searching is expensive and not performant. It is not immediately clear if there is a performance bottleneck is here, or if there is simply a better data structure to use here. Some candidates are: (augmented) skip list, using a WT table, Bloom filter or having a separate committed/uncommitted linked list.

Context:

WT-16789 introduced some performance metrics, specifically how many elements were traversed, and how many times a search function is called.

Scope:

• Run benchmarking and evaluate from the statistics if there is a performance bottleneck
• Determine potential data structure candidates for improving searches and/or simplification of the truncate-list code