Homework Feedback

[min-guk]

Feedback for your submitted solution will be given starting today.

[min-guk]

2022.7.16 오후 10:10:17

1. Why do LSM-tree and LevelDB use leveled structure?

만약 데이터베이스가 L0, L1 2개의 층으로만 구성되어 있다면, 거의 모든 데이터가 L1에 저장될 것이고 L1엔 같은 key의 데이터가 없어야 하므로 write를 할 때 마다 같은 key의 데이터가 존재하는지 확인하기 위해 저장된 모든 데이터를 참조해야 할 것이다.

해당 질문은 disk에서 single 레벨을 사용하지 않고, multi 레벨을 사용하는 이유을 물은 것입니다. 싱글 레벨에서는 Flush할 때마다, 겹치는 key range가 겹치는 모든 데이터를 compaction 해야합니다.

하지만 데이터를 더 많은 계층에 저장한다면 대부분의 데이터가 L2 이하의 계층에 저장될 것이고 그러면 write를 할 때 특정 key의 값이 여러개 존재한다 해도 상위 계층의 값만 참조하면 되므로 모든 key의 중복을 체크할 필요가 없어져 write 연산이 매우 빨라진다.

맞습니다. multi 레벨인 경우, compaction overhead가 줄어들고 write amplification이 줄어들어 write 성능이 향상됩니다.

허나 이 경우 한 key에 대한 값이 중복되어 저장되므로 공간 증폭이 발생하며
이를 하위 계층일 수록 크기를 크게 하는 것으로 최소화 하였다.

맞습니다. WAF가 낮아지지만, RAF과 SAF가 높아집니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?

계층의 크기가 클수록 compaction 연산의 부하가 커지는데,
level 0의 데이터들은 정렬되어 있지 않고 범위가 넓기 때문에
level 0의 크기가 커지면 compact 연산의 부하와 읽기 증폭이 특히 커지게 된다.
그렇기에 leveldb는 level 0의 크기를 작게하고 level 0에만 파일 수 제한을 두어
다른 계층보다 더 자주 compaction을 수행하게 하였다.

level 0의 크기가 커지만, L0는 정렬되지 않고 중복된 데이터가 존재하므로 읽기 증폭이 증가합니다. 반면 L0의 크기가 커지는 경우, compaction을 더 많이 모아서 진행하므로 쓰기 증폭은 감소합니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.

fillseq의 경우가 fillrandom의 경우보다 더 뛰어난 처리율과 지연 시간을 보였으며
stats을 통해 확인한 fillseq는 read가 한번도 되지 않았고 write가 적게 된 반면
fillrandom은 read와 write 값이 매우 컸다.
이는 fillseq의 경우 fillrandom과 달리 일련의 연속된 key 값이 들어오므로
자동으로 값이 정렬되어 read가 발생하지 않았고,
seek time이 줄어들고 한 테이블의 범위가 작아
compaction 연산의 부하가 줄어든 것으로 보인다.

맞습니다. fillseq에서는 compaction으로 인한 read I/O가 발생하지 않습니다. 그리고 memtable에서도 순서대로 키가 삽입되므로, CPU 캐시 히트율이 높아져 memtable put 속도도 상대적으로 빠릅니다.

3-2. In benchmark A, SSTs are not written in L0. Why?
fillseq의 경우 중복된 key가 존재하지 않으므로
flush의 trivial move 규칙에 의해
최대한 밑으로 push되어 L0이 사용되지 않은 것 같다.

맞습니다.

4-1. Which user key-value interface does each benchmark use?
db.bench.cc 파일을 확인한 결과
readrandom엔 get이,
readseq와 seekrandom엔 iterator이 사용되었다.

맞습니다.

4-2. Compare throughput and latency of each benchmark and explain why.
readseq, readrandom, seekrandom 순으로 더 뛰어난 처리율과 지연 시간을 보였는데,
순서대로 값을 읽는 readseq가 seek time이 적어 특히 빨랐으며
readrandom과 seektrandom은 속도가 비슷했으나
seek가 약간의 시간을 더 필요로 했다.
이는 iterator와 get의 속도 차이 때문으로 추정된다.

readseq은 디스크에서 sequential read I/O을 진행하여 빠르고, 나머지는 random I/O입니다. iterator seek 무조건 최하위 레벨까지 탐색해야하고, get은 찾는 레벨을 하나하나 내려가면서 키 값을 찾으면 탐색을 중지하므로 더 빠릅니다.

Q. The size of input kv pairs is the same. But One is better in throughput, the other is better in latency. Explain why.
둘의 총 데이터 용량은 같으나
하나의 데이터 크기가 작은 대신 그 수가 많은 [B]가 [A]에 비해 훨씬 빨랐다.
leveldb의 경우 데이터가 memtable에 모였다가 한번에 put 되는데 (batch write)
level 0의 경우 2번 문제에서 말했듯 파일의 개수 제한이 존재하고
level 0의 데이터의 용량이 클수록 부하가 급격히 커지므로
같은 개수일 때 용량이 작은 [B]가 [A]에 비해 부하가 적어 속도가 빠른 것으로 생각된다.

같은 사이즈를 쓸 때, 크게 적게 쓰는 것이 응답속도는 느리나 처리율은 높고, 작게 여러번 쓰는 것이 응답속도는 빠르나 처리율은 낮습니다.

[min-guk]

2022.7.18 오전 12:59:24

1. Why do LSM-tree and LevelDB use leveled structure?

다중 레벨 구조의 데이터 베이스는 증폭을 감소시키는 효과가 있기 때문이다. 레벨이 나누어지게 되면 가장 상위층의 level0은 정렬되지 않았기 때문에 다른 단계의 데이터와 겹칠 가능성이 높다. (이는 compaction을 하는 이유이기도 하다.) 이렇게 레벨이 나누어진 데이터들을 정렬하고 압축하고 제거하는 과정을 통해 데이터를 유지하는 것이 이 레벨디비의 핵심이기 때문이다. 레벨의 숫자가 너무 작으면 더 많은 레벨이 생성되기 때문에 증폭의 크기가 커지게 되어 적합하지 않다.

단일 레벨은 쓰기 증폭이 증가하나, 읽기 증폭과 공간 증폭이 감소합니다. 멀티 레벨은 그 반대입니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?

leveldb는 일반적인 LSM 트리 구현이므로 메모리의 데이터가 유지되어야 한다. 따라서 leveldb에서 Minor Compaction이라고 하는 메모리 내 데이터의 지속성을 가지는 프로세스가 필요한데, 이 프로세스를 구성하기위한 계층이 7계층 까지 존재하기 때문에 0~7 총 8개의 레벨이 존재한다.

모범 답안을 참고하시길 바랍니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.

3-2. In benchmark A, SSTs are not written in L0. Why?
가장 위 계층인 l0는 처음 wal이 실행되고, memtable에 적혀진 키벨류 값들이 이동하면서 l0에 처음 쓰이게 된다. 즉 immutable한 memtable을 구성하게 되는데, 그렇기 때문에 a에서 sst는 l0에 쓰이지 않는다.

Trivial Move로 그러합니다.

3-2. Calculate SAF (Space Amplification Factor) for each benchmark.
saf는 공간증폭으로써, 실제 사용하는 공간에 대한 사용자가 쓰려고 하는 데이터의 비율을 의미한다.

PPT로 SAF를 계산하는 것을 참고하시길 바랍니다.

4-1. Which user key-value interface does each benchmark use?

4-2. Compare throughput and latency of each benchmark and explain why.

5. The size of input kv pairs is the same. But One is better in throughput, the other is better in latency. Explain why.

[min-guk]

2022.7.18 오전 2:03:31

1. Why do LSM-tree and LevelDB use leveled structure?

LSM-tree와 LevelDB는 데이터가 들어오게 되면 메모리에 계속 쌓이게 되고 수용 가능한 공간을 모두 써버리면 stack overflow가 일어나기 때문에 수용한 공간을 모두 disk에 전달하는 flush를 한다. disk에 공간을 세부적인 레벨로 나눠 stack overflow를 방지하고 각 레벨의 공간이 다 찼을때 LSM-tree는 merge sort, LevelDB는 compaction을 하여 더 낮은 레벨로 이동한다.

stack overflow보다는 Memtable에 할당한 공간이 다 차면 flush된다고 생각하시는 것이 적절할 것 같습니다.

