mssttest.c

/*
 * Copyright (c) 2016--2021  Wu, Xingbo <wuxb45@gmail.com>
 *
 * All rights reserved. No warranty, explicit or implicit, provided.
 */
#define _GNU_SOURCE

#include "lib.h"
#include "kv.h"
#include "wh.h"
#include "sst.h"

u8 * levels1 = NULL;
u8 * levels2 = NULL;

  static void
set_value_tag(struct kv * const curr, void * const priv)
{
  *(u8 *)(kv_vptr(curr)) = *(u8 *)priv;
}

  static void
build_mssty(const char * const dirname, const u64 seq, const u32 vlen, const u32 nway, const u32 tgtpages, const u64 range, const bool tags)
{
  srandom_u64(1001);
  u32 totset = 0;
  u32 uniq = 0;
  u64 maxi = 0;
  for (u64 i = 0; i < range; i++) {
    levels1[i] = (u8)(random_u64() % (nway * 2));
    levels2[i] = (u8)(random_u64() % (nway * 2));
    if ((levels1[i] < nway) || (levels2[i] < nway)) {
      uniq++;
      maxi = i;
    }

    // some are huge
    kvss[i]->vlen = ((i % 10111) == 1234) ? 65000 : vlen;
  }
  const struct kvmap_api * const api = &kvmap_api_wormhole;
  struct wormhole * const map = wormhole_create(&kvmap_mm_ts);
  debug_assert(map);

  // build all ssts
  for (u32 way = 0; way < nway; way++) {
    char tag = '0' + (char)way;
    // prep keys
    void * const ref = kvmap_ref(api, map);
    u32 nset = 0;
    for (u64 i = 0; i < range; i++) {
      if ((levels1[i] == way) || (levels2[i] == way)) {
        kvmap_kv_put(api, ref, kvss[i]);
        kvmap_kv_inpw(api, ref, kvss[i], set_value_tag, &tag);
        nset++;
      }
    }
    totset += nset;
    kvmap_unref(api, ref);
    struct miter * const miter = miter_create();
    debug_assert(miter);
    miter_add(miter, api, map);
    miter_seek(miter, kref_null());
    // gen sst
    const u64 tx0 = time_nsec();
    sst_build(dirname, miter, seq, way, 65500, tgtpages, false, (way & 1) == 0, NULL, NULL);
    const u64 dtx0 = time_diff_nsec(tx0);
    u64 omit = 0;
    while (miter_valid(miter)) {
      miter_skip1(miter);
      omit++;
    }
    printf("build-x dt %lu used %lu omitted %lu\n", dtx0, nset - omit, omit);
    miter_destroy(miter);
    api->clean(map);
  }
  api->destroy(map);

  struct msst * const msst = msstx_open(dirname, seq, nway);
  debug_assert(msst);
  // build ssty
  const u64 ty0 = time_nsec();
  ssty_build(dirname, msst, seq, nway, NULL, 0, tags);
  const u64 dty0 = time_diff_nsec(ty0);

  msstx_destroy(msst);
  printf("build-y dt %lu seq %lu nway %u uniq %u totset %u dup %u maxi %lu nr %lu\n",
      dty0, seq, nway, uniq, totset, totset - uniq, maxi, range);
}

  static void
do_range_search(const u64 range, const struct kvmap_api * const api,
    void * const map, const u32 nskip, const u32 nnext)
{
  void * const ref = kvmap_ref(api, map);
  void * const iter = api->iter_create(ref);
  struct kv * const tmp = malloc(1 << 20);
  const u64 rrange = range < 100000 ? range : 100000;
  debug_perf_switch();
  shuffle_u64((u64 *)kvss, range);
  const u64 t0 = time_nsec();
  for (u64 i = 0; i < rrange; i++) {
    cpu_prefetch0(kvss[i+1]);
    cpu_prefetch0(((const u8 *)kvss[i+1])+64);
    kvmap_kv_iter_seek(api, iter, kvss[i]);
    if (nnext) { // nnext > 0: do next
      for (u32 j = 0; j < nnext; j++)
        api->iter_next(iter, tmp);
    } else { // nnext == 0: do skip and peek
      api->iter_skip(iter, nskip);
      api->iter_peek(iter, tmp);
    }
  }
  const u64 dt = time_diff_nsec(t0);
  const double mops = ((double)rrange) * 1e3 / ((double)dt);
  if (nnext)
    printf("random seek-next%u mops %.3lf\n", nnext, mops);
  else
    printf("random seek-skip%u-peek mops %.3lf\n", nskip, mops);
  free(tmp);
  api->iter_destroy(iter);
  kvmap_unref(api, ref);
}

  static void
