cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Burman (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-7282) Faster Memtable map
Date Thu, 05 Jul 2018 12:14:00 GMT

    [ 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-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org


Mime
View raw message