각 레벨로 나누게 되면 오래된 데이터를 지우지 않고도 새로운 데이터를 갱신시킬 수 있는 out place of update 를 사용할 수 있고 이는 large sequential write가 되어 쓰기 성능을 대폭 향상시킬 수 있다.

맞습니다. leveldb에서는 Flush되는 SSTable에 대해 즉각적으로 Compaction을 진행하지 않아도 됩니다. 또한 key range가 겹치는 모든 SST에 대해 Compaction을 진행하는 것이 아니라, 해당 레벨과 다음 레벨에서 key range가 겹치는 SST만 Compaction을 진행하면 되므로 out-of-place update와 batch write을 통한 이득을 극대화할 수 있습니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?

leveldb는 i>=1 인 경우 각 레벨의 sstable 파일에는 merge sort 가 되어있기 때문에 중복 키가 포함되지 않는다. 따라서 한 단계씩 내려갈수록 디폴트로 10배의 공간이 더 할당되어 있는데, 이는 10배보다 적다면 많은 레벨로 나눠져 더 많은 읽기 증폭을 야기할 수 있고, 10배보다 더 많다면 한 레벨에 공간이 커지고 더 많은 공간 증폭을 야기할 수 있다. 그로 인해 RAF, SAF, Compaction 비용이 증가할 수 있기 때문에 어느정도 합리적인 10배를 디폴드로 설정하여 사용하고 있다.

맞습니다. 다음 레벨을 이전 레벨의 몇 배의 크기로 할 것인가는 결국 WAF vs RAF+SAF의 tradeoff입니다.

이때 level 0에 경우 로그 파일에서 생성된 잘 정렬된 파일이 배치되어 있으며 중복 키가 포함되어 있을 수 있다. 중복된 키가 많으면 level 0이 level 1가 병합될 때마다 level 1의 입력 파일의 총 데이터의 양이 많아지게 되고 높은 Compaction이나 덮어쓰기, 삭제 등을 야기할 수 있다 . 따라서 level 0의 파일의 수를 잘 제어하여 Compaction을 최소화하면서 읽기 효율을 높일 수 있어야 한다. 현재 leveldb는 level 0의 파일의 수를 특정 임계값 4개를 사용하고 있고 데이터 2MB마다 하나의 파일을 구성하므로 8MB를 사용하는 것을 알 수 있다.

맞습니다. 특히 L0에서는 정렬이 되어 있지 않고, 중복된 key range가 허용되므로 compaction trigger threshold가 높을수록 읽기 증폭이 증가합니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.

[A]의 경우 throughput : 20.4MB/s, latency : 5.428 micros/op
[B]의 경우 throughput : 14.9MB/s latency : 7.413 micros/op

fillseq 옵션 경우 순서대로 각 level에 해당하는 write를 수행하고 fillrandom 옵션 경우 무작위로 level에 write를 한다. fillrandom 경우에 key range가 커서 겹치는 범위가 많아지면 많은 양의 read 및 불필요한 read 가 발생하고 merge sort를 하고 중첩된 데이터를 삭제한 후 무작위로 write를 하는데 낮은 level에 쓰기를 여러번 수행해야 한다면 그 level의 위치를 찾아야 하기 때문에 seek time이 fillseq 보다 더 걸리고 무작위로 write 하다가 낮은 레벨이 먼저 임계치를 넘게 되면 다시 compaction을 해야한다. 따라서 throughput나 latency 면에서 fillseq 가 더 좋은 option 임을 알 수 있다.

맞습니다. fillrandom은 중복된 key range가 존재하여, Compaction이 발생하고, 이로 인한 WAF로 인해 Write성능이 저하됩니다.

3-2. In benchmark A, SSTs are not written in L0. Why?

memtable 공간이 가득 차면 flush 되어 sstable의 L0부터 순서대로 write 된다. L0에서 임계치를 넘게 되면 compaction trigger가 되어 L1로 내려오는 과정을 반복하기 때문에 L0은 빈 공간이 된다.

fillseq같은 경우에는 key range가 겹치지 않으므로, L0와 L1의 Compaction을 피하기 위한 trivial move가 진행되어, 곧바로 L2에 저장됩니다.

3-3. Calculate SAF (Space Amplification Factor) for each benchmark.
fillseq 경우( ./db_bench –benchmarks=”fillseq,stats,compact,stats”)
SAF = (99+9)/110 = 0.98

fillrandom 경우 ( ./db_bench –benchmarks=”fillrandom,stats,compact,stats”)
SAF = (12+21+52)/69 = 1.23

맞습니다.

4-1. Which user key-value interface does each benchmark use?
[Load] -> Put
[A] -> Get
[B] -> Get
[C] -> lterator

A는 Iterator입니다. VScode의 go to definition/references를 통해 코드를 직접 확인해보시길 바랍니다.

4-2. Compare throughput and latency of each benchmark and explain why.
[Load] 7.335 micros/op 15.1 MB/s
[A] 1.040 micros/op; 106.4 MB/s
[B] 5.904 micros/op; (1000000 of 1000000 found)
[C] 6.306 micros/op; (1000000 of 1000000 found)

[Load] 를 통해 db를 만들고 [A]는 만들어진 db를 N 시간동안 차례대로 읽고 [B]는 무작위로 읽는다. [A]는 memtable에서 cache의 도움을 받을 수 있고 sstable에서 낮은 level로 읽어나가 seek time이 [B]보다 작기 때문에 성능이 좋다. [C]는 무작위 데이터를 range scan으로 해당 범위의 range 을 읽고 찾기 때문에 그만큼 seek time이 크기 때문에 제일 성능이 느린것을 알 수 있다.

A는 가장 작은 키부터 n개의 key를 iterator를 통해 순회합니다. A의 성능은 sequential read I/O로 인한 것 입니다. leveldb의 iteration은 L0에서 다음 레벨로 읽어나가는 것이 아닌, 모든 레벨에서 가장 작은 키부터 가장 큰 키까지 차례대로 순회하는 것입니다.
LevelDB의 캐시는 SST의 datablock을 캐싱합니다.
seekrandom은 특정키에 대해 seek연산만 진행하지, iterator를 통해 순회하지 않습니다. 순회하는 것이 range query/scan입니다.

5. The size of input kv pairs is the same. But One is better in throughput, the other is better in latency. Explain why.
   [A] 7.566 micros/op; 14.6 MB/s
   [B] 22.623 micros/op; 42.8 MB/s

[B]가 [A]보다 value size 가 커서 batch processing(일괄처리)에서 더 좋기 때문에 처리율이 좋다. 하지만 value size 가 클수록 중첩되는 key range가 커진다. compaction이 trigger 될때 원하지 않은 파일을 읽어 RAF 더 높아지고 그에 따라 지연 시간이 늘어나기 때문에 지연 시간은 [A]가 더 좋다.

key range는 value가 아닌 key를 기준으로 정의됩니다. benchmark A,B의 차이는 크게 적게 쓰느냐, 작게 여러번 쓰느냐의 차이입니다.

[min-guk]

2022.7.18 오후 12:40:23

1. Why do LSM-tree and LevelDB use leveled structure?

찾아보는데 소요되는 latency를 줄이기 위해서 leveled structure를 사용합니다.

L0에서 merge sort를 진행하는 싱글 레벨 LSM-tree는 모든 데이터가 한 레벨에 정렬되어 있으므로 읽기 성능이 뛰어납니다. 반면 매번 데이터를 디스크에 쓸 때 마다, Compaction을 진행해야 하므로 쓰기 성능이 낮습니다. LSM-tree는 write 성능을 위한 자료구조이므로, 멀티 레벨을 사용합니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?
   1차 minor compaction 산출은 메모리 데이터가 모두 포함된 0단 sstable 파일이지만 몇몇 0층 파일에는 데이터 오버랩이 존재할 수 있기 때문에 원래의 10^iMB 에 0을 대입하면 0이지만 8MB를 제공한다.

데이터 중복으로 인한 RAF를 감소시키기 위해 8MB라는 상한을 두었습니다.

[min-guk]

2022.7.18 오후 1:22:55

1. Why do LSM-tree and LevelDB use leveled structure?

1. PUT 의 측면
   케이스 1: 만일 level-1에 모든 1000000000000 개의 SSTable을 넣는다고 가정하자. 그리고 또 이 level-1이 데이터베이스 전체의 처음이자 마지막 레벨이라고 하자.

