Uploaded image for project: 'Cassandra'
  1. Cassandra
  2. CASSANDRA-7282

Faster Memtable map

    XMLWordPrintableJSON

    Details

      Description

      Currently we maintain a ConcurrentSkipLastMap of DecoratedKey -> Partition in our memtables. Maintaining this is an O(lg) 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.

        Attachments

        1. jasobrown-sample-run.txt
          102 kB
          Jason Brown
        2. profile.yaml
          0.7 kB
          Benedict Elliott Smith
        3. reads.svg
          322 kB
          Benedict Elliott Smith
        4. run1.svg
          1.07 MB
          Benedict Elliott Smith
        5. writes.svg
          210 kB
          Benedict Elliott Smith

          Activity

            People

            • Assignee:
              burmanm Michael Burman
              Reporter:
              benedict Benedict Elliott Smith
              Authors:
              Michael Burman
              Reviewers:
              Benedict Elliott Smith
            • Votes:
              0 Vote for this issue
              Watchers:
              23 Start watching this issue

              Dates

              • Created:
                Updated: