[
https://issues.apache.org/jira/browse/CASSANDRA-7282?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16533582#comment-16533582
]
Michael Burman commented on CASSANDRA-7282:
-------------------------------------------
Out of range tokens were also important for system tables as they do not follow
the normal ranges. I agree that this type of information should not be inside
the Memtable, but outside the Memtable. I however designed the patch to be
"plug-in" without touching other parts too much. There's certainly going to be
more overhead for one memtable per range, but that might not be an issue
depending on the amount of vnodes per node. Which then is part of the reason
for your next question. The tree is certainly an overkill, but I made it
because it behaves more predictably with the amount of vnodes currently in use:
{code:java}
[java] Benchmark (vnodes) Mode Cnt Score Error
Units
[java] BSTBench.binarySeek 4 thrpt 16 122117.853 ± 6815.672
ops/ms
[java] BSTBench.binarySeek 16 thrpt 16 22711.007 ± 691.020
ops/ms
[java] BSTBench.binarySeek 64 thrpt 16 4547.383 ± 180.749
ops/ms
[java] BSTBench.binarySeek 256 thrpt 16 892.406 ± 42.791
ops/ms
[java] BSTBench.binarySeek 512 thrpt 16 224.545 ± 6.469
ops/ms
[java] BSTBench.linearSearch 4 thrpt 16 214901.639 ± 3264.386
ops/ms
[java] BSTBench.linearSearch 16 thrpt 16 19594.770 ± 718.201
ops/ms
[java] BSTBench.linearSearch 64 thrpt 16 1302.657 ± 43.841
ops/ms
[java] BSTBench.linearSearch 256 thrpt 16 105.317 ± 2.950
ops/ms
[java] BSTBench.linearSearch 512 thrpt 16 25.932 ± 3.488
ops/ms
[java] BSTBench.treeSeek 4 thrpt 16 162053.915 ± 4228.035
ops/ms
[java] BSTBench.treeSeek 16 thrpt 16 31650.599 ± 789.500
ops/ms
[java] BSTBench.treeSeek 64 thrpt 16 5901.952 ± 137.575
ops/ms
[java] BSTBench.treeSeek 256 thrpt 16 1055.737 ± 22.786
ops/ms
[java] BSTBench.treeSeek 512 thrpt 16 208.169 ± 4.617
ops/ms
{code}
(The above test creates vnodes size of token ranges and then tries to find each
one in a random order) And the amount of code for binary search vs tree search
is almost equivalent. But between 4-256 it is a fast method (with linear search
being the quickest one for very small amount of token ranges). So I thought it
as a best "compromise".
> Faster Memtable map
> -------------------
>
> Key: CASSANDRA-7282
> URL: https://issues.apache.org/jira/browse/CASSANDRA-7282
> Project: Cassandra
> Issue Type: Improvement
> Reporter: Benedict
> Assignee: Michael Burman
> Priority: Major
> Labels: performance
> Fix For: 4.x
>
> 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
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