• 만일 level-1에 새로운 데이터가 PUT 된다면, 최악의 경우 1000000000000 개의 모든 SSTable을 merge sort 해야할 수도 있다. (만일 key range가 겹치는 SSTable들이 많다면). 그렇게 되면 PUT을 했을 때 처리시간이 많이 걸릴 수 있다.

맞습니다.

케이스 2: 만일 level-1에는 10개의 SSTable가 있고, level-2에는 100개의 SSTable가 존재한다. 또 각 fanout 이 10이라고 가정하자.

• 만일 level-1에 새로운 데이터가 PUT이 된다면, 최악의 경우 10개의 SSTable을 읽어본다. 하지만 10개의 SSTable를 가지고만 compaction을 할 것이다.
• 만일 방금 한 compaction이 level-2에 영향을 미친다고 가정하자. 그렇다고 하면, 최악의 경우 level-2 에 있는 SSTable를 추가적으로 더 compaction을 하게 될 것이다.
• 물론 정말 최악의 경우 Old Level에 내려가서 compaction을 하는 경우도 생길 것이다. 하지만 해당 old level로 내려가면서 level들을 compaction 하는 과정에서 중간에 compaction이 종료가 될 가능성이 존재한다.

맞습니다

따라서 한개의 level에 모든 SSTable을 다 넣게 된다면, PUT을 하는 과정에서 compaction을 하는 과정에서 SSTable을 확인하고 merge sort 하는 갯수가 처음부터 많다. 반면 여러개의 level을 운영하게 된다면, compaction을 하는 과정에서 한번에 모든 SSTable들을 다 처리하지 않고, 단계적으로 또 점차적으로 숫자를 늘려가면서 compaction을 할 수 있게 된다. 따라서 PUT의 측면에서 level을 가지고 있음이 유리하다.

맞습니다.

2. GET 의 측면

케이스 1: 만일 level-1에 모든 1000000000000 개의 SSTable을 넣는다고 가정하자. 그리고 또 이 level-1이 데이터베이스 전체의 처음이자 마지막 레벨이라고 하자.

• 만일 GET을 하여 한개의 Key value 값을 찾아야한다고 하면, 최악의 경우 우리는 1000000000000 개의 SSTable 중 마지막 SSTable에서 찾을 수 있다.

싱글 레벨 LSM-tree에서, Flush만 진행하고 Compaction을 진행하지 않는다면 맞습니다. 반면 Compaction을 진행하여 정렬되어 있다면, 하나의 레벨에서 하나의 SSTable을 통해 한번에 찾을 수 있습니다.

케이스 2: 만일 level-1에는 10개의 SSTable가 있고, level-2에는 100개의 SSTable가 존재한다. 또 각 fanout 이 10이라고 가정하자.

• 만일 GET을 하여, level-1 을 탐색하면, 최악의 경우 10개의 SSTable을 찾게 될 것이다. 만약 여기서 못찾는다면, 다음 level인 level-2 에 내려가서 찾게 될 것이다. level-2 는 총 100개의 SSTable을 가지고 있으니, 최악의 경우 100개의 SSTable만 찾으면 된다.

manifest는 따라서 각 레벨 별 sst의 key range를 관리합니다.

• 이런식으로 key-value 값을 찾아나갈 때, level을 가지고 있고 이런 level에 따라 찾아나가게 된다면 초기부터 찾아야 하는 값이 크지 않다. 뿐만 아니라, '잠재적'으로 중간 level에서 찾을 수 있다는 가능성도 존재한다.
• (물론 만일 찾는 데이터가 정말 old level에 존재한다면 사실상 맨 밑에 있는 SSTable 까지 찾아야하는 것은 마찬가지지만, 상대적으로 일반적인 케이스들을 본다면 중간 level들에서 찾을 가능성이 존재한다)
• 뿐만 아니라, LSM Tree 에서는 새로운 정보 즉 PUT 된지 얼마 안된 정보는 young level에 존재할 확률이 높다 (물론 level-2로 바로 떨어지는 경우도 있긴 하지만). 그렇기에 만일 우리에게 자주쓰고 자주 업데이트 되는 데이터가 존재한다면, young level에 놓게 될 것이다.

맞습니다. workload에 따라 다르지만 일반적으로 recent hot한 상위레벨에서 hit가 많이 됩니다.

• 가령 GET 하는 key-value 쌍이 level-1에 존재한다면, 우리는 10개의 SSTable만 조회해도 해당 key-value 값을 얻을 수 있게 된다. 또 만일 해당 key-value가 지속적으로 업데이트 되고 자주 쓰게 된다면, young level에 존재하게 될 확률이 크기 때문에탐색 시간이 줄어들 것이다.

그렇기에 만일 한개의 level에 모든 SSTable을 다 넣게 된다면, GET을 하는 과정에서 자료를 찾을 때 SSTable을 확인해야 하는 갯수가 늘어나고, 최근 사용하고 업데이트가 자주 되는 데이터가 존재하는 상황에서 또한 Level들을 사용하는 것이 효율적이다.

이건 싱글레벨에서 중복 key range를 허용하는가, 허용하지 않는 가에 걸린 것 같습니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?

/db/version_set.cc 에 정의된 VersionSet::Finalize는 왜 level-0이 특별하고 왜 level-0을 다른 level처럼 취급하지 않는지에 대한 정보가 담겨있다.

다음의 내용은 소스코드 일부를 찾아보며 왜 level-0이 8MB의 제한을 가지고 있는지에 대해서 추정해본 결과이다.

1. /db/version_set.cc 에 정의된 VersionSet::Finalize 에는 @ln 1153 언저리에 config::kL0_CompactionTrigger 를 사용한다.

2. config::kL0_CompactionTrigger 는 /db/dbformat.h 의 @ln 28에 다음과 같이 기본값으로 정의 되어있다:

// Level-0 compaction is started when we hit this many files.
static const int kL0_CompactionTrigger = 4;                                                           

4. 이 말은 level-0은 총 4개의 파일이 차게 되면 compaction이 이루어진다는 뜻이다.
5. /include/leveldb/options.h 의 @ ln 115 에는 max_file_size 가 선언되어있다..

size_t max_file_size = 2 * 1024 * 1024;

6. 이 말은 각 파일의 최대 크기는 2 * 1024 * 1024 bytes = 2MB 라는 의미이다..
7. 4.에 따라서 level-0에서 총 파일의 갯수는 4개까지 존재할 수 있다. 2MB * 4개 = 8MB. 따라서 최대로 level-0에 존재할 수 있는 데이터는 8MB가 될 것이다.

L0의 key range 중복이 발생함에 따른 RAF를 고려하여 상한을 두면서도, 너무 작게 설정하지는 않아 WAF를 줄인 것입니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.

Q1. Compare throughput, latency, and stats of two benchmarks and explain why.

$ ./db_bench --benchmarks="fillseq,stats,fillrandom,stats" --histogram=1 > result.txt
...

다음의 내용은 results.txt 내부의 내용이다.

Metric	A(fillseq)	B(fillrandom)
Throughput (MB/s)	63.3	31.2
Latency (Average microseconds)	1.7485	3.546

A (fillseq) - Stats

                               Compactions
Level  Files Size(MB) Time(sec) Read(MB) Write(MB)
--------------------------------------------------
  2       32       99         1        0       105
  3        2        6         0        0         0

B (fillrandom) - Stats

                               Compactions
Level  Files Size(MB) Time(sec) Read(MB) Write(MB)
--------------------------------------------------
  0        0        0         1        0       103
  1       19       36         1      154       138
  2       24       48         1      102        99

분석

fillseq 와 fillrandom 의 결과 중 모든 측면이 fillseq이 더 좋은 결과를 보여주었다. 이에 따른 분석은 다음과 같다.

/db/db_bench.cc 에 따르면 각각은 다음과 같이 정의되어있다.

• fillseq -- write N values in sequential key order in async mode
• fillrandom -- write N values in random key order in async mode

1. fillseq의 경우 key range의 overlapping이 발생하지 않는다. compaction의 방법은 다양하지만, 그 중 일부 compaction은 key range가 overlapping 되는 SSTable을 확인하고, 이런 SSTable들을 모두 merge sort한 이후 SSTable을 재구성한다. 하지만 fillseq의 경우, 이미 sequential 하게 PUT이 되기 때문에, overlapping이 생기지 않고, comapction시 그 어떤 SSTable끼리도 merge sort가 진행되지 않으니, merge sort 하는 시간이 없어진다.

