lsm_vs_btree.c

//bin/sh -c 'o=${0%.c}; [ "$o" -nt "$0" ] || ${CC:-clang} -O3 -march=native -o "$o" "$0"; exec "$o" "$@"' "$0" "$@"; exit
// source: http://smalldatum.blogspot.com/2016/01/summary-of-advantages-of-lsm-vs-b-tree.html
#define _GNU_SOURCE
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>

#define NOPS 100000
#define PAGE_SIZE 4096
#define VAL_SIZE 64
#define KEY_SIZE 16
#define ENTRY_SIZE (KEY_SIZE + VAL_SIZE)
#define NPAGES 16384
#define LSM_COMPACTION_FACTOR 3

static double now_sec(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec / 1e9;
}

static void bench_btree_insert(const char *path) {
    int fd = open(path, O_RDWR | O_CREAT | O_TRUNC | O_DSYNC, 0644);
    if (fd < 0) { perror("open btree"); return; }
    ftruncate(fd, (off_t)NPAGES * PAGE_SIZE);
    char page[PAGE_SIZE];
    memset(page, 0, PAGE_SIZE);
    uint64_t bytes_written = 0;
    double t0 = now_sec();
    for (int i = 0; i < NOPS; i++) {
        uint64_t page_idx = ((uint64_t)i * 2654435761u) % NPAGES;
        off_t offset = (off_t)page_idx * PAGE_SIZE;
        pread(fd, page, PAGE_SIZE, offset);
        memcpy(page, &i, sizeof(i));
        pwrite(fd, page, PAGE_SIZE, offset);
        bytes_written += PAGE_SIZE;
    }
    double t1 = now_sec();
    double elapsed = t1 - t0;
    printf("B-Tree: %d inserts in %.3f sec (%.1f Kops/sec)\n", NOPS, elapsed, NOPS/elapsed/1e3);
    printf("  bytes_written=%lu bytes/op=%.1f page_size=%d npages=%d\n",
           bytes_written, (double)bytes_written/NOPS, PAGE_SIZE, NPAGES);
    printf("  pattern=random read-modify-write per op\n");
    close(fd);
    unlink(path);
}

static void bench_lsm_insert(const char *path) {
    int fd = open(path, O_RDWR | O_CREAT | O_TRUNC | O_DSYNC, 0644);
    if (fd < 0) { perror("open lsm"); return; }
    int batch_size = PAGE_SIZE;
    char batch[PAGE_SIZE];
    memset(batch, 0, PAGE_SIZE);
    uint64_t bytes_written = 0;
    int pos = 0;
    double t0 = now_sec();
    for (int i = 0; i < NOPS; i++) {
        if (pos + ENTRY_SIZE > batch_size) {
            write(fd, batch, batch_size);
            bytes_written += batch_size;
            pos = 0;
        }
        memcpy(batch + pos, &i, sizeof(i));
        memset(batch + pos + KEY_SIZE, i & 0xff, VAL_SIZE);
        pos += ENTRY_SIZE;
    }
    if (pos > 0) { write(fd, batch, pos); bytes_written += pos; }
    double t1 = now_sec();
    double elapsed = t1 - t0;
    uint64_t total_with_compaction = bytes_written * LSM_COMPACTION_FACTOR;
    printf("LSM: %d inserts in %.3f sec (%.1f Kops/sec)\n", NOPS, elapsed, NOPS/elapsed/1e3);
    printf("  bytes_written=%lu bytes/op=%.1f entry_size=%d compaction=%dx batch_size=%d\n",
           total_with_compaction, (double)total_with_compaction/NOPS, ENTRY_SIZE, LSM_COMPACTION_FACTOR, batch_size);
    printf("  pattern=sequential batched append compaction_factor=%d\n", LSM_COMPACTION_FACTOR);
    close(fd);
    unlink(path);
}

static void bench_btree_secondary(const char *path) {
    int fd = open(path, O_RDWR | O_CREAT | O_TRUNC | O_DSYNC, 0644);
    if (fd < 0) { perror("open btree sec"); return; }
    ftruncate(fd, (off_t)NPAGES * PAGE_SIZE);
    char page[PAGE_SIZE];
    memset(page, 0, PAGE_SIZE);
    uint64_t reads = 0, writes = 0;
    double t0 = now_sec();
    for (int i = 0; i < NOPS; i++) {
        uint64_t page_idx = ((uint64_t)i * 2654435761u) % NPAGES;
        off_t offset = (off_t)page_idx * PAGE_SIZE;
        pread(fd, page, PAGE_SIZE, offset);
        reads++;
        memcpy(page, &i, sizeof(i));
        pwrite(fd, page, PAGE_SIZE, offset);
        writes++;
    }
    double t1 = now_sec();
    printf("B-Tree secondary index: %.3f sec reads=%lu writes=%lu total_io=%lu\n",
           t1-t0, reads, writes, reads+writes);
    close(fd);
    unlink(path);
}

