Harris Linked List

어느 블로그에서 본 글

저 소스에 따르면 Concurrency 관련 논문들을 읽지 않는 이상 이게 뭔지 보통 모를 거래요. 왜냐? 가장 빠르고 단순한 Non blocking Linked list이지만, 실용적이지는 않다네요.

Harris 링크드리스트에서 head와 tail 노드는 항상 존재합니다. 지워지지 않아요.

이 소스의 저자는 해리스 링크드리스트가 중국 직소 퍼즐(본문의 사진으로 유추하건대 캐스트퍼즐을 말하는 거 같아요) 같대요. 갖고 놀다가 우연히 풀 수도 있지만 막상 각잡고 맞춰보려면 간단한 트릭을 못 풀어 몇시간 걸리는 그런 퍼즐 말이에요.

해리스 링크드 리스트에서 가장 대표적인 트릭은 next node를 가리키는 포인터에 tag를 다는 거에요. tag는 least significant 1 bit를 사용하는데 (이유는 노드가 align되어있기 때문) 이 tag를 통해 이 다음 노드가 삭제된 노드인지(dealloc되지는 않았더라도 논리적으로 지워졌다고 적고 가는거죠) 판단합니다.

근데 여기서 프랙티컬한 문제가 생긴대요.

많은 고급 언어에서는(like Java, Scala, C#, etc) 포인터 비트연산이 안된다네요. 뭐 저희 수업은 Rust로 진행되고 이런 위험한 연산들은 crossbeam이 다 해주니 이 문단을 넘어갑시다.

아 다 읽고나니 harris linked list의 이해에는 도움이 하나도 안 되는 페이지였습니다...

위키피디아의 문서

source

2001년 해리스는 cas를 이용해 nonblocking ordered linked list를 만듭니다. p 다음 n을 넣는 과정은 다음과 같아요.

next ← p.next
n.next ← next
(p.next).cas(next, n)
cas가 실패하면 1로 갑니다.

하지만 p.next를 지우는건 간단하지 않아요. 나이브한 방법은 그냥 CAS로 다른 스레드 신경 안쓰고 지워버리는 것이지만, 이러면 다른 스레드에서 insert할 때 데이터를 잃을 수도 있대요.

이 그림은 그런 상황을 나타내는데, a다음 b를 추가하는 것과 동시에 a를 지운 상황이에요. 점선은 중간 단계, 실선은 최종상황을 말합니다. 분명 head->b->c가 되어야 할텐데 b 추가가 안 되어 버렸죠.

그래서 두번의 cas가 필요합니다. 먼저 p.next에 지워졌다고 태그를 합니다. (tagging은 위에서 설명한대로 마지막 비트를 사용해요) 그리고 다음 진짜로 p.next를 지워버리는거에요.

진짜 논문

source

결국 부족한 정보 덕에 진짜 논문을 읽게 됐네요. 이 논문에서 챙기고 싶은 건 알고리즘이랑 코렉트니스이니 2,4,5 챕터만 빠르게 읽어봅니다.

챕터 2는 위의 위키피디아 내용과 일치하니 스킵~

챕터 4-알고리즘을 읽어봅시다.

먼저 중요해보이는 포인트가 있네요. 가정과 correctness requirement 부분을 봅시다.

We say that an operation A precedes B if the response to A occurs before the invocation of B and that operations are concurrent if they have no real-time ordering.

precede와 concurrent에 대한 정의였네요. 크게 주의해야 할 점은 없는 거 같으니(있을수도 있어요!! 바보인 저(maxlevsnail)를 믿지 마세요) 쭉쭉 읽어봅시다.

Our basic correctness requirement is linearizability which requires that (a) the responses received in every concurrent history are equivalent to those of some legal sequential history of the same requests and (b) the ordering of operations within the sequential history is consistent with the real-time order.

이렇게 두가지의 requirement가 있네요. 간단하게 해석해보면 현실과 순서가 맞아야 한다 이런 뜻인거같아요. 제 주관적인 해석은 락 걸고 한스레드씩 작업하도록 하는거랑 비슷하게 작동해야 한다는 그런 뜻이지 않을까 싶네요.

그리고 non-blocking에 대한 명시가 있습니다. non blocking이란 다른 스레드에서의 작업이 실패하더라도 지금 작업은 끝나긴 해야한다는 겁니다. Wait-free와 Lock-free등이 비슷하지만 다른 개념인데 이는 다른 글에서 다룰게요.

implementation 코드는 cs431의 코드를 기반으로 할게요.

Harris Linked List(엄밀하게는 Ordered Set)는 세가지 operation이 가능합니다. 삽입, 제거, 찾기.

삽입, Insert

fn insert<'g, F>(&'g self, key: K, value: V, find: F, guard: &'g Guard) -> bool
    where
        F: Fn(&mut Cursor<'g, K, V>, &K, &'g Guard) -> Result<bool, ()>,
    {
        let mut node = Owned::new(Node::new(key, value));
        loop {
            let (found, mut cursor) = self.find(&node.key, &find, guard);
            if found {
                drop(node.into_box().into_value());
                return false;
            }

            match cursor.insert(node, guard) {
                Err(n) => node = n,
                Ok(()) => return true,
            }
        }
    }

#[inline]
    pub fn insert(
        &mut self,
        node: Owned<Node<K, V>>,
        guard: &'g Guard,
    ) -> Result<(), Owned<Node<K, V>>> {
        node.next.store(self.curr, Ordering::Relaxed);
        match self.prev.compare_exchange(
            self.curr,
            node,
            Ordering::Release,
            Ordering::Relaxed,
            guard,
        ) {
            Ok(node) => {
                self.curr = node;
                Ok(())
            }
            Err(e) => Err(e.new),
        }
    }

이게 삽입 코드고요, 하나하나 뜯어봅시다.

let (found, mut cursor) = self.find(&node.key, &find,guard);
if found {
    drop(node.into_box().into_value());
    return false;
}

여기에서 볼 수 있듯이 Set이기에 중복된 요소가 있으면 만든 노드 드랍하고 끝냅니다.
중복아니라면 현재 커서값이 self.curr는 찾는 값보다 큰 값, self.prev는 전 노드의 next 항목의 주소가 될 것입니다. 즉 self.prev는 self.curr의 주소값을 갖고 있겠죠. 그래서 insert할 때 우리가 삽입할 노드의 next를 self.curr로 설정하고, cas를 이용해 전 노드의 next포인터 값을 바꿔줍니다. insert는 위에서도 언급했듯이 굉장히 나이브하게 진행됩니다.

제거, Delete

    #[inline]
    fn delete<'g, F>(&'g self, key: &K, find: F, guard: &'g Guard) -> Option<&'g V>
    where
        F: Fn(&mut Cursor<'g, K, V>, &K, &'g Guard) -> Result<bool, ()>,
    {
        loop {
            let (found, cursor) = self.find(key, &find, guard);
            if !found {
                return None;
            }

            match cursor.delete(guard) {
                Err(()) => continue,
                Ok(value) => return Some(value),
            }
        }
    }

/// Deletes the current node.
    #[inline]
    pub fn delete(self, guard: &'g Guard) -> Result<&'g V, ()> {
        let curr_node = unsafe { self.curr.as_ref() }.unwrap();

        let next = curr_node.next.fetch_or(1, Ordering::Acquire, guard);
        if next.tag() == 1 {
            return Err(());
        }

        if self
            .prev
            .compare_exchange(self.curr, next, Ordering::Release, Ordering::Relaxed, guard)
            .is_ok()
        {
            unsafe {
                guard.defer_destroy(self.curr);
            }
        }// maybe safe? 

        Ok(&curr_node.value)
    }

제거는 두 번의 cas가 들어갑니다. 첫 cas는 tagging, 두번째 cas는 링크드리스트에서의 삭제입니다.
fetch_or함수를 통해 curr_node.next에 태그를 달고, next를 받아옵니다. 당연히 이 next가 태그되어있으면, 즉 이미 삭제된 노드라면 Cursor::delete 함수는 Err(())를 리턴합니다. 그리고 위의 Set의 delete는 loop되어 있어 게속 다시 시도하겠죠. 그리고 다른 스레드의 delete가 완료되면, 즉 tag되지않은 값이 next로 받아진다면 delete를 수행할 것입니다.
삭제하는 방법은 간단합니다. self.prev에 next값을 넣는거죠. 자세한 correctness는 아래에서 다룰게요.

찾기 Search

Find는 별거 없어서 Search를 봅시다.

/// Clean up a chain of logically removed nodes in each traversal.
    #[inline] 
    pub fn find_harris(&mut self, key: &K, guard: &'g Guard) -> Result<bool, ()> {
        // Finding phase
        // - cursor.curr: first unmarked node w/ key >= search key (4)
        // - cursor.prev: the ref of .next in previous unmarked node (1 -> 2)
        // 1 -> 2 -x-> 3 -x-> 4 -> 5 -> ∅  (search key: 4)
        let mut prev_next = self.curr;
        let found = loop {
            let curr_node = some_or!(unsafe { self.curr.as_ref() }, break false);
            let next = curr_node.next.load(Ordering::Acquire, guard);

            // - finding stage is done if cursor.curr advancement stops
            // - advance cursor.curr if (.next is marked) || (cursor.curr < key)
            // - stop cursor.curr if (not marked) && (cursor.curr >= key)
            // - advance cursor.prev if not marked

            if next.tag() != 0 {
                self.curr = next.with_tag(0);
                continue;
            }

            match curr_node.key.cmp(key) {
                Less => {
                    self.curr = next.with_tag(0);
                    self.prev = &curr_node.next; 
                    prev_next = next; 
                }
                Equal => break true,
                Greater => break false,
            }
        };

        // If prev and curr WERE adjacent, no need to clean up
        if prev_next == self.curr {
            return Ok(found);
        }

        // cleanup marked nodes between prev and curr, failed the cas
        self.prev
            .compare_exchange(
                prev_next, 
                self.curr,
                Ordering::Release,
                Ordering::Relaxed,
                guard,
            )
            .map_err(|_| ())?;

        // defer_destroy from cursor.prev.load() to cursor.curr (exclusive)
        let mut node = prev_next;
        while node.with_tag(0) != self.curr { 
            let next = unsafe { node.as_ref() }
                .unwrap()
                .next
                .load(Ordering::Acquire, guard);
            unsafe {
                guard.defer_destroy(node);
            }
            node = next;
        }

        Ok(found)
    }

먼저 이 Search는 위에 설명한 세 가지 메소드에서 모두 사용됩니다. Search를 통해 Insert, Delete, Find가 진행되는거죠. Search는 Cursor를 리턴하는데, 위에 설명한 것처럼 .prev는 그 전 노드(찾는 값보다 작은)의 next항목, .curr는 그 후 노드(찾는 값보다 크거나 같은)가 되겠습니다.

Search는 세 단게로 구성됩니다. 먼저 찾습니다.

// Finding phase
let mut prev_next = self.curr;
let found = loop {
    let curr_node = some_or!(unsafe { self.curr.as_ref() }, break false);
    let next = curr_node.next.load(Ordering::Acquire, guard);
    // - finding stage is done if cursor.curr advancement stops
    // - advance cursor.curr if (.next is marked) || (cursor.curr < key)
    // - stop cursor.curr if (not marked) && (cursor.curr >= key)
    // - advance cursor.prev if not marked
    if next.tag() != 0 {
        self.curr = next.with_tag(0);
        continue;
    }
    match curr_node.key.cmp(key) {
        Less => {
            self.curr = next.with_tag(0);
            self.prev = &curr_node.next; 
            prev_next = next; 
        }
        Equal => break true,
        Greater => break false,
    }
};

이 부분이죠. prev_next는 마지막 유효한 노드, next는 현재 노드가 되겠습니다. next가 태그되어있으면 무시하고 전진하고, 유효할 때만 prev_next와 self.prev를 업데이트해줍니다.

다음 단계는 사이에 제거할 노드가 있는지 찾아보는 것입니다.

// If prev and curr WERE adjacent, no need to clean up
if prev_next == self.curr {
    return Ok(found);
}

이 부분이 되겠죠. 주석에 써있는 대로 사이에 유효한 값만 있으면 굳이 삭제할 필요가 없을 겁니다.

마지막 단계는 태그되어있는 노드들을 정리하는 단계입니다.

// cleanup marked nodes between prev and curr
self.prev
    .compare_exchange(
        prev_next, 
        self.curr,
        Ordering::Release,
        Ordering::Relaxed,
        guard,
    )
    .map_err(|_| ())?;
// defer_destroy from cursor.prev.load() to cursor.curr (exclusive)
let mut node = prev_next;
while node.with_tag(0) != self.curr { 
    let next = unsafe { node.as_ref() }
        .unwrap()
        .next
        .load(Ordering::Acquire, guard);
    unsafe {
        guard.defer_destroy(node);
    }
    node = next;
}

이 부분. 먼저 self.prev의 값이 prev_next일 텐데 이 값을 self.curr로 cas해 그 사이 노드들을 접근하지 못하도록 합니다. 그리고 그 사이를 천천히 destroy해줍니다. 그러면 Search가 끝이 나게 됩니다.

Correctness

if self
    .prev
    .compare_exchange(self.curr, next, Ordering::Release, Ordering::Relaxed, guard)
    .is_ok()
{
    unsafe {
        guard.defer_destroy(self.curr);
    }
}// maybe safe?

self.prev
    .compare_exchange(
        prev_next, 
        self.curr,
        Ordering::Release,
        Ordering::Relaxed,
        guard,
    )
    .map_err(|_| ())?;

이 두 CAS는 태그된 노드를 unlink할 때만 성공합니다. 따라서 태그된 노드의 수보다 더 많이 unlink할 수는 없습니다. Delete의 첫번쨰 CAS를 보면 알 수 있듯이 한 번의 성공적인 삭제에 정확히 하나의 노드가 태그되며, 그리고 위의 두 CAS 중 하나에 의해 정확히 하나의 노드만 삭제될 것입니다.

Linearization points. Let op_im be the mth operation performed by processor
i and let d_im be the final real-time at which the List::search post-conditions
are satisfied during its execution. These d_im identify the times at which the
outcome of the operations become inevitable and we shall take the ordering
between them to define the linearized order of Find(k) operations or unsuccessful updates. For a successful find at d_im the right node was unmarked and contained the search key. For an unsuccessful insertion it exhibits a node with a matching key. For an unsuccessful deletion or find it exhibits the left and right nodes which, respectively, have keys strictly less-than and strictly greater-than the search key.
Furthermore let u_im be the real-time at which the update C2 inserts a node or
C3 logically deletes a node. We shall take u_im as the linearization points for such successful updates. In the case of a successful insertion the CAS at u_im ensures that the left node is still unmarked and that the right node is still its successor.
For a successful deletion the CAS at u_im serves two purposes. Firstly, it ensures that the right node is still unmarked immediately before the update (that is, it has not been logically deleted by a preceding successful deletion). Secondly, the update itself marks the right node and therefore makes the deletion visible to other processors.

메소드 중에 재귀 관련된 방법은 없으니 브랜치들만 살펴봅니다.

먼저 Search의 Finding phase에서 있는 브랜치들을 지날 때마다 self.curr는 한 칸 전진합니다. 리스트는 항상 태그되지 않은 테일 노드를 가지고, 방문한 노드들은 점점 커집니다.
Search의 마지막 단계에서

{ Each time B1 is taken the local variable t is advanced once node down the
list. The list is always contains the unmarked tail node and the nodes visited
have successively strictly larger keys.
{ Each time B2 is taken the CAS at C1 has failed and therefore the value of
left node.next != left node next. The value of the field must have been
modified since it was read during the loop ending at B1. Modi cations are
only made by successful CAS instructions and each operation causes at most
two successful CAS instructions.
{ Each time B3 or B4 is taken the CAS at C2 or C4 has failed. As before, the
value held in that location must have been modi ed since it was read in
List::search and at most two such updates may occur for each operation.
{ Each time G1 or G2 is taken then a node which was previously unmarked
has been marked by another processor. As before, at most two updates may
occur for each operation.

Harris Michael LL

Harris LL와 다른 점은

/// Clean up a single logically removed node in each traversal.
    #[inline]
    pub fn find_harris_michael(&mut self, key: &K, guard: &'g Guard) -> Result<bool, ()> { //fixing one at a time right away.
        loop {
            debug_assert_eq!(self.curr.tag(), 0);

            let curr_node = some_or!(unsafe { self.curr.as_ref() }, return Ok(false));
            let mut next = curr_node.next.load(Ordering::Acquire, guard);

            if next.tag() != 0 {
                next = next.with_tag(0);
                self.prev
                    .compare_exchange(self.curr, next, Ordering::Release, Ordering::Relaxed, guard)
                    .map_err(|_| ())?;
                unsafe {
                    guard.defer_destroy(self.curr);
                }
                self.curr = next;
                continue;
            }

            match curr_node.key.cmp(key) {
                Less => {
                    self.prev = &curr_node.next;
                    self.curr = next;
                }
                Equal => return Ok(true),
                Greater => return Ok(false),
            }
        }
    }

오직 이 부분이다. Harris Michael 에서는 태그된 노드를 즉각즉각 없애주는 것이 차이점.

Harris-Herlihy-Shavit’s

    /// Gotta go fast. Doesn't fail. fast on read, overall just harris can be better.
    #[inline]
    pub fn find_harris_herlihy_shavit(&mut self, key: &K, guard: &'g Guard) -> Result<bool, ()> {
        Ok(loop {
            let curr_node = some_or!(unsafe { self.curr.as_ref() }, break false);
            match curr_node.key.cmp(key) {
                Less => {
                    self.curr = curr_node.next.load(Ordering::Acquire, guard);
                    // NOTE: unnecessary (this function is expected to be used only for `get`)
                    self.prev = &curr_node.next;
                    continue;
                }
                Equal => break curr_node.next.load(Ordering::Relaxed, guard).tag() == 0,
                Greater => break false,
            }
        })
    }

여기서는 logically deleted node들을 그냥 무시해버린다. wait free이지만, 오직 lookup에만 사용가능하다. 삽입/삭제에서는 사용못하는데 왜냐하면 cursor.prev가 이미 삭제된 노드일수도 있기 때문이다.

Non Blocking Linked List

MaxLevSnail