맞습니다.

3. fillrandom의 경우 Key Range의 overlapping이 발생할 가능성이 농후하다. (운이 매우매우매우 좋다면 filseq과 같은 순차적으로 들어가는 경우도 생기겠지만, 이건 매우 특수한 경우니까 제외하고 일반적 케이스를 고려하자). fillrandom을 진행하면 key range의 overlapping이 생기고, compaction 도중 이런 overlapping 된 SSTable끼리 merge sort를 진행하기 때문에, 시간이 상대적으로 더 걸린다.

맞습니다. 부연 설명을 하자면, 하나의 sst가 2MB이고 kv pair가 116B이므로 entry수는 20,000개입니다. uniform random이고 key range가 좁아 compaction이 발생합니다. 더 궁금하다면 코드를 확인하시길 바랍니다.

따라서 fillrandom과 fillseq의 사이에서 fillseq의 결과가 더 좋은 이유는 key range의 overlapping에 따른 compaction 시의 merge sort 여부때문이다.

맞습니다.

3-2. In benchmark A, SSTs are not written in L0. Why?
fillseq의 경우 key order에 맞추어서 sequential 하게 작성한다. leveldb에서는 immutable을 SST file로 작성할 때, flush를 하게 된다. 이때 flush할 때, trivial move가 생길 수도 있다. trivial move는 immutable을 최대한 아래의 level에 놓게 하려고 하는데, 이 trival move가 충족되는 조건은 다음과 같다.

1. 현재 level의 SSTable과 overlapping되지 않을 때.
2. 다음의 level에 있는 SSTable중 10개 미만으로 overlapping 될 때.

추가적인 설명은 (비록 rocksdb wiki이지만) https://github.com/facebook/rocksdb/wiki/Compaction-Trivial-Move 여기서 찾아볼 수 있었다.

fillseq의 경우 이미 key가 sorting 된 상태로 존재하고, 이게 sequential 하게 작성이 된다. 그렇기 때문에, 각 SSTable의 key range끼리 overlapping이 되지 않는다. 따라서 trivial move의 1. 2. 의 모든 조건을 만족한다. (현 level에서 overlapping이 일어나지 않는 것 처럼, 다음 level에서 overlapping이 일어나지 않는다)

따라서 fillseq시 trivial move를 할 수 있는 조건을 만족한다. 우리가 fillseq을 통해서 작성하는 데이터는 총 (16byte + 100byte)* 1000000 ≈ 110.6MB 이다. 데이터를 작성하면 다음의 상황이 생길 것이다. (단 전제는 manual compaction을 하지 않고, 자동으로 compaction을 사용한다는 가정이다, 또한 compression은 고려하지 않았다)

여기까지는 맞습니다.

1. level-0에 데이터를 하나씩 넣다보면, 제한인 8MB를 다 채우게 된다. 따라서 compaction trigger에 의해서 compaction이 시작된다.
2. level-0의 8MB에 해당하는 모든 데이터가 level-1로 내려간다
3. level-0에 또 다시 데이터를 넣다보면 제한인 8MB를 다 채우고 compaction이 시작된다.
4. level-0에서 level-1로 compaction을 한다. 따라서, level-0에서 level-1로 총 8MB를 그대로 옮긴다. 이렇게 되면 level-1의 제한인 10MB를 초과한다.
5. level-1에서 level-2로 compaction을 한다. 따라서 level-1에서 level-2에 16MB데이터를 보낸다. 따라서 level-2에는 16MB가 저장되어있다.
6. 이후 또 데이터를 지속적으로 채우다보면, level-0은 8MB를 채울 것이고, 이후 compaction이 일어나게 된다. compaction시 trivial move의 조건을 모두 만족한다. (level-1, level-2 모두 overlapping 되는 SSTable이 존재하지 않으므로)
7. 따라서 level-0에서 level-2로 바로 내려간다.

바로 memtable에서 L2로 내려갑니다. db_bench에서 num을 조절하여 실험적으로 확인하시길 바랍니다. 복잡한 케이스에는 실제로 뜯어보고, 돌려보며 이해하는 것이 빠릅니다.

fillseq의 경우에는 SSTable들간의 overlapping이 생기지 않는다. 그렇기에 compaction시 trivial move를 하게 되고, level-0을 건너뛰고 데이터를 작성하게 되므로 level-0에 데이터가 작성되지 않는다.

3-2. Calculate SAF (Space Amplification Factor) for each benchmark.

$ ./db_bench --benchmarks="fillseq,stats,compaction,stats" 
... 
------------------------------------------------
fillseq      :       1.682 micros/op;   65.8 MB/s

                               Compactions
Level  Files Size(MB) Time(sec) Read(MB) Write(MB)
--------------------------------------------------
  2       32       99         1        0       105
  3        2        6         0        0         0

compact      : 1159490.000 micros/op;

                               Compactions
Level  Files Size(MB) Time(sec) Read(MB) Write(MB)
--------------------------------------------------
  2        0        0         1        0       110
  3       67      110         1       97        97

• fillseq 시 level-0에서 105MB를 write 했다.
• compact 시 level-2 에는 110MB, level-3 에는 97MB를 write 해서 총 207MB를 write 했다.

SAF는 Actual Used Space / Required Space 의 계산을 할 수 있다.

SAF = 'used db size / total user request data size'입니다. 구글링 해보시길 바랍니다.

따라서 Compact 시 Write / fillseq 시 Write 를 계산하면 SAF를 구할 수 있다. 이는
207MB / 105MB ≈ 1.97.

따라서 A(fillseq) 의 경우 SAF는 약 1.97이 계산된다.

B (fillrandom)

$ ./db_bench --benchmarks="fillrandom,stats,compaction,stats" 
...
------------------------------------------------
fillrandom   :       3.006 micros/op;   36.8 MB/s

                               Compactions
Level  Files Size(MB) Time(sec) Read(MB) Write(MB)
--------------------------------------------------
  0        7       22         1        0       103
  1       14       26         1      113       103
  2       23       43         1       90        88

compact      : 1704392.000 micros/op;

                               Compactions
Level  Files Size(MB) Time(sec) Read(MB) Write(MB)
--------------------------------------------------
  0        0        0         1        0       104
  1        0        0         1      158       141
  2       35       69         2      221       202

• fillrandom 시 level-0에서 103MB, level-1에서 103MB, level-2에서 88MB를 write 해서 총 294MB를 write 했다.
• compact 시 level-0에서 104MB, level-1에서 141MB, level-2에서 202MB를 write 해서 총 447MB를 write 했다.

SAF는 Actual Used Space / Required Space 의 계산을 할 수 있다.
따라서 Compact 시 Write / fillrandom 시 Write 를 계산하면 SAF를 구할 수 있다. 이는
447MB / 294MB ≈ 1.52.

따라서 B(fillrandom) 의 경우 SAF는 약 1.52이 계산된다.

SAF는 사용자가 요구하는 데이터를 저장하는 데 필요한 공간입니다. 따라서 유저가 요청한 총 kv pair 대비 얼마나 많은 스토리지를 사용하여 DB가 이를 저장하는 가를 따져보는 것입니다.

4-1. Which user key-value interface does each benchmark use?

• A(readseq) : "Get"
• B(readrandom) : "Get"
• B(seekrandom) : "Iterator"

코드를 따라가며 확인해보시길 바랍니다. A는 iterator->next, B는 iterator->seek입니다.

4-2. Compare throughput and latency of each benchmark and explain why.

echo "LoadDB"
./db_bench --benchmarks="fillrandom" --use_existing_db=0
echo "A: readseq"
./db_bench --benchmarks="readseq" --use_existing_db=1 --histogram=1
echo "B: readrandom"
./db_bench --benchmarks="readrandom" --use_existing_db=1 --histogram=1
echo "C: seekrandom"
./db_bench --benchmarks="seekrandom" --use_existing_db=1 --histogram=1

결과

Metric	A(readseq)	B(readrandom)	C(seekrandom)
Throughput (MB/s)	335.9	?	?
Throughput (micros/op)	0.329	1.899	1.572
Latency (Average microseconds)	0.3293	1.8893	1.5721
Latency (Std Dev)	0.83	5.99	0.77

B, C의 경우 Throughput (MB/s) 대신 (1000000 of 1000000 found) 로 나타나서 해당 값을 알 수 없는 상태임.

분석

db_bench.cc 에 따르면 각각은 다음과 같이 정의되어있다.

