Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@cassandra.apache.org
Date: Sat, 13 Sep 2014 03:57:34 +0000 (UTC)
From: "Aleksey Yeschenko (JIRA)" <jira@apache.org>
To: commits@cassandra.apache.org
Message-ID: <JIRA.12715826.1400697535000.25677.1410580654865@Atlassian.JIRA>
In-Reply-To: <JIRA.12715826.1400697535000@Atlassian.JIRA>
References: <JIRA.12715826.1400697535000@Atlassian.JIRA>
 <JIRA.12715826.1400697535854@arcas>
Subject: [jira] [Commented] (CASSANDRA-7282) Faster Memtable map
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ https://issues.apache.org/jira/browse/CASSANDRA-7282?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14132511#comment-14132511 ] 

Aleksey Yeschenko commented on CASSANDRA-7282:
----------------------------------------------

True, but the new more complex code replacing the old code tested by years of production stays there for all the use cases. So maybe you want to benchmark both the niche and the general use case as well - to make a decision whether or not a particular change is justified. (No idea if it is or it isn't in this case, but would love to see some real world data on this).

> 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: reads.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)