Lock-based AVL tree에 관한 고민

[codingskynet]

기본적으로 https://stanford-ppl.github.io/website/papers/ppopp207-bronson.pdf 을 바탕으로 구현해보도록 한다.

구현 계획은 아래와 같다.

1. crossbeam-utils에서 제공하는 SharedLock(Readers-Writer Lock)으로 RwLockAVLTree를 만들어 본다.
2. 직접 SeqLock을 구현하여 optimistic하게 구현해본다.

[codingskynet]

위 논문에서 접근하고 있는 방안은 다음과 같다.

0. Bouge et al.에서 rebalance가 보이는 height(동기화가 필요없다는 것 같다)에 대해서 시행되더라도 부분적으로 일어나는 rebalance들의 순열이 곧 strict AVL tree를 만들어낼 수 있다는 점을 보였다.
1. AVL tree에서 RL, LR의 경우에는 RR, LL과는 달리 2회전이 필요하다. 이러한 경우에는 하위 트리에 대해 rotation을 하고, 다시 function을 call함으로써 상위 트리에 대해 rotation을 시도하는 방법으로 접근하다. 아마, 2회전의 경우 너무 많은 시간을 write lock에 소모해야 하니 그런 게 아닐까 싶다.
2. height는 node 같은 것과 달리 수시로 바뀐다(Insertion/Removal만 생각해봐도 root-node까지 route에 있는 모든 nodes에 write lock을 걸고 update를 가해야 한다). 따라서 read-only atomic을 사용할 수 있도록 field에 versioning을 한다. 실제로 versioning을 하는 코드는 살펴봐야 할 것 같다.
3. 당연한 이야기이지만, concurrent이기 때문에 중간에 '잠시라도' unlinked가 일어나면 안 된다. rotation에서 link/unlink하는 부분은 order를 유의깊게 생각하여 코딩할 것

[codingskynet]

현재 위 논문의 접근법을 섞어서 RwLockAVLTree에 적용하려는 사항은 다음과 같다.

• 2회전의 경우 1+1회전으로 나눠서 접근하기
  • 그런데, 현재 RwLockAVLTree의 구조를 보면 Cursor-based로 operation이 돌아가도록 구현되어 있다. 이는, node 간의 관계를 single linked로 나타내기 위함이었는데(구현의 간단함 + write operation의 감소), 1+1회전으로 쪼개려면 child node에서 parent node를 알 수 있도록 해야 하지 않을까? 라는 고민이 있다. 일단은 같은 parameter(current, parent, grand_parent)로 2번 try하는 것이 문제가 될 거 같진 않다. 증명은 해보지 않았지만, 이미 그 state가 parameter에 주어진 nodes의 관계와 다르다는 것은 다른 thread가 이미 rebalance를 success했다는 것으로 이해할 수 있기 때문이다. 애초에 2회전이 필요한 경우(LR, RL)는 1회전 + 1회전(LR -> LL -> balanced, RL -> RR -> balanced)으로 상태를 세분화할 수 있으며, 최초 하위 회전도 결국 거시적으로 봤을 때 엔트로피를 줄이는 방향이다.
• height의 경우, 일단 NodeInner에 넣고 write lock으로 관리할 수 있도록 할 생각이다. correct 구현에 성공하면 이후에 read-only versioned atomic을 도입해볼까 싶다. 아마 환형큐처럼 뭔가를 만들면 될 거 같긴 한데 흠... 이는 SeqLockAVLTree를 만들게 된다면, optimistic의 성질 때문에 가볍게 해결될 듯하다.

추가로 고려중인 사항은 다음과 같다.

