LSM range scan after deletes

You run an LSM-based wide-column store (Cassandra/HBase style) and a high-delete, range-scan workload is misbehaving: a partition that holds a queue (rows inserted then deleted as they're processed) is getting slower and slower to scan even though it's logically near-empty. Design how the storage engine should handle deletes and range reads so this doesn't happen, and explain the underlying mechanics. Assume sustained writes plus deletes and frequent range scans over recently-touched partitions.