🍋: A General Lock following paper "Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method"

Related tags

Learning Resources concurrency lock rust-lang lock-free readwritelock
Overview

Optimistic Lock Coupling

CI docs.rs

from paper "Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method"

In actual projects, there are some lock-free data structures, especially database-related ones such as BwTree, Split-Ordered List (also known as Lock Free HashTable) when there are many write conflicts. The performance loss is very serious, and sometimes it is not as good as the brainless Mutex. However, the performance of the brainless Mutex is often very bad under normal circumstances, so is there an intermediate form that can solve this problem?

This is the intermediate form. So this can be used everywhere as a general lock, and the performance is satisfactory.

But I have a lock-free data structure that is well designed and optimized for usage scenarios. Can’t it be your implementation?

Of course, this is better, but when you don't have 114514 PHD students to optimize your data structure, and you don't have 1919810 powerful debugging masters to deal with problems such as Memory Order, it will be tricky.

At this time, my project is already online, the investor has given me money.

So what are the disadvantages of such a data structure?

Of course there is~

The disadvantage of this data structure is mainly because of the use of a 61bit version, when this version is full, we can lie flat. Of course, your data structure is crazy to change to this binary, it should be a problem for you to write the code.

Bench Mark

source code is under \benches dir. you can run it on your own~

Bench Result on my MacOS 2.3 GHz Intel Core i5 Images

  • heavy read hr
  • heavy write hw
  • read only ro
  • write only wo

Drawback

The shortcomings of optimistic lock are obvious. When there is a serious conflict, it will be slammed by Mutex and others. But when read > write, optimistic locking works better.

Lock Usage

when 3 reader core and 2 writer core

removed intermediate part of blocking log

Operation Delta Time ThreadID Status
Read 142869 ThreadId(6) OptimisticLockCouplingReadGuard { version: 0, data: 1 }
ErrRead 216320 ThreadId(6) failed to sync
ErrRead 222578 ThreadId(6) Blocked
ErrRead 241218 ThreadId(6) Blocked
Write 145456 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 0, data: 1 }
Write 291942 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 1, data: 2 }
Write 312349 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 2, data: 3 }
ErrWrite 147945 ThreadId(3) Blocked
ErrWrite 530522 ThreadId(3) Blocked
Write 319592 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 3, data: 4 }
Write 548172 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 4, data: 5 }
Write 605291 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 5, data: 6 }
Write 613679 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 6, data: 7 }
Write 618416 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 7, data: 8 }
Write 623453 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 8, data: 9 }
Write 627723 ThreadId(2) OptimisticLockCouplingWriteGuard { version: 9, data: 10 }
ErrWrite 536923 ThreadId(3) Blocked
Write 696435 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 10, data: 11 }
Write 704458 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 11, data: 12 }
Write 712664 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 12, data: 13 }
Write 718093 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 13, data: 14 }
Write 749839 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 14, data: 15 }
Write 755558 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 15, data: 16 }
ErrRead 149826 ThreadId(5) Blocked
ErrRead 805119 ThreadId(5) Blocked
ErrRead 810206 ThreadId(5) Blocked
Write 775039 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 16, data: 17 }
Write 871475 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 17, data: 18 }
Write 891289 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 18, data: 19 }
Write 896488 ThreadId(3) OptimisticLockCouplingWriteGuard { version: 19, data: 20 }
ErrRead 273387 ThreadId(6) Blocked
Read 925559 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 971184 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 994963 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 998833 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1002179 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1005515 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1008870 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
ErrRead 831229 ThreadId(5) Blocked
Read 1055143 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1076076 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1080036 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1083564 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1086850 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1090126 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1093422 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1110135 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1115111 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1118556 ThreadId(5) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1038825 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1142881 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1146449 ThreadId(6) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
ErrRead 148865 ThreadId(4) Blocked
Read 1197872 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1217034 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1220737 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1224141 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1227430 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1230666 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1233888 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1237159 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1240422 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
Read 1243714 ThreadId(4) OptimisticLockCouplingReadGuard { version: 20, data: 20 }
You might also like...
Simple retro game made using Rust bracket-lib by following "Herbert Wolverson's Hands on Rust" book.

Flappy Dragon Code from This program is a result of a tutorial i followed from Herbert Wolverson's Hands-on Rust Effective Learning through 2D Game De

