Concurrent ART에 관한 연구 about concurrent-data-structure HOT 3 OPEN

paper

• https://db.in.tum.de/~leis/papers/ART.pdf
• https://15721.courses.cs.cmu.edu/spring2017/papers/08-oltpindexes2/leis-damon2016.pdf

repo

• https://github.com/kaist-cp/cs431/tree/main/homework/src/art
• https://github.com/Lagrang/art-rs
• https://github.com/dshulyak/art

from concurrent-data-structure.

꽤나 hot(?)했던 자료구조였는지 적당히 잘 구현된 코드들도 있는거 같다. 얘도 아마 구현해봤던 기억상 & 추정상으로는 rebalance라기 보다, removal시 path 압축 및 node 제거 정도의 간단한 것만 처리하면 되던 것으로 기억하기 때문에 optimistic lock coupling으로 쉽게 괜찮은 성능을 뽑아볼 수 있을 거 같다.

from concurrent-data-structure.

구현하면서 든 여러 가지 고민거리

• Node 안에 임의의 keys들이 들어있는 것을 len으로 가지고 있을 것인지, 아니면 invalid marking을 해둬서 접근을 막을 것인지
  • 일단 general하게 쓸 수 있도록 len을 가지고 있는게 나을 듯.
• path compression은 얼마만큼 할 것인지(pessimistic과 optimistic을 얼마나 잘 섞어볼 것인가)
• SIMD가 실제로 linear search나 binary search 대비 얼마나 성능이 괜찮을 것인가
• Node 크기를 줄일 수 있지 않을까? 가령 strictascii string만 허용한다고 해서(a-z, A-Z, 0-9, :, -) 총 64글자(6비트)로 Node64까지만 만든다거나 등등

from concurrent-data-structure.