test_seek_all(char * const dirname, char * const apitype,
    const u64 seq, const u32 nway, const u64 range)
{
  printf("%s %s %lu %u %lu\n", __func__, apitype, seq, nway, range);
  char buf1[10];
  char buf2[10];
  sprintf(buf1, "%lu", seq);
  sprintf(buf2, "%u", nway);
  char * argv[5] = {"api", apitype, dirname, buf1, buf2};
  const struct kvmap_api * api = NULL;
  void * map = NULL;
  // mm is ignored by msstx/mssty
  kvmap_api_helper(5, argv, NULL, &api, &map);
  debug_assert(api);
  debug_assert(map);

  srandom_u64(1023);
  u64 t0, dt;
  u64 err = 0;
  double mops;
  struct kv * const tmp = malloc(1 << 20);
  struct kv * const tmp0 = malloc(1 << 20);
  void * const ref = kvmap_ref(api, map);
  kv_qsort(kvss, kvnr);

  // get/probe
  debug_perf_switch();
  err = 0;
  for (u64 i = 0; i < range; i++) {
    if ((levels1[i] < nway) || (levels2[i] < nway)) {
      struct kv * const ret = kvmap_kv_get(api, ref, kvss[i], tmp);
      if (!ret)
        err++;
      if (kv_compare(kvss[i], tmp) != 0)
        err++;
      if (!kvmap_kv_probe(api, ref, kvss[i]))
        err++;
    } else { // nonexist
      if (kvmap_kv_probe(api, ref, kvss[i]))
        err++;
    }
  }
  printf("get/probe err %lu/%lu\n", err, range);

  // test dup
  debug_perf_switch();
  err = 0;
  u64 ndup = 0;
  for (u64 i = 0; i < range; i++) {
    if ((levels1[i] < nway) && (levels2[i] < nway)) {
      ndup++;
      struct kv * const ret = kvmap_kv_get(api, ref, kvss[i], tmp);
      if (ret) {
        const u8 l = levels1[i] > levels2[i] ? levels1[i] : levels2[i];
        if (ret->kv[ret->klen] != ('0' + l)) {
          kv_print(ret, "s", stdout);
          printf("%c\n", ret->kv[ret->klen]);
          err++;
        }
      }
    }
  }
  printf("get dup err %lu/%lu\n", err, ndup);

  void * const iter = api->iter_create(ref);
  // seek only
  debug_perf_switch();
  err = 0;
  for (u64 i = 0; i < range; i++) {
    kvmap_kv_iter_seek(api, iter, kvss[i]);
    struct kv * const ret = api->iter_peek(iter, tmp);
    if (!ret)
      err++;
    if (((levels1[i] < nway) || (levels2[i] < nway)) && (kv_compare(kvss[i], tmp) != 0))
      err++;
  }
  printf("seek err %lu/%lu\n", err, range);

  // skip only
  debug_perf_switch();
  err = 0;
  ndup = 0;
  kv_refill(tmp0, "", 0, "", 0);
  kvmap_kv_iter_seek(api, iter, tmp0);
  for (u64 i = 0; i < range; i++) {
    struct kv * const ret = api->iter_peek(iter, tmp);
    if (ret == NULL) {
      printf("skip stopped at %lu\n", i);
      break;
    }
    const int cmp = kv_compare(tmp0, tmp);
    if (cmp > 0)
      err++;
    else if (cmp == 0)
      ndup++;
    api->iter_skip1(iter);
    kv_dup2_key(tmp, tmp0);
  }
  printf("skip-all ndup %lu err %lu/%lu\n", ndup, err, range);

  // random seek-skip
  debug_perf_switch();
  err = 0;
  for (u64 i = 0; i < 10000; i++) {
    const u64 idx = random_u64() % range;
    kvmap_kv_iter_seek(api, iter, kvss[idx]);
    if (api->iter_peek(iter, tmp) == NULL) {
      printf("seek %lu/%lu failed (should be near the end)\n", idx, range);
      continue;
    }
    if (kv_compare(kvss[idx], tmp) > 0)
      err++;
    for (u64 j = 1; j <= 20; j++) {
      api->iter_skip1(iter);
      if (!api->iter_valid(iter))
        break;
      kv_dup2_key(tmp, tmp0);
      api->iter_peek(iter, tmp);
      if (kv_compare(tmp0, tmp) > 0)
        err++;
    }
  }
  printf("seek-skip-20 err %lu/%lu\n", err, 10000lu);

  //// throughput

  // random get
  const u64 rrange = range < 100000 ? range : 100000;
  debug_perf_switch();
  shuffle_u64((u64 *)kvss, range);
  t0 = time_nsec();
  for (u64 i = 0; i < rrange; i++) {
    cpu_prefetch0(kvss[i+1]);
    cpu_prefetch0(((const u8 *)kvss[i+1])+64);
    kvmap_kv_get(api, ref, kvss[i], tmp);
  }
  dt = time_diff_nsec(t0);
  mops = ((double)rrange) * 1e3 / ((double)dt);
  printf("random get %.3lf\n", mops);

  // random probe
  debug_perf_switch();
  shuffle_u64((u64 *)kvss, range);
  t0 = time_nsec();
  for (u64 i = 0; i < rrange; i++) {
    cpu_prefetch0(kvss[i+1]);
    cpu_prefetch0(((const u8 *)kvss[i+1])+64);
    kvmap_kv_probe(api, ref, kvss[i]);
  }
  dt = time_diff_nsec(t0);
  mops = ((double)rrange) * 1e3 / ((double)dt);
  printf("random probe mops %.3lf\n", mops);

  // random seek
  debug_perf_switch();
  shuffle_u64((u64 *)kvss, range);
  t0 = time_nsec();
  for (u64 i = 0; i < rrange; i++) {
    cpu_prefetch0(kvss[i+1]);
    cpu_prefetch0(((const u8 *)kvss[i+1])+64);
    kvmap_kv_iter_seek(api, iter, kvss[i]);
  }
  dt = time_diff_nsec(t0);
  mops = ((double)rrange) * 1e3 / ((double)dt);
  printf("random seek mops %.3lf\n", mops);

  // skip-peek
  do_range_search(range, api, map, 0, 0);
  do_range_search(range, api, map, 10, 0);
  do_range_search(range, api, map, 50, 0);
  // next
  do_range_search(range, api, map, 0, 10);
  do_range_search(range, api, map, 0, 50);

  // clean up
  free(tmp);
  free(tmp0);
  debug_perf_switch();
  api->iter_destroy(iter);
  kvmap_unref(api, ref);
  api->destroy(map);
}

  static void
