A Contention-Friendly, Non-Blocking Skip List

Abstract : This paper presents a new non-blocking skip list algorithm. The algorithm alleviates contention by localizing synchronization at the least contended part of the structure without altering consistency of the implemented abstraction. The key idea lies in decoupling a modification to the structure into two stages: an eager abstract modification that returns quickly and whose update affects only the bottom of the structure, and a lazy selective adaptation updating potentially the entire structure but executed continuously in the background. As non-blocking skip lists are becoming appealing alternatives to latch-based trees in modern main-memory databases, we integrated it into a main-memory database benchmark, SPECjbb. On SPECjbb as well as on micro-benchmarks, we compared the performance of our new non-blocking skip list against the performance of the JDK non-blocking skip list. Results indicate that our implementation is up to 2:5 faster than the JDK skip list.
Type de document :
Rapport
[Research Report] RR-7969, INRIA. 2012
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00699794
Contributeur : Tyler Crain <>
Soumis le : vendredi 16 novembre 2012 - 14:56:13
Dernière modification le : jeudi 15 novembre 2018 - 11:57:36
Document(s) archivé(s) le : samedi 17 décembre 2016 - 11:14:22

Fichier

techReport_v3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00699794, version 4

Citation

Tyler Crain, Vincent Gramoli, Michel Raynal. A Contention-Friendly, Non-Blocking Skip List. [Research Report] RR-7969, INRIA. 2012. 〈hal-00699794v4〉

Partager

Métriques

Consultations de la notice

1065

Téléchargements de fichiers

1071