[ 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