test_check_seek_near(struct msst * const map, struct mssty_iter * const iter, const u32 nway)
{
  mssty_iter_seek(iter, kref_null());
  struct kv * const tmp = malloc(1 << 17);
  u64 x = 0;
  u64 lt = 0;
  u64 eq = 0;
  u64 gt = 0;
  while (x < kvnr) {
    const bool hit = (levels1[x] < nway) || (levels2[x] < nway);
    const struct kref kref = kv_kref(kvss[x]);
    mssty_iter_seek_near(iter, &kref, random_u64() & 1);
    if (mssty_iter_valid(iter)) {
      struct kv * const ret = mssty_iter_peek(iter, tmp);
      const int cmp = kv_compare(kvss[x], ret);
      if (cmp < 0) {
        if (hit) {
          printf("should hit at %lu but seek to > key (this can be false alarm with omitted keys)\n", x);
          kv_print(ret, "sn", stdout);
          kv_print(kvss[x], "sn", stdout);
          break;
        }
        lt++;
      } else if (cmp == 0) {
        if (!hit) {
          printf("BUG! should mismatch at %lu but seek to == key\n", x);
          kv_print(ret, "sn", stdout);
          kv_print(kvss[x], "sn", stdout);
          break;
        }
        eq++;
      } else {
        gt++;
      }
    } else {
      printf("seek_near: iter became invalid at %lu/%lu\n", x, kvnr);
      kv_print(kvss[x], "sn", stdout);
      break;
    }
    x += (random_u64() & 0x3f);
  }
  printf("check_seek_near done: %lu %lu %lu==0 last:\n", lt, eq, gt);
  struct kv * const last = mssty_last(map, tmp);
  kv_print(last, "sn", stdout);
  free(tmp);
}

  static void
