[ https://issues.apache.org/jira/browse/CASSANDRA-7282?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14019075#comment-14019075 ]
Benedict commented on CASSANDRA-7282: ------------------------------------- [~enigmacurry] how easy would it be to kick off a quick comparison of this with stock? Do we have any hardware that's unoccupied? > 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 > Fix For: 3.0 > > > 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 skip list / hash map. The skip list would impose the order on the > collection, but a hash index would live alongside as part of the same data > structure, simply mapping into the skip list and permitting O(1) lookups. It > should be possible to define the hash map to also permit O(1) inserts. Our > decorated keys are in fact perfectly designed for this scheme. > At the same time, we can potentially improve the data locality in the skip > list by baking the initial 64 token bits directly into the structure, and > storing multiple values per skip list entry to improve cache performance, > bringing down memory and constant factor cpu overheads. -- This message was sent by Atlassian JIRA (v6.2#6252)