static void bench_lsm_secondary(const char *path) {
    int fd = open(path, O_RDWR | O_CREAT | O_TRUNC | O_DSYNC, 0644);
    if (fd < 0) { perror("open lsm sec"); return; }
    char batch[PAGE_SIZE];
    memset(batch, 0, PAGE_SIZE);
    uint64_t reads = 0, writes = 0;
    int pos = 0;
    double t0 = now_sec();
    for (int i = 0; i < NOPS; i++) {
        if (pos + ENTRY_SIZE > PAGE_SIZE) {
            write(fd, batch, PAGE_SIZE);
            writes++;
            pos = 0;
        }
        memcpy(batch + pos, &i, sizeof(i));
        memset(batch + pos + KEY_SIZE, i & 0xff, VAL_SIZE);
        pos += ENTRY_SIZE;
    }
    if (pos > 0) { write(fd, batch, pos); writes++; }
    double t1 = now_sec();
    printf("LSM secondary index: %.3f sec reads=%lu writes=%lu total_io=%lu\n",
           t1-t0, reads, writes, reads+writes);
    close(fd);
    unlink(path);
}

int main(void) {
    const char *btree_path = "/tmp/lsm_btree_test.db";
    const char *lsm_path = "/tmp/lsm_log_test.db";

    printf("=== LSM vs B-Tree: real disk I/O ===\n");
    printf("source: http://smalldatum.blogspot.com/2016/01/summary-of-advantages-of-lsm-vs-b-tree.html\n");
    printf("ops=%d page_size=%d entry_size=%d\n\n", NOPS, PAGE_SIZE, ENTRY_SIZE);

    bench_btree_insert(btree_path);
    bench_lsm_insert(lsm_path);

    uint64_t btree_bytes = (uint64_t)PAGE_SIZE * NOPS;
    uint64_t lsm_bytes = (uint64_t)ENTRY_SIZE * NOPS * LSM_COMPACTION_FACTOR;
    printf("\nwrite amp: B-Tree/LSM = %.1fx\n", (double)btree_bytes / lsm_bytes);
    printf("  B-Tree bytes/op = %.1f page_size=%d\n", (double)btree_bytes/NOPS, PAGE_SIZE);
    printf("  LSM bytes/op = %.1f entry_size=%d compaction=%dx\n", (double)lsm_bytes/NOPS, ENTRY_SIZE, LSM_COMPACTION_FACTOR);

    printf("\nsecondary index maintenance:\n");
    bench_btree_secondary(btree_path);
    bench_lsm_secondary(lsm_path);

    printf("\nB-Tree reads_per_op=1 writes_per_op=1\n");
    printf("LSM reads_per_op=0 writes_per_op=1\n");

    return 0;
}
// OUTPUT:
// === LSM vs B-Tree: real disk I/O ===
// source: http://smalldatum.blogspot.com/2016/01/summary-of-advantages-of-lsm-vs-b-tree.html
// ops=100000 page_size=4096 entry_size=80
//
// B-Tree: 100000 inserts in 5.192 sec (19.3 Kops/sec)
//   bytes_written=409600000 bytes/op=4096.0 page_size=4096 npages=16384
//   pattern=random read-modify-write per op
// LSM: 100000 inserts in 0.341 sec (293.1 Kops/sec)
//   bytes_written=24094080 bytes/op=240.9 entry_size=80 compaction=3x batch_size=4096
//   pattern=sequential batched append compaction_factor=3
//
// write amp: B-Tree/LSM = 17.1x
//   B-Tree bytes/op = 4096.0 page_size=4096
//   LSM bytes/op = 240.0 entry_size=80 compaction=3x
//
// secondary index maintenance:
// B-Tree secondary index: 5.179 sec reads=100000 writes=100000 total_io=200000
// LSM secondary index: 0.324 sec reads=0 writes=1961 total_io=1961
//
// B-Tree reads_per_op=1 writes_per_op=1
// LSM reads_per_op=0 writes_per_op=1