[
https://issues.apache.org/jira/browse/CASSANDRA-7282?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14385740#comment-14385740
]
Benedict commented on CASSANDRA-7282:
-------------------------------------
bq. +1 for massive understatement.
Thanks. I spent a day working on just that, so glad it panned out :)
I'm currently leaning towards postponing this ticket until 3.1, since some
careful consideration is needed to ensure a uniform distribution of hash keys
within the map, especially without vnodes on large clusters. It's possible we
could only enable this optimisation on nodes that can predict their
distribution will be fair. In either case I think it may be helpful to consider
the ticket in relation to CASSANDRA-7032 and CASSANDRA-6696, by e.g. having a
separate hash table for each vnode range. Depending on 3.0 release timeline,
the incorporation of these tickets, and on the progression of my other
commitments, I may still aim to deliver this in 3.0, but just alerting that at
the moment my view is this is uncertain and on balance less than likely.
> 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
> Labels: performance
> Fix For: 3.0
>
> Attachments: jasobrown-sample-run.txt, profile.yaml, reads.svg,
> run1.svg, writes.svg
>
>
> 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 ordered list / hash map. The list would impose the normal order on the
> collection, but a hash index would live alongside as part of the same data
> structure, simply mapping into the list and permitting O(1) lookups and
> inserts.
> I've chosen to implement this initial version as a linked-list node per item,
> but we can optimise this in future by storing fatter nodes that permit a
> cache-line's worth of hashes to be checked at once, further reducing the
> constant factor costs for lookups.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
