Skip to main content
Department of Information Technology

A Practical Concurrent Binary Search Tree (PPoPP'10)

Nathan G. Bronson, Jared Casper, Hassan Chafi and Kunle Olukotum
Computer Systems Laboratory, Stanford University

Description

Abstract:
We propose a concurrent relaxed balance AVL tree algorithm that is fast, scales well, and tolerates contention. It is based on optimistic techniques adapted from software transactional memory, but takes advantage of specific knowledge of the the algorithm to reduce overheads and avoid unnecessary retries. We extend our algorithm with a fast linearizable clone operation, which can be used for consistent iteration of the tree. Experimental evidence shows that our algorithm outperforms a highly tuned concurrent skip list for many access patterns, with an average of 39% higher single-threaded throughput and 32% higher multi-threaded throughput over a range of contention levels and operation mixes.

Link to the paper

Questions

Question 1:
Describe how the node version numbers are used to validate that a read performed at time t1 is still valid at time t2.

Question 2:
Summarize the hand-over-hand optimistic validation protocol.

Andreas

Q1:
If the version number remains the same, then the read performed at time t1 is still valid at time t2.


Q2:
It is a variation of hand-over-hand locking. The difference is, that the nodes are not locked, but version numbers for each node are used to validate the links. After each descent the version number of the current parent is checked against the version number of the current node, which was read read before.

Jonatan

Q1: "at t1 read the associated version number v1, blocking until the change bit is not set; read the protected value x; then at t2 reread the version number v2. If v1 = v2, then x was still valid at t2."


Q2: Separate version numbers are kept for the left and right child link. The hand over hand validation is like hand over hand locking, but applied to version numbers. To navigate through a node, the parent link and its version is read. Thereafter, the child link and its version number is read. Thereafter the parent version is validated. If still valid, it's ok to proceed descending.

Martin

Q1: The version number is changed when the node is changed. So at time t1, one first reads the version
(ands wait if the version indicates that the node is currently being updates), and then reads the value.
Then at t2, to verify that the node was not updated, one reads the version again. If the version has not
changed, the read performed at t1 is still valid.


Q2: While traversing nodes in the tree, it will check the validity of each link by the version numbers
as described above. To pass a node, the inbound and outbound edge both need to be valid at the same time,
so the protocol will have overlapping intervals where it checks that the links did not change. That these
intervals overlap is the reason it is called "hand-over-hand". The "optimistic" keyword is because links
are expected to be unchanged, and when a potential dangerous modification is detected, the algorithm will
backtrack and retry. To contrast, a "pessimistic" approach would be to instead make sure that no other
thread could change the links while they are traversed.

Kjell

Q1: To check that a read of a node performed at t0 is still valid at t1 the version number is read before t0 and then again after t1. If the the version number has not changed between the reads, the read of the the node performed at t0 is still valid at t1.


Q2: The links between nodes have version numbers. At time t0 (before traversing link X), the version number of link X is read. Link X's version number is read again at time t1 after the value of the node at the end of link X has been read. The value of the link version number read at t0 and t1 is compared (after t1). Based on the comparison it is decided if the algorithm shall backtrack to the previous node or not.

Pan

Q1: If the version numbers are the same at t1 and t2, it means the read performed at t1 is still valid at t2. A changing bit is used to indicate the data is being written. When reading the version number, the operation blocks until the changing bit is not set (no one is writing the data).
Q2:

Sofia

Q1: At t1 the version number is read, then the protected value. At t2 the version number is read again. If it is the same as the version number at t1, then the read at t1 is still valid.


Q2: In the tree, links are marked with version numbers to track changes to left and right child nodes. Links are validated as in Q1. In order to pass through a node, both the incoming and outgoing edge must be valid at the same time, so the incoming edge is validated after the outgoing edge.

Afshin

Q1. To perform a read at time t1 and verify that the read is still valid at t2: at t1 read the associated version number v1, blocking until the change bit is not set; read the protected value x; then at t2 reread the version number v2. If v1 = v2 then x was still valid at t2.



Q2. There is an implicit state of a search, which is an open interval of keys that must either be absent from the entire tree or present in the current subtree. Each time that the search process performs a comparison and navigates downward, the interval is reduced. At all times the interval includes the target key, so if the subtree ever becomes empty we can conclude that no node with that key is present.

Yunyun

Q1: If the version numbers v1 (at time t1) and v2 (at time t2) are the same, then the value read at t1 is still valid at t2.


Q2: The left and the right links of each node are marked with version numbers. To validate the search of a node, both links of the node must be validated as described above. If the node is valid, then the search can pass. Otherwise, it has to backtrack.

Stavros

Q1: Reading sequence: Read version number -> wait until change bit is reset -> read data -> re-read version number and compare. In this way, any changes that happen will be noticed by the difference in the version numbers.


Q2: The commit action of each transaction happens after the initialization action of the next transaction. Therefore a failing transaction will conceptually undo the commit of the previous, which will then have to be retried.

Updated  2013-05-29 15:24:15 by Stavros Aronis.