Praneeth Chinthaka Ranasinghe 1 Feb 7, 2022
Cryptocurrencies trend-following trading bot sandbox written in Rust.

Trend trading bot Experiments repo about (crypto) trend trading. By "trend" I mean trading following the trend using technical indicators (vs other ki

Julien 6 Oct 2, 2022
A following of the book: Zero to Production In Rust

A following of the book: Zero to Production In Rust

Zack Penn 2 Mar 19, 2022
simple but convenient CLI-based Nostr client app for following users and sending DMs

nostr-commander-rs TLDR: simple but convenient CLI-based Nostr client app for publishing, sending DMs, as well as following users and channels nostr-c

null 18 Dec 30, 2022
Following "ZK HACK III - Building On-chain Apps Off-chain Using RISC Zero"

RISC Zero Rust Starter Template Welcome to the RISC Zero Rust Starter Template! This template is intended to give you a starting point for building a

drCathieSo.eth 3 Dec 22, 2022
💩 Small HTTP client for the Webpurify API following the sans-io approach 🦀

💩 tame-webpurify Super simple client for the WebPurify REST API What is this? An incredibly small library to interact with the https://www.webpurify.

Embark 8 May 1, 2023
An attempt to start documenting the rust sdk for temporal and how to use it following some of the examples in typescript

This is an attempt to start documenting the rust sdk for temporal and how to use it following some of the examples in typescript.

Cosm 5 May 24, 2023
An implementation of Joshua Yanovski's Ghost Cell paper.

A novel safe and zero-cost borrow-checking paradigm from the GhostCell paper. Motivation A number of collections, such as linked-lists, binary-trees,

null 350 Dec 22, 2022
Instance Distance is a fast pure-Rust implementation of the Hierarchical Navigable Small Worlds paper

Fast approximate nearest neighbor searching in Rust, based on HNSW index

Instant Domain Search, Inc. 135 Dec 24, 2022
This repo contains the schedule for summer paper meetup

21' Summer 💙 Paper Meetup Annoucement 📢 6/21/2021: our first summer love paper meetup will start on July 10th, 2021. Papers to contribute 🥂 Check o

msft system virtual meetup 24 Sep 22, 2022
HNSW ANN from the paper "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs"

hnsw Hierarchical Navigable Small World Graph for fast ANN search Enable the serde feature to serialize and deserialize HNSW. Tips A good default for

Rust Computer Vision 93 Dec 30, 2022
Source code for our paper
Source code for our paper "Higher-order finite elements for embedded simulation"

Higher-order Finite Elements for Embedded Simulation This repository contains the source code used to produce the results for our paper: Longva, A., L

Interactive Computer Graphics 18 Sep 30, 2022
Multilayered Linkable Spontaneous Anonymous Group - Implemented as is from paper. Not Monero specific

MLSAG This is a pure Rust implementation of the Multilayered Linkable Spontaneous Anonymous Group construction. This implementation has not been revie

Crate Crypto 19 Dec 4, 2022
e-paper/e-ink monitor linux driver
e-paper/e-ink monitor linux driver

Ardoise: e-paper/e-ink monitor Goal: Create a e-paper/e-ink monitorfor linux. My personal use is a typewriter. Written in Rust Latency is 0,2s when th

Cyril Jacquet 1 Dec 8, 2022
Hamming Weight Tree from the paper Online Nearest Neighbor Search in Hamming Space

hwt Hamming Weight Tree from the paper Online Nearest Neighbor Search in Hamming Space To understand how the data structure works, please see the docs

Rust Computer Vision 7 Oct 9, 2021
fast rust implementation of online nonnegative matrix factorization as laid out in the paper "detect and track latent factors with online nonnegative matrix factorization"

ONMF status: early work in progress. still figuring this out. code still somewhat messy. api still in flux. fast rust implementation of online nonnega

null 2 Apr 10, 2020
An implementation of the paper
An implementation of the paper "Honey Badger of BFT Protocols" in Rust. This is a modular library of consensus.

Honey Badger Byzantine Fault Tolerant (BFT) consensus algorithm Welcome to a Rust library of the Honey Badger Byzantine Fault Tolerant (BFT) consensus

null 335 Dec 25, 2022
A command line application which sets your wall paper with new image generating pollens once they arrive.

pollenwall Table of Contents pollenwall About Installation Binary releases Build from source Usage Command Line Arguments Running as a service MacOS L

Pollinations.AI 2 Jan 7, 2022
An Rust implementation of the Modified Merkle Patricia Tree described by ETH Yellow Paper

Merkle Patricia Tree的Rust实现 博客文章：https://dere.press/2022/01/24/eth-trie/ 本实现参考下列项目： https://ethereum.github.io/yellowpaper/paper.pdf https://github.co

M4tsuri 3 Dec 13, 2022
Comments
  • cargo clippy

    cargo clippy

    参考slice::len源码

    以下代码用const fn + #[inline]即可，没必要inline(always)

    #[inline]
const fn is_locked(version: u64) -> bool {
    version & 0b10 != 0
}

    不需要inline的函数?

    我的建议是，涉及IO操作例如数据库读写的不要加inline

    warning: you have declared `#[inline(always)]` on `fmt`. This is usually a bad idea
   --> src/lib.rs:385:5
    |
385 |     #[inline(always)]
    |     ^^^^^^^^^^^^^^^^^
    |
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#inline_always

    像这个提示fmt不要inline挺好的，虽然fmt没有IO操作，但有内存分配这种比较耗时的操作吧

    declared #[inline(always)] on fmt. This is usually a bad idea

    opened by pymongo 0
Releases(0.2.5)
Owner
LemonHX
🍋 檸檬さんは檸檬さんの檸檬です
LemonHX
GitHub https://docs.rs/optimistic_lock_coupling/
An attempt to start documenting the rust sdk for temporal and how to use it following some of the examples in typescript

This is an attempt to start documenting the rust sdk for temporal and how to use it following some of the examples in typescript.

Cosm 5 May 24, 2023
This repo contains the schedule for summer paper meetup

21' Summer ?? Paper Meetup Annoucement ?? 6/21/2021: our first summer love paper meetup will start on July 10th, 2021. Papers to contribute ?? Check o

msft system virtual meetup 24 Sep 22, 2022
fast rust implementation of online nonnegative matrix factorization as laid out in the paper "detect and track latent factors with online nonnegative matrix factorization"

ONMF status: early work in progress. still figuring this out. code still somewhat messy. api still in flux. fast rust implementation of online nonnega

null 2 Apr 10, 2020
A lock-free, partially wait-free, eventually consistent, concurrent hashmap.

A lock-free, partially wait-free, eventually consistent, concurrent hashmap. This map implementation allows reads to always be wait-free on certain pl

Ian Smith 216 Nov 18, 2022
Gecko is a high-level, general-purpose programming language built on top of the LLVM project.

Gecko is a high-level, general-purpose programming language built on top of the LLVM project. Gecko Technology & principles Gecko is a general-purpose

Gecko 19 Oct 3, 2022
An OOP programming language I am making by following Crafting Interpreters.

horba An OOP programming language I am making by following Crafting Interpreters. https://craftinginterpreters.com/ I intend it to have a somewhat C-s

Thomas 3 Dec 5, 2021
Following along with the Geometry Processing with Intrinsic Triangulations course in Rust.

Intrinsic Triangulations in Rust In this repo is code I wrote following along with the Nicholas Sharp, Mark Gillespie, Keenan Crane's course on geomet

Lukas Hermann 8 Nov 16, 2021
An iterator following a space-filling pattern over a given range

rlp-iter rlp-iter (Resolving Lattice Point Iterator) is an iterator that returns a space-filling permutation of integers in a given range. Specificall

Nathan Essex 1 May 27, 2022
Blackjack is a procedural modelling application, following the steps of great tools like Houdini or Blender's geometry nodes project

Blackjack Your Rusty ?? procedural 3d modeler Blackjack is a procedural modelling application, following the steps of great tools like Houdini or Blen

null 1.1k Jan 3, 2023
Extreme Bevy is what you end up with by following my tutorial series on how to make a low-latency p2p web game.

Extreme Bevy Extreme Bevy is what you end up with by following my tutorial series on how to make a low-latency p2p web game. There game can be played

Johan Klokkhammer Helsing 39 Jan 5, 2023