• readseq -- read N times sequentially
• readrandom -- read N times in random order
• seekrandom -- N random seeks

공통

일단 LoadDB 단계에서 fillrandom을 하며, compaction에 의해서 mergesort 가 실행된다. 그렇기에 이미 데이터는 각 Level들의 Key값들이 순차적으로 sorting이 되어있는 상태이다.

A (readseq)

readseq 으로 순차적으로 N회 read를 할 때, 각 데이터들이 이미 정렬이 되어있는 상태이고, 만일 순차적으로 비교적 가까운 값들을 읽어나간다면 (가령 Key가 1인 값을 읽고, 다음 Key가 2인 값을 읽는다고 하면), 같은 Level에서 확인을 해나가면 되기 때문에 Latency, Throughput 모두 가장 좋은 결과를 보여준다. (물론 연속된 Key값중 다음 Key값이 다음 Level에 존재할 가능성도 존재하지만, 그래도 극단적으로 level-1 -> level-5 이런식으로 움직이지는 않을 것이다).

극단적으로 L0 -> L5 -> L1 이렇게 움직입니다. gdb를 통해 scan시의 merger iterator를 확인해보시면 됩니다. 따라서 b-tree보다 lsm-tree는 낮은 scan성능을 보입니다.

즉 이말은, key를 순차적으로 찾아가기에 찾는 key들의 level이 동일할 확률이 높다. 이에 대해 생각해 볼 수 있는 것이, Latency의 측면에서 Standard deviation 값이 0.83 으로 다른 readrandom, seekrandom에 비해서 월등히 낮은 값을 보여주는 것을 근거로 삼을 수 있다.

이는 sequential I/O인가, random I/O인가의 차이와, 몇 번을 탐색하는 가의 차이입니다.

B (readrandom)

readrandom 을 하여 이런 저런 데이터들을 random하게 read해 나간다면, 다양한 Level들을 왔다갔다 해야한다. 가령 Key 가 1이고 level-1에 존재하고, 다음 Key가 임의로 생성된 999999라는 값이고, level-3에 존재한 이후, 또 다음 Key가 임의로 생성된 54라는 값이고, level-1에 존재한다고 가정하자. 이렇게 random 한 key 값들을 찾아나가는 과정에서는 그렇게 된다면, level-1, 다음은 level-3, level-1 이런식으로 다양하게 나타날 것이다.

모든 키를 찾을 때, 순서대로 mem->immutable_mem -> L0 -> L1 -> ... 이런식으로 찾다가, 해당 키를 찾으면 탐색을 그만 둡니다. 레벨끼리는 key_range가 중복되기 때문이죠.

즉 이 말은, 만일 young level 에 존재하는 key, value 쌍이면 접근 시간이 얼마 걸리지 않을 것이지만, 반면 old level에 존재하는 key, value 쌍이라면 접근 시간이 상대적으로 길어질 수 있음을 의미한다. 이는 Latency의 Standard deviation 값이 5.99로 readseq에 비해서 상대적으로 큰 값을 보여주는 이유를 설명한다. 따라서 read하는 key가 존재하는 Level에 따라서, read time에 큰 편차가 생길 수 있다고 해석된다.

readseq는 이어서 차례대로 읽기 때문에 빠르고, readrandom은 어디까지 탐색하는 지 그 레벨의 편차가 존재하므로 표준편차가 커집니다.

C (seekrandom)

leveldb 에서는 seek 연산을 하기 위해서 cursor를 통해서 min-heap을 구성한다. seekrandom의 경우 random 하게 seek을 하는 과정을 거친다. Seek을 하며 만일 특정 범위의 값들을 읽어나간다면, seek 하는 range 내부의 cursor들을 찾고, min-heap을 지속적으로 구성해나갈 것이다. (:D-MOOC
비정형 빅데이터를 위한 키-밸류 DB 강의 04_02 @ 24분)

leveldb는 min-heap을 사용하지 않고 merge iterator를 활용합니다. 시간복잡도는 O(n)입니다. REMIX라는 LSM-tree만이 특이하게 min-heap을 활용하는데, 해당 kv store는 range scan에 특화되어 있기 때문입니다.

앞서 말한 것 처럼, LoadDB단계 이후 compaction에 의해서 각 level들은 sorting이 이미 되어있는 상태이다. 그 뜻은 readrandom에 비해서는 상대적으로 level을 위 아래로 내려갈 가능성이 낮다는 의미를 한다. cursor를 찾으며 같은 level 내부에 존재하는 sstable들을 찾고, 이후에 없으면 다음 level로 내려가기 때문이다.

모든 레벨에 커서를 꽂아야 하므로 더 성능이 좋지 않습니다. latency (micros/op)는 the lower, the better입니다.

따라서 Latency 측면에서 Standard deviation 값이 0.77이다. 하지만 다만 여러가지의 값들을 지속적으로 찾고 min-heap을 구성해나가는 방식이 조금 시간이 더 걸리기 때문에 Latency 측면의 average가 1.5721로 readrandom보다는 좋지만 readseq에 비해서는 별로 좋지 않은 결과를 보여준다고 해석된다.

모든 케이스 전부 모든 레벨에 커서를 다 꽂아야하므로, readrandom보다 편차가 적습니다.

Q. The size of input kv pairs is the same. But One is better in throughput, the other is better in latency. Explain why.

결과

Metric	A	B
Throughput (MB/s)	36.1	56.3
Throughput (micros/op)	3.062	17.205
Latency (Average microseconds)	3.0623	17.2039
Latency (Std Dev)	35.28	194.17

A vs B

• A 의 경우 각 Key size 는 16byte, Value size 는 100byte 이다. 따라서 총 Key value size 는 116byte이다.
• B 의 경우 각 Key size 는 16byte, Value size 는 1000byte 이다. 따라서 총 Key value size 는 1016byte이다.

116 * 1000000 = 1016 * 114173 이므로, 결과적으로 A, B 모두 사실상 똑같은 데이터의 총 size를 fillrandom 을 통해서 작성한다. 하지만 두개의 실행 결과에는 차이가 보여진다.

A가 B보다 Throughput과 Latency 측면에서 좋은 성능을 보여준다. (Throughput (MB/s)의 경우 A가 B보다 낮은 수준을 보여주는 것은 B의 Key value size가 A에 비해서 9배정도 크기 때문인 것으로 추정된다).

A가 latency가 좋고, throughput(bandwidth)이 안 좋습니다.

이는 WAL/Manifest 때문인 것으로 보여진다. LevelDB에서는 처음에 put 연산이 일어날 시, WAL에 먼저 적은 이후, 다음에 Batch Write를 실행한다. 이 Batch Write를 통해서 디스크 파일에 각 Key value 값을 저장하게 된다. 하지만 여기서 다소의 차이가 생기는 것으로 추정된다.

leveldb의 문서들로 다음의 내용을 알 수 있다.

• 각 Log file은 32KB block으로 구성이 된다. 그리고 각 Block은 chunk의 sequence로 구성이 된다. @ 2주차 강의자료
• Example에 따르면 length 1000의 경우 1개의 FULL record로 1개의 block 에 작성된다. @ /doc/log_format.md

따라서 우리는 A의 경우와 B의 경우 모두 1개의 chunk에 모두 저장이 되는 것을 알 수 있다. (왜냐면 B가 1000byte인데 1개의 chunk에 FULL record로 작성된다고 했으니까, 이보다 작은 100byte의 A 또한 당연히 FULL record로 작성될 것이다). 하지만 여기서 차이점이 생긴다. A의 경우 총 저장해야하는 공간은 116byte이지만, B의 경우 총 저장해야 하는 공간은 1016byte이다.

32KB 짜리 Log file 의 block 에 작성을 하게 되면 다음처럼 된다 (header의 7바이트는 생략하고 그냥 정말 막 계산하면 다음처럼 된다)

• A : 32 * 1024byte / 116byte ≈ 282개 (실제로는 이것보다는 덜 들어갈 것이다 header 때문에)
• B : 32 * 1024byte / 1016byte ≈ 32개 (실제로는 이것보다는 덜 들어갈 것이다 header 때문에)

즉 하나의 Log file에 block을 작성하고 이를 처리할 때, A의 경우 한번의 write batch 에 282의 value를 저장할 수 있다. 하지만 B의 경우 write batch에 32개의 value를 저장할 수 있다. 한번의 write batch 에 따라서 A가 B보다 많은 양의 데이터를 저장할 수 있으니, A가 B보다 결과가 더 좋은 것으로 해석된다.

