[CASSANDRA-8414] Avoid loops over array backed iterators that call iter.remove()

• Type: Improvement
• Status: Resolved
• Priority: Normal
• Resolution: Fixed
• Fix Version/s: 2.0.13, 2.1.3
• Labels: performance
• Assignee: Jimmy Mårdell Assign to me
• Reporter: Richard Low

Authors

Jimmy Mårdell

Reviewers

Richard Low

• Created: 03/Dec/14 17:20
• Updated: 16/Apr/19 09:31
• Resolved: 22/Jan/15 00:29

Description

I noticed from sampling that sometimes compaction spends almost all of its time in iter.remove() in ColumnFamilyStore.removeDeletedStandard. It turns out that the cf object is using ArrayBackedSortedColumns, so deletes are from an ArrayList. If the majority of your columns are GCable tombstones then this is O(n^2). The data structure should be changed or a copy made to avoid this.