[SERVER-84080] Replace hash table with new model for greater fine grained locks Created: 12/Oct/23  Updated: 19/Dec/23

Status: Backlog
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Improvement Priority: Major - P3
Reporter: Francisco Casas Assignee: Backlog - Service Architecture
Resolution: Unresolved Votes: 0
Labels: perf
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
Assigned Teams:
Service Arch
Participants:

 Description   

Improve current hashing mechanism to allow for fine grained locks along the lines of Oracle’s Latching, RBS and redo logs mechanism allowing higher concurrency through non-blocking reads when write is required.

*Sample papers reviewed by Performance Engineering.
growt (GrowTable) is a header only library implementing a concurrent growing hash table
https://github.com/TooBiased/growt
parlayhash : A Header Only Fast Concurrent Hash Table.
https://github.com/cmuparlay/parlayhash/tree/main

Other Hash Tables
https://github.com/BlazingPhoenix/concurrent-hash-map (libcuckoo)
https://github.com/GLaDOS-418/threading_library - sharded locks

Papers:
https://www.cs.princeton.edu/~mfreed/docs/cuckoo-eurosys14.pdf
https://www.liblfds.org/downloads/white%20papers/[Hash]%20-%20[Michael]%20-%20High%20Performance%20Dynamic%20Lock-Free%20Hash%20Tables%20and%20List-Based%20Sets.pdf
http://erdani.org/publications/cuj-2004-12.pdf

Other
https://github.com/cmuparlay/concurrent_deferred_rc
https://github.com/cmuparlay/parlaylib
https://www.liblfds.org/



 Comments   
Comment by Jason Chan [ 19/Dec/23 ]

We think the motivations of this ticket is similar to PM-3089. Putting this ticket in the backlog for now to see if we want to revisit the hash table performance evaluation here.

Generated at Thu Feb 08 06:53:59 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.