WAL에 대한 해석은 신선하네요. 그럼에도 WAL에서도 크게 적게 쓰는 것이, 작게 여러번 쓰는 것보다 처리율은 좋고, 응답속도는 나쁠 것 입니다.

[min-guk]

오늘은 여기까지만 하겠습니다. ㅎㅎ;;

[min-guk]

2022.7.18오후 2:42:21
1. Why do LSM-tree and LevelDB use leveled structure?

LSM tree의 구조는 memtable과 immutable memtable이 존재하는 memory와
여러 level들로 이루어져 있고 각 level에는 sstable들이 있는 ssd로 이루어져 있습니다.
LSM-tree의 ssd는 여러 level로 나뉘어져 있으며 각 level(i+1)이 level(i)보다 10배 크도록 구성되어 있습니다.

스터디의 마지막 시간 한 학우분이 여쭤보신것처럼 그리고 https://stackoverflow.com/questions/68297612/why-rocksdb-needs-multiple-levels
위 주소의 stackoverflow에서의 질문점 처럼 level1에서는 모든 키가 정렬되어 있기에(level0에서 merge sort하여 skiplist를 통해 자동 정렬) 저 또한 레벨구조가 굳이 필요한가에 대한 고찰을 하였습니다.

put이 발생하여 ssd에있는 log에 기록된 뒤 memtable -> immutable memtable을 거치며 immutable memtable이 꽉차게 되어 flush되어 level0으로 내려왔다고 가정해보았습니다.
그다음 대량의 put이 발생하면 level0이 꽉차게 되어 level1로 compaction되고 level1또한 꽉차게 되어 level2로 compaction되어집니다. 이 상황에서 데이터의 약 90%는 level2에 존재하게 됩니다.{각 level(i+1)이 level(i)보다 10배 크도록 구성
100의 데이터를 넣을 경우(level0의 최대 크기 10가정)
level0에 10(10%)
level1에 90(90%)
}
이 때 level0-> level1의 compaction은 매우 작아지게 되며 compaction에 대한 쓰기증폭(WAF)가 큰 폭으로 줄어들게 됩니다. 다중 레벨 구조를 가질수록 compaction에 대한 문제중 하나인 쓰기증폭이 줄어들게 됩니다. 또한 level0을 제외한 각 level(i)들은 데이터 겹침이 없으므로 검색 프로세스를 최적화할 수 있어 최대 하나의 파일 순회만 완료할 수 있습니다. 이를 통해 LSM-tree와 LevelDB등은 compaction에 대한 증폭들(읽기, 쓰기 등)을 줄이기 위해 leveled structure를 사용한다고 이번 숙제에 대해 구글링하며 배우게 되었습니다.

맞습니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?
   leveled structure에서 각 level(i+1)이 level(i)보다 10배 크도록 구성되어 있기 때문에 max level의 크기는 10^iMB이지만 level0의 크기가 8MB인 이유에 대하여 생각해보았습니다.

먼저 구글링, 공부를 통해 알아보기전 먼저 제가 생각해본 바로는 질문 1의 대답과 비슷하게
level0의 크기가 10^i로 커질 경우 level1(2,3,4,...i)과는 달리 level0의 경우 중복되는 key-value쌍들이 있는 sstable을 가지고 있으므로 읽기 증폭이 커지게 될것이고 쓰기 증폭또한 immutable memtable에서 level0으로 flush될 때 매우 커지게 될것이라고 예상하였습니다.

leveldb핸드북을 구글번역기를 통해 공부한 결과 사용자의 쓰기 속도가 항상 주요 압축 속도보다 높으면 계층 0의 파일 수는 계속 증가하고 사용자의 읽기 효율성은 계속해서 떨어진다고 명시되어 있으므로 leveldb는 다음을 정의하였습니다.
level 0 파일 수가 SlowdownTrigger를 초과하지 않도록 해야하며 여기서 SlowdownTrigger가 바로 level0의 최대 크기 8MB라고 볼 수 있습니다.

맞습니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.

[A]는 순차적으로 각 Level의 sstable에 데이터를 넣는 방식이고
[B]는 마찬가지이지만 무작위로 데이터를 넣는 방식입니다.(인덱싱)

fillseq의 결과로 5.300 micros/op; 20.9 MB/s가 도출되었고
fillrandom 의 결과로는 7.524 micros/op; 14.7 MB/s가 도출되었습니다.
다만 leveldb의 전반적인 지식 부족과 구글링을 함에도 결과에 대한 직접적인 설명이 없었고
벤치마크등과 파라미터등에 관한 설명만이 존재했기에 각각 결과가 정확히 무엇(throughput, latency)을 의미하는지는 파악하지 못하였습니다.

다만 제가 생각한바로는 각 결과의 micros/op가 각 benchmark의 latency를 나타내는것이며
[A]의 경과율이 [B]의 경과율보다 낮게 걸렸음을 알 수 있었으며
[A]의 처리율이 [B]의 처리율보다 많았음을 결과를 통해 확인 할 수 있었다고 생각하였습니다.

이를 기반으로 분석하였을 때
[A]의 경과율이 낮음에도 불구하고 [B] benchmark보다 처리율이 많은것으로 보아 새로운 데이터베이스를 순차적으로 만드는 [A]가 [B]보다 성능이 좋다는 것을 파악하였습니다.

LSM-tree 기반 key-value store는 새로운 데이터의 추가 및 기존 데이터의 update를 모두 새로운 record로 SSTable 단위로 batch로 기록하여 sequential write을 사용하여 쓰기 성능을 높인다는 지식을 이 코드를 실행하며 그리고 구글링을 통하여 습득하게 되었습니다.

(batch, 배치작업은, 데이터를 실시간으로 처리하는게 아니라, 일괄적으로 모아서 처리하는 작업을 의미)

fillseq이 성능이 좋고, 성능이 좋은 이유는 key range가 겹치지 않아서 compaction이 발생하지 않기 때문입니다.

