[GitHub] [trafficserver] masaori335 opened a new pull request, #9394: Add BRAVO Reader-Writer Lock

[via GitHub]

masaori335 opened a new pull request, #9394:
URL: https://github.com/apache/trafficserver/pull/9394

   # Abstract
   
   Introduce `ts::bravo::shared_mutex` as an alternative to the 
`std::shared_mutex` or `pthread_rwlock_t`.
   
   As we know, `std::shared_mutex` or `pthread_rwlock_t` (almost equivalent on 
Linux) doesn't scale on a multi-thread application like ATS. BRAVO is a 
reader-writer lock algorithm published by Dave Dice and Alex Kogan at USENIX 
2019[*1]. The algorithm acts as an accelerator layer for the reader lock. 
Please note that this doesn't accelerate the writer lock, but almost no 
penalty. This algorithm is useful for read-heavy use cases. For the details of 
the algorithm, please check the paper.
   
   # Implementation
   
   The puzpuzpuz/xsync's `RBMutex` is an algorithm implementation in go-lang. 
`ts::bravo::shared_mutex` followed it in C++.
   
   ## Exclusive locking (writer)
   
   `ts::bravo::shared_mutex` can be a drop-in replacement.
   ```
   ts::bravo::shared_mutex mutex; 
   std::lock_guard lock(mutex);
   ```
   
   ## Shared locking (reader)
   
   To handle `ts::bravo::Token`, it needs `ts::bravo::shared_lock`, but you can 
use it like `std::shared_lock`.
   ```
   ts::bravo::shared_mutex mutex; 
   ts::bravo::shared_lock lock(mutex);
   ```
   
   # Micro Benchmark
   
   `benchmark_shared_mutex.cc` is Catch2 based micro benchmark tool. You can 
adjust threads and the rate of reading and writing.
   
   ```
   $ taskset -c 0-63 ./benchmark_shared_mutex --ts-nthreads 64 --ts-nloop 1000 
--ts-nread 100 --ts-nwrite 1
   ```
   
   ## read: 1000, write: 0
   
     | ts::shared_mutex | ts::bravo::shared_mutex
   -- | -- | --
   1 | 4.36742 | 1.09271
   2 | 76.5058 | 1.08926
   4 | 126.713 | 1.11642
   8 | 232.651 | 1.18535
   16 | 498.872 | 1.80362
   32 | 1012.19 | 2.17977
   64 | 2172.4 | 5.7694
   <img width="535" alt="Screenshot 2023-02-09 at 15 20 18" 
src="https://user-images.githubusercontent.com/741391/217733963-77c9d910-b303-4387-aa6d-192eaae24dca.png";>
   
   ## read: 1000, write: 1
   
     | ts::shared_mutex | ts::bravo::shared_mutex
   -- | -- | --
   1 | 4.3714 | 3.19028
   2 | 59.3886 | 17.5586
   4 | 132.736 | 53.6457
   8 | 249.857 | 112.068
   16 | 586.322 | 128.144
   32 | 1375.09 | 227.752
   64 | 5240.33 | 1301.71
   
   <img width="535" alt="Screenshot 2023-02-09 at 15 20 27" 
src="https://user-images.githubusercontent.com/741391/217733992-a03d087b-0c88-4c6b-8e60-ab3b03373cdd.png";>
   
   # References
   
   [*1] Dave Dice and Alex Kogan. 2019. BRAVO: Biased Locking for Reader-Writer 
Locks. In Proceedings of the 2019 USENIX Annual Technical Conference (ATC). 
USENIX Association, Renton, WA, 315–328.
   https://www.usenix.org/conference/atc19/presentation/dice
   
   [*2] xsync - Concurrent data structures for Go
    https://github.com/puzpuzpuz/xsync


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscr...@trafficserver.apache.org

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org