test_check_mssty(char * const dirname, const u64 seq, const u32 nway)
{
  printf("%s %s %lu %u\n", __func__, dirname, seq, nway);
  const u64 magic = seq * 100lu + nway;
  struct kv * const tmp = malloc(1 << 17);
  tmp->hash = 0;

  const struct kvmap_api * const api = &kvmap_api_mssty;
  struct msst * const map = mssty_open(dirname, magic/100lu, (u32)(magic%100lu));
  debug_assert(map);

  void * const ref = kvmap_ref(api, map);
  struct mssty_iter * const iter = api->iter_create(ref);
  u64 count = 0;
  kvmap_kv_iter_seek(api, iter, kv_null());
  do {
    struct kv * const ret = api->iter_next(iter, tmp);
    if (ret == NULL)
      break;
    count++;
  } while (api->iter_valid(iter));

  if (count) {
    kv_print(tmp, "xn", stdout);
    struct kv * const last = mssty_last(map, tmp);
    kv_print(last, "xn", stdout);
    printf("check mssty %lu: count %lu\n", magic, count);

    // seek near
    test_check_seek_near(map, iter, nway);
  } else {
    printf("check mssty %lu: empty\n", magic);
  }

  api->iter_destroy(iter);
  kvmap_unref(api, ref);
  api->destroy(map);
  free(tmp);
}

  int
main(int argc, char ** argv)
{
  if (argc < 4) {
    printf("Usage: <keyfile> <vlen> <target-pages-per-block>\n");
    exit(0);
  }

  if (kv_load(argv[1]) == false)
    return 0;
  kv_qsort(kvss, kvnr);

  const u32 vlen = a2u32(argv[2]);
  const u32 vlen1 = vlen < sizeof(u8) ? sizeof(u8) : vlen;
  levels1 = malloc(kvnr);
  levels2 = malloc(kvnr);
  char dirname[50];
  sprintf(dirname, "/tmp/msst-%s", getlogin());
  mkdir(dirname, 00777);
  const u32 tgtpages = a2u32(argv[3]);

  // really nothing
  build_mssty(dirname, 3, vlen1, 0, tgtpages, 0, false);
  test_check_mssty(dirname, 3, 0);
  build_mssty(dirname, 5, vlen1, 0, tgtpages, 0, true);
  test_check_mssty(dirname, 5, 0);

  const u32 maxnway = 16;
  // empty sstx/ssty
  build_mssty(dirname, 6, vlen1, maxnway, tgtpages, 0, false);
  test_check_mssty(dirname, 6, maxnway);
  build_mssty(dirname, 7, vlen1, maxnway, tgtpages, 0, true);
  test_check_mssty(dirname, 7, maxnway);

  // 1,2,4,8,16
  for (u32 nway = 1; nway <= maxnway; nway <<= 1) {
    // randomly insert about 50% of the keys into X ssts, and build a ssty
    build_mssty(dirname, nway, vlen1, nway, tgtpages, kvnr, false);
    test_check_mssty(dirname, nway, nway);
    build_mssty(dirname, maxnway + nway, vlen1, nway, tgtpages, kvnr, true);
    test_check_mssty(dirname, maxnway + nway, nway);
  }

  // check that the data are there (about 50% hit)
  // very slow
  const u64 maxseq = maxnway;
  //test_seek_all(dirname, "msstx", maxseq, maxnway, kvnr);
  test_seek_all(dirname, "mssty", maxseq, maxnway, kvnr);
  test_seek_all(dirname, "mssty_dup", maxseq, maxnway, kvnr);
  test_seek_all(dirname, "mssty", maxseq * 2, maxnway, kvnr);
  test_seek_all(dirname, "mssty_dup", maxseq * 2, maxnway, kvnr);
  kvloader_destroy();
  free(levels1);
  free(levels2);
  return 0;
}