[
https://issues.apache.org/jira/browse/CASSANDRA-7282?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Benedict reassigned CASSANDRA-7282:
-----------------------------------
Assignee: Benedict
> Faster Memtable map
> -------------------
>
> Key: CASSANDRA-7282
> URL: https://issues.apache.org/jira/browse/CASSANDRA-7282
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Benedict
> Assignee: Benedict
> Fix For: 3.0
>
>
> Currently we maintain a ConcurrentSkipLastMap of DecoratedKey -> Partition in
> our memtables. Maintaining this is an O(lg(n)) operation; since the vast
> majority of users use a hash partitioner, it occurs to me we could maintain a
> hybrid skip list / hash map. The skip list would impose the order on the
> collection, but a hash index would live alongside as part of the same data
> structure, simply mapping into the skip list and permitting O(1) lookups. It
> should be possible to define the hash map to also permit O(1) inserts. Our
> decorated keys are in fact perfectly designed for this scheme.
> At the same time, we can potentially improve the data locality in the skip
> list by baking the initial 64 token bits directly into the structure, and
> storing multiple values per skip list entry to improve cache performance,
> bringing down memory and constant factor cpu overheads.
--
This message was sent by Atlassian JIRA
(v6.2#6252)