3-2. In benchmark A, SSTs are not written in L0. Why?
각 stats를 분석하였을 때 fillseq의 경우 level0, 1이 없음을 putty를 통해 확인하였었는데 이는 시스템이 유사한 성능을 가지고 있는 fillseq 벤치마크의 특징 때문에 ssd에 순차 쓰기를 스트리밍하고 압축 을 일으키지 않습니다. 키값 쌍은 메모리에 버퍼링되고 이미 주문된 SST에 덤프됩니다. 즉, 압축 없이 단순히 하위 수준으로 이동됩니다.
(출처 , https://www.pdl.cmu.edu/PDL-FTP/FS/CMU-PDL-19-102.pdf / 18page)

key range가 겹치지 않아, trivial move가 발생하기 때문입니다.

3-2. Calculate SAF (Space Amplification Factor) for each benchmark.
먼저 rocksdb는 B tree가 아닌 LSM-tree구조를 사용합니다.
LSM-tree의 특징중 하나인 out-place Update로 인해 새로이 key가 중복되는(이미 테이블안에 있는) 데이터를 update할 때 이전 항목을 덮어쓰지 않고 새로운 위치에 update합니다.
이 때문에 SAF 즉, 공간증폭이 발생하게 됩니다.

SAF를 계산하는데에는 아래 두 강의자료의 도움을 받았습니다.
https://github.com/DKU-StarLab/leveldb-study/blob/761b550973ab6d1e88189190e66c0ee19a52aa12/introduction/Jongmoo%20Choi,%20Key-Value%20Store%20-%20Database%20for%20Unstructured%20Bigdata,%202021.pdf

https://www.flashmemorysummit.com/English/Collaterals/Proceedings/2014/20140805_D12_Dong.pdf

SAF의 계산은
실제 사용하고 있는 공간 / 사용자가 쓰려고 하는 데이터
로 계산되기 때문에 각 benchmark를 통해 db_bench,stats를 분석한 결과
(실행 시마다 소수점은 달라질것으로 추측)
[A]의 SAF는 108(level2's size + level'3 size) / 108(write) = 1
[B]의 SAF는 84(level0's size + level1's size + level'2 size) / 103(level0's write) = 0.8x

+추가
공간 증폭 은 데이터 크기에 대한 디스크의 데이터베이스 파일 크기의 비율입니다. 데이터베이스에 10MB를 넣고 디스크에서 100MB를 사용하는 경우 공간 확장은 10입니다. 일반적으로 디스크 공간이나 메모리가 부족하지 않도록 공간 확장에 대한 하드 제한을 설정하기를 원할 것
https://zhangyuchi.gitbooks.io/rocksdbbook/content/RocksDB-Tuning-Guide.html

맞습니다.

4-1. Which user key-value interface does each benchmark use?
아래 깃허브 소스코드를 분석하였습니다.
https://github.com/facebook/rocksdb/blob/main/tools/db_bench_tool.cc

[Load] fillrandom = write

[A] readseq = read
[B] readrandom = read
[C] seekrandom = seek

다만 각 벤치마크들마다 제가 작성한 사용자 인터페이스 외에도 다른 인터페이스가 있을것으로 추측됩니다.

fillrandom은 put, readseq은 iterator->next, readrandom은 get을 사용합니다.

4-2. Compare throughput and latency of each benchmark and explain why.
[Load] fillrandom : 7.440 micros/op(=µs,마이크로초)(latency) 14.9MB(throughput)
=> 7.440의 latency가 걸림과 데이터베이스에 14.9MB/s를 쓰고있음

[A] readseq
=>1.041 micros/op; 106.2 MB/s
[B] readrandom
=>5.887 micros/op;
[C] seekrandom
=> 6.375 micros/op;

sequential하게 data를 쓸 때 성능이 증가하는 lsm-tree구조의 특성에 의해서
[A]readseq가 [B], [C]보다 latency가 적게 경과함을 알 수 있었습니다.

sequential read가 좋은 이유는 lsm-tree 구조보다는 sequential I/O와 seek를 한번 밖에 하지 않는 다는 점입니다.

Q. The size of input kv pairs is the same. But One is better in throughput, the other is better in latency. Explain why.
[A]
=> 23.485 micros/op; 41.3 MB/s
[B]
=> 7.234 micros/op; 15.3 MB/s

[A]와 [B] benchmark의 다른점은 num과 value_size입니다.
소스코드를 분석한 결과 num은 데이터베이스에 위치할 key/value쌍의 갯수를 의미합니다.
value_size는 말 그대로 key-value쌍에서 각 value의 size를 의미합니다.

key-value쌍의 크기가 훨씬 큰 B가 latency가 A보다 더 작은 이유는 value_size에 달려있다고 생각합니다.
value_size가 작으면 k-v 데이터를 메모리에 쓸때나 flush할때나 compaction할 때 latency가 경감하기 때문입니다.

작게 여러번 하는 것이 latency에서는 유리하나, 처리율에서는 불리합니다.

숙제가 주어졌을 때 미루지 않고 하는 스타일이지만 이번 숙제에 대해서는 의도한바는 아니지만 조금 다른 방식으로 수행하였습니다.

문제 하나하나에 대해서 여러 논문과 구글링을 이용하여 질문의 뜻을 이해하였고
지금까지 학부생활을 지내오며 오픈소스에 대해서 직접 분석할 기회가 많이 없었는데 leveldb의 c코드를 조금 엿보며 ./db_bench를 입력하면 이 소스코드들을 통해 결과가 출력되는구나를 직접 putty에서 실행해보고 소스코드와 대조하며 분석하면서 모든것이 새롭게 느껴졌습니다.

현재의 저는 정말 부족하고 이해못한 부분이 많지만 스터디가 끝나갈 때가 되었을 때는 전부를 이해하진 못하더라도 타인에게 rocksdb, leveldb에 대해 자신있게 설명할 수 있었으면 함이 이번 스터디의 목표임을 2주차 숙제를 통해 확실하게 정하게 되었던 것 같습니다.

네, 열심히 참여해주셔서 감사합니다. 앞으로도 잘 부탁드립니다.

[min-guk]

2022. 7. 18 오후 6:48:01

2023. Why do LSM-tree and LevelDB use leveled structure?
      쓰기 증폭을 줄이기 위해서다. 각 레벨에서 허용가능한 용량이 꽉 차면 그 레벨의 SSTable들과 다음 레벨의 SSTable들을 골라 merge sort하는 compaction이란 작업을 한다. 만약 하나의 레벨만 가진 구조거나 두 개 정도의 레벨만 가진 구조라면 이런 compaction하는 과정에서 엄청나게 많은 SSTable들이 선택되어 merge sort가 이루어질 것이고 이는 쓰기 증폭이 매우 커지게 된다. 그러나 멀티 레벨 구조로 관리한다면 각 레벨에서 compaction이 이루어질 때 merge sort를 하기 위해 골라지는 SSTable들(즉 후보들)의 양이 줄게 되고 이는 쓰기 증폭을 줄이는 효과를 가져다줄 수 있다. LSM-Tree는 실시간으로 저장(즉 write)하는 데이터가 많은 경우에 사용할 목적으로 설계되어 있기 때문에 이러한 레벨 구조를 사용해 write에 사용되는 오버헤드(쓰기 증폭)을 최대한 줄이는 방향으로 설계한 거라 생각할 수 있다. 단 이런 설계는 읽기 증폭은 좀 늘리는 단점이 있다(같은 키를 갖는 데이터가 여러 레벨에 분포할 수 있음)

맞습니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?
   Level 0는 write buffer(MemTable)로부터 데이터가 내려오는 곳으로 다른 레벨들과는 달리 키가 중복되는 데이터들이 존재할 수 있다. 그래서 Level 0 → level 1으로 이루어지는 compaction은 cost는 꽤 큰 편인데, 이 때 Level 0에서 수용가능한 데이터 양이 너무 적다면 level 0 → level 1 compaction이 자주 발생할 것이니 level 0 의 size를 너무 작게 하는 건 좋지 않다. (따라서 10^0 = 1MB로 하지 않음). 그렇다고 level 0의 용량을 너무 크게 하면 read의 효율성이 떨어지게 된다.

맞습니다.
왜 굳이 8MB로 한 건지는 정확하게는 잘 모르겠지만.. 위에서 쓴 문제들 때문에 level 0에서 수용가능한 파일 수(SSTable 개수)를 4개로 지정하고 4개가 되면 level 0 → level 1 compaction이 trigger되도록 한 것 같다, 이 때 SSTable의 기본 사이즈가 2MB이기 때문에 level 0의 사이즈를 2MB * 4 = 8MB로 만든 것 같다(근데 이것 역시 SSTable의 size를 저마다 다르게 얘기해서 정확히는 모르겠다..)
맞습니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.
LevelDB: version 1.23
Date: Mon Jul 18 17:28:01 2022
CPU: 1 * Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
CPUCache: 12288 KB
Keys: 16 bytes each
Values: 100 bytes each (50 bytes after compression)
Entries: 1000000
RawSize: 110.6 MB (estimated)
FileSize: 62.9 MB (estimated)
WARNING: Snappy compression is not enabled

---

fillseq : 6.387 micros/op; 17.3 MB/s

Level Files Size(MB) Time(sec) Read(MB) Write(MB)

2 32 99 2 0 108
3 3 9 0 0 0

---

fillrandom : 10.742 micros/op; 10.3 MB/s

Level Files Size(MB) Time(sec) Read(MB) Write(MB)

0 6 19 2 0 103
1 7 12 4 128 120
2 28 55 4 151 141

fillseq가 하나의 write를 처리하는데 걸리는 시간(지연율)이 더 짧고, fillseq가 같은 시간에 처리하는 양이 더 많다. 이는 디스크에 순차적으로 접근할 시엔 seek time으로 인해 낭비되는 시간이 줄기 때문이라고 생각된다. 또한 stat을 보니 fillseq로 했을 땐 level 0와 level 1의 SSTable들은 안 채워졌고, 각 level에서 read는 한 번도 발생하지 않았음을 확인했다.

fillseq과 fillrandom 모두 memtable이라는 write buffer에서 모아쓰므로 디스크에 순서대로 씁니다. 다만 버퍼에서 정렬을 유지할 때, fillseq이 cpu cache 히트율에서 보다 유리합니다.

3-2. In benchmark A, SSTs are not written in L0. Why?
flush가 일어나고 trivial move가 발생해서 그렇다. 또한 fillseq로 했을 때 stats을 찍어보면 fillrandom으로 했을 때와는 다르게 read역시 한 번도 일어나지 않았는데 이 역시 trivial move때문인 것 같다(메모리에 읽는 작업없이 레벨만 쏙 내리니까)

맞습니다.

3-2. Calculate SAF (Space Amplification Factor) for each benchmark.
SAF(공간 증폭) = 실제 사용된 공간 / 필요했던 공간..필요했던 공간은 62.9MB인 것 같은데, 실제 사용된 공간을 뭘로 잡아야 하는지 모르겠다..

각 레벨 별 SST의 합으로 잡으시면 됩니다.

4-1. Which user key-value interface does each benchmark use?
A는 Iterator, B는 Get, C는 Iterator

맞습니다.

4-2. Compare throughput and latency of each benchmark and explain why.
readseq : 3.197 micros/op; 34.6 MB/s

readrandom : 6.488 micros/op; (1000000 of 1000000 found)

seekrandom : 6.997 micros/op; (1000000 of 1000000 found)

순차적 접근이 임의 접근에 비해 seek time에 쓰이는 시간이 더 적어서 readrandom과 seekrandom보다 readseq가 더 빠르다.

맞습니다. 또한 탐색을 한번 밖에 하지 않는 점도 중요합니다. readrandom과 seekrandom의 차이는 어느 레벨까지 탐색하느냐입니다.

Q. The size of input kv pairs is the same. But One is better in throughput, the other is better in latency. Explain why.
A, B 둘다 쓰여지는 데이터들의 용량은 똑같지만, A는 한 개의 데이터용량이 비교적 작은 대신 더 많은 개수의 데이터들이 들어가고 B는 한 개의 데이터용량이 비교적 큰 대신 더 적은 개수의 데이터들이 들어간다.

A 지연율, 처리율 : 10.602 micros/op; 10.4 MB

B 지연율, 처리율 : 22.026 micros/op; 44.0 MB

지연율의 경우 A가 더 빠르고 처리율의 경우 B가 더 크다. write해야 할 데이터의 용량이 작을수록 시간이 덜 들기 때문에, 데이터 하나하나의 용량이 비교적 작은 A가 B에 비해 더 빠른 지연율을 보인다고 생각한다. 또한 levelDB는 Batch Write기능을 제공하는데 이로 인해 여러 write들이 하나로 묶여 한꺼번에 처리되기 때문에 데이터 하나하나의 용량이 더 큰 B가 A에 비해 처리율이 높다고 생각한다.

정답!

[min-guk]

2022.7.18 오후 8:11:39

1. Why do LSM-tree and LevelDB use leveled structure?
   leveled structure를 사용하면 상위 레벨의 용량이 초과 될 때 하위 레벨로 옮겨지게 되는데, 이 과정에서 compaction을 해주어 write amplication을 줄일 수 있기 때문에 사용한다.

맞습니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?
   레벨 0은 바이트 수가 아니라 파일 수로 설정해주었는데(파일 수가 4가 될 때마다 compaction이 되도록), 버퍼 사이즈가 클수록 너무 많은 레벨 0 compaction을 하지 않는것이 좋고, 작은 크기의 너무 많은 파일을 피하기 위해 사이즈를 8MB로 해주었다.

RAF를 피하기 위해 상한을 두었으며, 너무 작으면 WAF가 커지므로 8MB입니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.
A는 key 값을 순서대로 쓰는 반면, B는 key 값을 무작위 순서로 써서 compaction 하는 과정에서 시간이 많이 걸리게 되고, throuput이 상대적으로 낮게 나온다.

A는 key range가 겹치지 않아, compaction이 trigger되지 않습니다.

3-2. In benchmark A, SSTs are not written in L0. Why?
A의 memtables은 이미 정렬이 되어있기 때문에 flush 되어 저장되기 전에 새로 정렬해줄 필요가 없다.

trivial move로 인하여 그렇습니다.

[min-guk]

2022.7.18 오후 9:07:07

1. Why do LSM-tree and LevelDB use leveled structure?
   write amplification을 완화하기 위해서

맞습니다

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?
   읽기 성능을 위해서

맞습니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.
여기 아래부터는 솔직히 아직 잘 모르겠습니다.. 강의들 들으며 조금만 더 생각해보겠습니다.

[min-guk]

2022.7.18 오후 9:10:51

1. Why do LSM-tree and LevelDB use leveled structure?
   레벨 디비에서 레벨이 나눠져있는 이유는 읽기와 쓰기 효울의 문제 때문이다. 메모리 측면에서 본다면 충분이 큰 용량의 디스크를 통해 한층의 레벨로 구상을 한다면 낮은 레벨에서 키값이 겹치는 현상이 자주 발생한다. 이후 flush 처리와 merge sort 하는 상황이 자주 발생하게 된다. 그렇게 된다면 메모리의 효율 측면에서 데이터의 크기가 커지면 커질수록 성능이 떨어지는 현상이 발생한다.
   compaction이 될때 만약 레벨이 나눠지는 구조가 아닌 구조라면 merge sort 하는 비용과 처리 비용이 너무 많이 필요하다.(leveldb 디자인 압축의 목적 중 하나는 읽기의 효율성을 높이는 것입니다 .)

맞습니다.

자주 사용되는 키값들은 데이터들이 겹치는 현상이 발생한다. 그렇게 된다면 낮은 레벨에 있는 데이터들은 오버랩이 자주 발생하므로 낮은 레벨에 자주 사용하는 키값을이 모이게 된다. 그렇게 된다면 자연스럽게 높은 레벨에 있는 값을든 값들이 채워지면서 compaction과 merge sort를 통해 자주 사용하지 않는 값들이 몰리게 되면서 자연스럽게 캐시 구조와 같이 메모리간의 계층(hierarchy) 가 생기게 된다. 그렇게 된다면 쓰기와 읽기의 효율과 성능의 향상을 기대할 수 있다.

캐시는 조금 다른 이야긴 것 같네요. 제가 학생들에게 혼란스러울 수 있는 힌트를 줬던 것 같네요.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?
   데이터의 키값들의 범위가 겹치는 상황이 아니라면 문제가 발생하지는 않지만 만약 데이터들이 항상 범위가 겹치는 상황이 발생한다면 문제가 발생한다.
   이렇게 된다면 만약 항상 겹치는 값들을 처리할때 compaction 과정에서 파일을 읽을때 모든 데이터를 순회하면 검색해야하는 최악의 경우가 발생한다.
   그래서 이런것을 줄이기 위해 쓰기 효율성을 높이기 위해서 level 0 의 크기를 늘려서 merge sort를 통해서 compaction이 이뤄진다면 최악의 경우를 피할수 있다.

맞습니다. 읽기 효율을 높이기 위해 8MB로 작게 설정한 것 입니다.

[min-guk]

2022.7.18 오후 10:54:28

1. Why do LSM-tree and LevelDB use leveled structure?
   머지를 쉽고 빠르게 할 수 있기 때문이다. 성능을 향상시킬 수 있기 때문이다.

맞습니다. WAF를 위해 멀티 레벨을 구성합니다.

2. In leveldb, max size of level i is 10^iMB. But max size of level 0 is 8MB. Why?
   2MB*4, 매 읽기마다 머지해야 하는데 너무 많은 작은 파일을 피해야 하기 때문에..?

RAF를 줄이기 위해서면서도, WAF를 너무 키우지 않기 위함입니다.

3-1. Compare throughput, latency, and stats of two benchmarks and explain why.

fillseq(9.093micros/op, 12.2MB/s, 레벨2,3)
fillrandom(16.780micros/op, 6.6MB/s, 레벨0,1,2)

3-2. In benchmark A, SSTs are not written in L0. Why?
l0에 있던 데이터들이 플러시 되고 컴팩션 될 때 모두 l2에 들어갈 수 있었기 때문에..?

trivial move로 인한 것 입니다.

3-2. Calculate SAF (Space Amplification Factor) for each benchmark.
fillseq: 16/35, fillrandom: 16/42

PPT를 참고하시길 바랍니다.

4-1. Which user key-value interface does each benchmark use?
A,B:Get , C:Iterator

A 또한 Iterator입니다.

4-2. Compare throughput and latency of each benchmark and explain why.
A(0.969 micros/op)>B(6.374 micros/op)>C(7.320 micros/op)

Q. The size of input kv pairs is the same. But One is better in throughput, the other is better in latency. Explain why.
값의 범위가 커서..? B가 throughput이 더 좋았다.

작게 여러번 쓰느냐, 크게 몇 번 안 쓰느냐의 차이입니다.

[min-guk]

모든 학생들의 피드백이 끝났습니다. 다들 열심히 과제를 제출해주셔서 감사합니다!