Sorted Set - ListPack
1. “이전 엔트리 길이를 뒤에 적는다”
ZipList는 엔트리의 시작 부분에 prevlen(이전 엔트리 길이)을 적었다. 그래서 앞의 데이터가 커지면 내 시작 위치가 밀리고, 내 prevlen 공간도 커져야 하는 연쇄 반응이 일어나는 것이다.
ListPack은 엔트리 맨 뒷부분에 해당 엔트리 자신의 길이를 기록한다.(backlen)
2. 연쇄 업데이트를 어떻게 막을까?
역방향 탐색 과정을 비교해 보자.
- ZipList: 현재 내 머리(Start)에 적힌 prevlen을 보고 “앞으로 N바이트 가자!”라고 판단한다. 앞이 커지면 내 머리 정보를 수정해야 한다.
- ListPack: 내 머리 정보는 건드리지 않고 내 바로 앞의 ‘꼬리’를 보고 “앞의 길이가 N바이트니, 앞으로 N바이트 가자!”라고 판단한다. 앞이 아무리 커져도 자신의 내부 데이터를 수정할 필요가 없다.