• repair 함수 파라미터를 그냥 unique concurrent deque에서 뽑아내서 task를 처리하는 방식을 채택해보기
  • 간단히 생각해보면, 1이 삽입되어 있는 AVL tree에 0, 2를 삽입하면 1의 height을 두 번 업데이트하는 비효율성을 관찰할 수 있다. 이게 sequential이라면 무조건 하면 되지만, concurrent 상황에서는 그 repair operation이 lock 때문에 wait할 확률이 높다. 게다가 이게 rotation의 경우를 생각하면 cost가 엄청 클 것이라 생각하기 때문에 다음과 같은 개선책을 생각해보았다.
  • repair에서 call하는 try_cleanup, try_rebalance는 각 parameter를 concurrent deque에 넣어놓고 뽑아서 operation을 수행하는 방법 을적용할 수 있다. 위의 예시를 renew_height function에 대해 보이자면, 기존에는 0, 1, 2, 1 노드에 각각 시행해야 했다면, 이제는 0, 2, 1 이렇게 시행할 수 있도록 만드는 것이다. node 2를 먼저 삽입했다고 가정하면, concurrent deque에는 2, 0이 있을테고, 이후 1, 0이 push될 것이다. 이때, 0은 이미 있으므로 1만 삽입되어, 1, 2, 0 정도의 상태가 된다. 실제로, root에 가까울수록 나중에 작업이 이뤄져야 하고, 겹치지 않는 부분은 현재 deque에 있는 nodes보다 level이 크거나 같기 때문에 아마 concurrent stack 형식으로 문제를 해결할 수 있을 것 같다.
  • 이 접근법의 문제는 이 concurrent deque를 어떤 쓰레드가 관리하냐에 있다. 여기에는 크게 두 가지 생각이 있다. 먼저, 특정 1개의 쓰레드를 tree 전용으로 할당받아 이 repair 작업만 수행하게 만드는 방법이 있다. 이러면 concurrent deque는 mutiple producer single consumer의 형태를 띌 것이다. 이렇게 하면 구현이 간단해질 것이지만, concurrent 상황에서 local하게 동시에 실행할 수 있는 task가 sequential하게 실행되어야 한다는 단점이 있다. 다음으로, task만 concurrent deque로 관리하되, 각 쓰레드가 자신이 push한 task가 모두 끝날 때까지 task를 할당받아 처리하고 insert/remove operation을 종료하는 방법이 있다. 이 경우에는 concurrent deque가 multiple producer multiple consumer의 형태를 띄어야 한다. 전자의 방법의 문제점을 해결할 수 있다. 그러나, 위에 말한 것처럼 아마 concurrent deque에서 stack의 형태를 사용하게 될 것인데, 이는 맨 처음 repair를 시도한 operation이 맨 마지막에 repair에 들어온 operation에 의존을 하는 단점을 가질 수 있다. 전자와 후자를 잘 섞어서, local하게 repair 가능한 것은 concurrent하게, 겹치는 부분(동일 조상들을 가지는 경우)에 대해서는 특정 한 쓰레드가 작업권을 가지도록 작업 분배를 설계할 수 있다면 좋지 않을까 싶다.

[codingskynet]

현재 RwLockAVLTree, SeqLockAVLTree에서 구현한 rebalance 사항은 다음과 같다.

• 모든 회전은 실패하더라도 재시도 하지 않는다. 그래도 실험적으로 거의 balanced tree가 된다는 것을 확인할 수 있었기 때문인데, 사실 SeqLock에서는 read lock은 non-blocking이기 때문에 재시도하더라도 cost가 크지 않고 balanced tree로 만들기 쉬울 듯하긴 하다. 다만 이 경우에는, write를 re-checking하는 방식을 사용하기 보다는 read lock의 write lock로서의 upgrade가 성공했냐로 체크하여 재시도해야 할 듯.
• 2회전이 필요한 경우(RL, LR)에도 write lock을 다 걸고 한꺼번에 2회전을 한다. 이렇게 한 이유는, 굳이 1+1회전으로 쪼갤 필요가 없어서...? 나중에 쪼갠 것도 테스트해보면 좋을 거 같다.
• 어느정도 최적화를 하긴 했지만, 그래도 Rust의 std::BTreeMap이 매우 빨라서 scalability를 제외하곤 큰 효용성이 있지 않다. 아마도 AVL의 random access적인 특성 때문에 cache가 비효율적으로 사용되는 거 같은데, B tree를 바탕으로 만든 BzTree를 테스트해본 결과, 그래도 std::BTreeMap이 너무 빠른 듯하여 이쪽을 연구하여 concurrent를 붙이는 것이 좋은 방향이 될 것 같다.