링 버퍼 (Ring Buffer)

https://chronicle.software/ring-buffer/
링 버퍼는 FIFO queue 처리를 위한 자료구조 중 하나다. circular buffer라고도 부른다.

기본 자료구조 개론에서는 잘 다뤄지지 않는데, 응용의 폭이 꽤 넓어서 알아두면 좋다.

기본 원리

이건 배열을 기반으로 동작한다.
고정된 크기의 정적 배열인지, 크기가 늘어나는 동적 배열인지는 구현 선택에 따라 다르다.

구성요소는 간단한 편이다.
배열 한줄과, 앞을 가리키는 start 인덱스, 끝을 가리키는 end 인덱스로 구성된다.

기본 동작 원리도 간단한 편이다.

1. 데이터를 꺼낼 때는 start 인덱스 위치에서 요소를 꺼내고 start를 증가시킨다.
2. 데이터를 집어넣을 때는 end 오른쪽에 요소를 집어넣고 end를 증가시킨다.

그럼 start가 오른쪽 끝을 넘으면 어떻게 될까?

사실 그래도 문제는 없다.
배열 자체는 직선이지만 논리적으로는 원형이기 때문에, 끝 인덱스 다음을 0번째 인덱스로 간주하면 되는 것이다.
그래서 이렇게 end가 start 왼쪽에 있을 수도 있다.
https://eteo.tistory.com/m/359

근데, 데이터가 꽉 찬 상태에서 요소를 집어넣으면 어떻게 할까?

1. 기본적인 구현에서는 가장 오래된, start 위치의 데이터를 지우고 밀어넣는 경우가 많다.
   스트리밍이나 로그 agent처럼 데이터의 부분적인 유실이 크게 중요하지 않은 경우에는 이 방법이 충분히 효율적이다.
2. 그게 아니라면 배열 크기를 늘리고 데이터를 옮겨야 한다. 후술할 dynamic ring buffer가 이런 원리다.

장점과 단점

배열의 뛰어난 성능에 기반해서 queue 기능을 구현할 수 있다.
queue를 구현하는 다른 방식인 linked list나 chunked array에 비해서 삽입, 삭제, 접근 속도가 훨씬 뛰어나다.

대신, (기본 구현의 경우) 데이터 유실 가능성이 있고, (dynamic 구현의 경우) 확장과 축소의 관리가 linked list에 비해 유연하지 못하다는 단점이 있다.
ring buffer를 동적으로 구현하는 것도 가능하지만, ring buffer가 최적으로 작동하는 시나리오는 최대 크기가 정해져있는 경우다.

Dynamic Ring Buffer

ring buffer의 이상적인 사용사례는 크기가 고정되어있는 경우지만, 응용프로그램에서는 그런 한계점을 두고서는 써먹기가 어려울 수도 있다.

그래서 일부 응용 구현에서는 사용량에 따라서 자동으로 배열이 확장되거나 축소되는 형태로 변형이 되기도 한다.

dynamic ring buffer를 구현하는 방법은 잘 일반화되어있지는 않지만, 그로 인해 발생하는 단점은 대충 이런 것들이 있을 수 있다.

1. 크기가 늘거나 줄어들때마다, 배열을 새로 만들고 옮겨야 한다. 적지 않은 비용이고, 동시성 처리에도 불리한 지점이다. 그래서 리사이징을 돌리는 주기를 잘 선택해야 한다.

2. 사용량이 급격이 늘어났다가 줄어들 경우에 메모리 누수가 발생할 수 있다. 크기를 사용량에 맞춰 항상 compact하게 유지하는 것은 거의 불가하다.

대표적인 dynamic Ring Buffer 구현체로는 Rust의 기본 자료구조 VecDeque가 있다.
Java의 ArrayDeque도 Ring buffer 기반의 구현체로 알려져있다.