<?php
/**
* SeekQuarry/Yioop --
* Open Source Pure PHP Search Engine, Crawler, and Indexer
*
* Copyright (C) 2009 - 2026 Chris Pollett chris@pollett.org
*
* LICENSE:
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*
* END LICENSE
*
* This file contains unit tests of the LSMTree class used to keep track of
*
* @author Chris Pollett chris@pollett.org
* @license https://www.gnu.org/licenses/ GPL3
* @link https://www.seekquarry.com/
* @copyright 2009 - 2026
* @filesource
*/
namespace seekquarry\yioop\tests;
use seekquarry\yioop\configs as C;
use seekquarry\yioop\library as L;
use seekquarry\yioop\models\Model;
use seekquarry\yioop\library\data_structures\LSMTree;
use seekquarry\yioop\library\data_structures\PackedTableTools;
use seekquarry\yioop\library\data_structures\UndoLog;
use seekquarry\yioop\library\UnitTest;
/**
* Yioop LSMTree Unit Class
*
* Used to test insert, lookup, and deletion of key-value pairs in a
* Log-structured Merge Tree.
* @author Chris Pollett
*/
class LSMTreeTest extends UnitTest
{
/**
* Test directory to hold LSMTree used for these unit tests
*/
const TEST_DIR = '/test_files/lsm_tree_test';
/**
* Folder names to use for test LSMTree
* @var array
*/
public $table_dirs;
/**
* Minimum degree is set to 2 and the number of key-value pairs is set to 25
*/
public function setUp()
{
$this->table_dirs = [];
}
/**
* Delete the LSMTree files created during the test
*/
public function tearDown()
{
$model = new Model();
foreach ($this->table_dirs as $table_dir) {
$model->db->unlinkRecursive($table_dir, true);
}
$this->table_dirs = [];
}
/**
* Creates a single LSM tree under a per-parameter directory
* derived from key size, file size, block factor, and suffix.
* Each call tracks the directory so tearDown can clean it up.
*
* @param array $format column definitions for the tree
* @param int $max_file_size maximum on-disk size of any single
* file in the tree
* @param int $block_factor number of records per disk block
* @param string $suffix optional suffix appended to the test
* directory name to disambiguate concurrent test trees
* @return LSMTree freshly-constructed tree backed by the
* per-test directory
*/
public function createTree($format, $max_file_size, $block_factor,
$suffix = "")
{
$key_size = $format["PRIMARY KEY"][1];
$table_dir = __DIR__ . self::TEST_DIR .
"_{$key_size}_{$max_file_size}_{$block_factor}_$suffix";
$this->table_dirs[] = $table_dir;
return new LSMTree($table_dir, $format, $max_file_size,
$block_factor);
}
/**
* NUM_SIMPLE_ENTRIES is how many entries simplePutGetTierTestCase puts
* into each tree. Each entry is longer than either file size the case
* tries, so every tree spreads its entries over many files.
*/
const NUM_SIMPLE_ENTRIES = 12;
/**
* SIMPLE_TREE_SETTINGS lists the trees simplePutGetTierTestCase
* makes, each a file size in bytes, a block factor, a key length and
* a number of extra columns. Each value of each setting appears in at
* least one tree, rather than every combination of them.
*/
const SIMPLE_TREE_SETTINGS = [[20, 1, 16, 0], [50, 2, 8, 1],
[20, 2, 8, 2], [50, 1, 16, 2]];
/**
* simplePutGetTierTestCase puts NUM_SIMPLE_ENTRIES entries into each
* tree SIMPLE_TREE_SETTINGS lists, flushes the tree into one tier,
* and checks that every entry can be read back.
*/
public function simplePutGetTierTestCase()
{
foreach (self::SIMPLE_TREE_SETTINGS as
[$max_file_size, $block_factor, $key_len, $cols]) {
$format = ["PRIMARY KEY" => ["KEY", $key_len],
"VALUE" => "TEXT"];
for ($j = 0; $j < $cols; $j++) {
$format["COL$j"] = "INT";
}
$lsm_tree = $this->createTree($format, $max_file_size,
$block_factor, "{$key_len}_$cols");
for ($i = 0; $i < self::NUM_SIMPLE_ENTRIES; $i++) {
$key = str_pad("key$i", $key_len, "0", STR_PAD_LEFT);
$entry = ["KEY" => $key, "VALUE" => "value$i"];
for ($j = 0; $j < $cols; $j++) {
$entry["COL$j"] = $i;
}
$lsm_tree->put($entry);
}
$lsm_tree->flush();
for ($i = 0; $i < self::NUM_SIMPLE_ENTRIES; $i++) {
$key = str_pad("key$i", $key_len, "0", STR_PAD_LEFT);
$values = $lsm_tree->get($key);
$this->assertEqual("value$i", $values[0]["VALUE"],
"{$i}th insert key length $key_len, $cols extra " .
"columns, into a single tier is read back");
}
}
}
/**
* Checks that the correct number of block folders are created when
* inserting several items into am LSMTree with a small block factor
* and max file size
*/
public function blockFactorTestCase()
{
$max_file_size = 20;
$block_factor = 2;
$key_len = 16;
$cols = 2;
$format = ["PRIMARY KEY" => ["KEY", $key_len],
"VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, $max_file_size,
$block_factor, "{$key_len}");
for ($i = 0; $i < 15; $i++) {
$key = str_pad("key$i", $key_len, "0",
STR_PAD_LEFT);
$entry = ["KEY" => $key, "VALUE" => "value$i"];
$lsm_tree->put($entry);
}
$this->assertTrue(file_exists($lsm_tree->folder .
"/Tier0000/A/F00000000000key12") && !file_exists($lsm_tree->folder .
"/Tier0000/A/F00000000000key14"),
"Correct number of block folders created");
}
/**
* Checks that the correct number of data files are created when
* inserting several items into am LSMTree with a small max file size
*/
public function maxFileSizeTestCase()
{
$max_file_size = 50;
$block_factor = 10000;
$key_len = 16;
$cols = 2;
$format = ["PRIMARY KEY" => ["KEY", $key_len],
"VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, $max_file_size,
$block_factor, "{$key_len}");
for ($i = 0; $i < 15; $i++) {
$key = str_pad("key$i", $key_len, "0",
STR_PAD_LEFT);
$entry = ["KEY" => $key, "VALUE" => "value$i"];
$lsm_tree->put($entry);
}
$block_folder = $lsm_tree->folder . "/Tier0000/A/F000000000000key0";
$this->assertTrue(file_exists("$block_folder/D00000000000key13") &&
!file_exists("$block_folder/D00000000000key14"),
"Correct number of data files created");
}
/**
* Tests that values for identical keys are correctly merged when merge
* two slots within a tier.
*/
public function mergeRecordsTierTestCase()
{
$max_file_size = 50;
$block_factor = 2;
$key_len = 16;
$cols = 2;
$format = ["PRIMARY KEY" => ["KEY", $key_len],
"VALUE" => "TEXT"];
for ($j = 0; $j < $cols; $j++) {
$format["COL$j"] = "INT";
}
$lsm_tree = $this->createTree($format, $max_file_size,
$block_factor, "{$key_len}_$cols");
foreach ([["A", 0, 10], ["B", 5, 15]] as $slot_info) {
$lsm_tree->selectPutSlot($slot_info[0]);
for ($i = $slot_info[1]; $i < $slot_info[2]; $i++) {
$key = str_pad("key$i", $key_len, "0",
STR_PAD_LEFT);
$entry = ["KEY" => $key, "VALUE" => "value{$slot_info[0]}$i"];
for ($j = 0; $j < $cols; $j++) {
$entry["COL$j"] = $i;
}
$lsm_tree->put($entry);
}
$lsm_tree->flush();
}
$lsm_tree->mergeTiers();
$key = str_pad("key10", $key_len, "0", STR_PAD_LEFT);
$values = $lsm_tree->get($key);
for ($i = 0; $i < 15; $i++) {
$key = str_pad("key$i", $key_len, "0", STR_PAD_LEFT);
$values = $lsm_tree->get($key);
if ($i < 10) {
$this->assertEqual("valueA$i", $values[0]["VALUE"],
"Able to retrieve Slot A value $i");
}
if ($i > 4 && $i < 10) {
$this->assertEqual("valueB$i", $values[1]["VALUE"],
"Able to retrieve Slot B value $i");
}
if ($i >= 10) {
$this->assertEqual("valueB$i", $values[0]["VALUE"],
"Able to retrieve Slot B value $i");
}
}
}
/**
* NUM_MERGE_ENTRIES is how many entries mergeTiersTestCase puts into
* its tree, ten for each merge.
*/
const NUM_MERGE_ENTRIES = 30;
/**
* mergeTiersTestCase checks that tiers are made and merged correctly
* when NUM_MERGE_ENTRIES entries go into a tree with a small block
* factor and file size, merging after every ten. The tiers left
* holding data follow the number of merges in binary, and each value
* can be read back with its key.
*/
public function mergeTiersTestCase()
{
$max_file_size = 50;
$block_factor = 2;
$key_len = 16;
$cols = 3;
$format = ["PRIMARY KEY" => ["KEY", $key_len],
"VALUE" => "TEXT"];
for ($j = 0; $j < $cols; $j++) {
$format["COL$j"] = "INT";
}
$lsm_tree = $this->createTree($format, $max_file_size,
$block_factor, "{$key_len}_$cols");
$slot = "B";
for ($i = 0; $i < self::NUM_MERGE_ENTRIES; $i++) {
if ($i % 5 == 0) {
$slot = ($slot == "B") ? "A" : "B";
$lsm_tree->flush();
$lsm_tree->selectPutSlot($slot);
}
if ($i > 0 && $i % 10 == 0) {
$lsm_tree->mergeTiers();
}
$k = 10 * floor($i / 10);
$k += ($slot == "A") ? 2 * ($i % 10) : 2 * (($i % 10) - 5) + 1;
$key = str_pad("key$k", $key_len, "0", STR_PAD_LEFT);
$entry = ["KEY" => $key, "VALUE" => "value$k"];
for ($j = 0; $j < $cols; $j++) {
$entry["COL$j"] = $k;
}
$lsm_tree->put($entry);
}
$lsm_tree->flush();
$lsm_tree->mergeTiers();
/* Each merge after ten entries adds one more tier-0 group, and
merging carries like adding one in binary, so tier t holds data
when bit t - 1 of the number of groups is set. */
$groups = intdiv(self::NUM_MERGE_ENTRIES, 10);
$this->assertEqual($lsm_tree->getMaxTier(),
strlen(decbin($groups)), "Final maxTiers is correct");
for ($i = 0; $i <= strlen(decbin($groups)); $i++) {
$occupied = ($i > 0) && (($groups >> ($i - 1)) & 1) == 1;
$this->assertEqual($lsm_tree->occupiedTier($i), $occupied,
"{$i} th tier correctly occupied");
}
for ($i = 0; $i < self::NUM_MERGE_ENTRIES; $i++) {
$key = str_pad("key$i", $key_len, "0", STR_PAD_LEFT);
$values = $lsm_tree->get($key);
$this->assertEqual("value$i", $values[0]["VALUE"],
"Able to retrieve {$i}th value");
}
}
/**
* mergedTierIsNotCheckpointedTestCase checks that a tier merge leaves
* no checkpoint of the tier files in the tree's folder, and that a
* checkpoint an earlier version left is dropped when the tree is
* opened for writing. The checkpoint listed every tier file, and each
* open read the size of every one, which took up to 28 seconds on a
* large crawl's dictionary.
*/
public function mergedTierIsNotCheckpointedTestCase()
{
$format = ["PRIMARY KEY" => ["KEY", 16], "VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, 50, 2, "checkpoint");
foreach (["A", "B"] as $slot) {
$lsm_tree->selectPutSlot($slot);
for ($i = 0; $i < 6; $i++) {
$key = str_pad("key$slot$i", 16, "0", STR_PAD_LEFT);
$lsm_tree->put(["KEY" => $key, "VALUE" => "$slot$i"]);
}
$lsm_tree->flush();
}
$lsm_tree->mergeTiers();
$checkpoint = $lsm_tree->folder . "/" . UndoLog::CHECKPOINT_NAME;
$this->assertFalse(file_exists($checkpoint),
"a merge records no checkpoint of the tier files");
file_put_contents($checkpoint, $lsm_tree->folder . "/gone\t5\n");
$reopened = new LSMTree($lsm_tree->folder, $format, 50, 2);
$this->assertFalse(file_exists($checkpoint),
"an open for writing drops an old checkpoint");
$key = str_pad("keyB3", 16, "0", STR_PAD_LEFT);
$this->assertEqual($reopened->get($key)[0]["VALUE"] ?? "", "B3",
"the merged rows read back");
}
/**
* mergedTierIsDeletedLaterTestCase checks that mergeTier moves the
* merged tier aside rather than deleting it while the merge waits,
* that lookups still find every row, and that removeAsideTiers then
* deletes the moved folder, a call with no time left deleting only
* part of it.
*/
public function mergedTierIsDeletedLaterTestCase()
{
$format = ["PRIMARY KEY" => ["KEY", 16], "VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, 50, 2, "aside");
foreach (["A", "B"] as $slot) {
$lsm_tree->selectPutSlot($slot);
for ($i = 0; $i < 20; $i++) {
$key = str_pad("key$slot$i", 16, "0", STR_PAD_LEFT);
$lsm_tree->put(["KEY" => $key, "VALUE" => "$slot$i"]);
}
$lsm_tree->flush();
}
$lsm_tree->mergeTier(0);
$aside = glob($lsm_tree->folder . "/" . LSMTree::REMOVING_PREFIX .
"*", GLOB_ONLYDIR);
$this->assertEqual(count($aside), 1,
"the merged tier waits aside after the merge");
$key = str_pad("keyA7", 16, "0", STR_PAD_LEFT);
$this->assertEqual($lsm_tree->get($key)[0]["VALUE"] ?? "", "A7",
"a lookup finds a row of the merged tier");
$this->assertTrue($lsm_tree->removeAsideTiers(0),
"a call with no time left leaves some of it");
$this->assertTrue(file_exists($aside[0]),
"the folder is still there after that call");
$this->assertFalse($lsm_tree->removeAsideTiers(60),
"a call with time to spare deletes the rest");
$this->assertFalse(file_exists($aside[0]),
"the moved folder is gone");
}
/**
* mergeKeepsKeysWithEncodedBytesTestCase checks a tier merge of keys
* holding the bytes 254 and 255, which tier files store encoded.
* mergeTier copies a row as stored and decodes only its key, so the
* case checks every key is found after the merge with its value, and
* a key both tiers hold with both its rows.
*/
public function mergeKeepsKeysWithEncodedBytesTestCase()
{
$format = ["PRIMARY KEY" => ["KEY", 16], "VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, 200, 4, "encoded");
$keys = [];
for ($i = 0; $i < 40; $i++) {
$keys[] = str_pad(chr(250 + $i % 6) . "\xFF\xFE" . chr($i),
16, ($i % 2) ? "\xFF" : "\xFE");
}
sort($keys, SORT_STRING);
foreach (["A" => [0, 25], "B" => [15, 40]] as $slot => $span) {
$lsm_tree->selectPutSlot($slot);
for ($i = $span[0]; $i < $span[1]; $i++) {
$lsm_tree->put(["KEY" => $keys[$i], "VALUE" => "$slot$i"]);
}
$lsm_tree->flush();
}
$lsm_tree->mergeTier(0);
$found = 0;
$both = 0;
foreach ($keys as $i => $key) {
$values = array_column($lsm_tree->get($key), "VALUE");
$found += (in_array("A$i", $values) || in_array("B$i", $values))
? 1 : 0;
$both += (in_array("A$i", $values) && in_array("B$i", $values))
? 1 : 0;
}
$this->assertEqual($found, 40, "every key is found after the merge");
$this->assertEqual($both, 10,
"the ten keys both tiers held keep both rows");
}
/**
* spreadMergeTakesTierZeroAndOneMoreTestCase fills both slots of tiers
* 0 and 3 and one slot of tier 1. mergeTiersSpread merges tier 0 into
* tier 1, then the lowest full tier, tier 1, into tier 2, and leaves
* full tier 3 for a later call, where mergeTiers would merge it too.
* Every row is still found.
*/
public function spreadMergeTakesTierZeroAndOneMoreTestCase()
{
$format = ["PRIMARY KEY" => ["KEY", 16], "VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, 50, 2, "spread");
$slots = [3 => ["A", "B"], 1 => ["A"], 0 => ["A", "B"]];
$keys = [];
foreach ($slots as $tier => $tier_slots) {
$folder = $lsm_tree->getTierFolder($tier);
foreach ($tier_slots as $slot) {
$lsm_tree->selectPutSlot($slot);
for ($i = 0; $i < 3; $i++) {
$key = str_pad("key$tier$slot$i", 16, "0",
STR_PAD_LEFT);
$lsm_tree->put(["KEY" => $key, "VALUE" => $key]);
$keys[] = $key;
}
$lsm_tree->flush();
if ($tier > 0) {
@mkdir($folder, 0777, true);
rename($lsm_tree->getTierFolder(0) . "/$slot",
"$folder/$slot");
}
}
}
$lsm_tree->getMaxTier(true);
$lsm_tree->mergeTiersSpread();
$this->assertFalse($lsm_tree->tierIsFull(0), "tier 0 is merged");
$this->assertFalse($lsm_tree->tierIsFull(1),
"tier 1, full after taking tier 0, is merged");
$this->assertTrue($lsm_tree->tierIsFull(3),
"full tier 3 waits for a later call");
$found = 0;
foreach ($keys as $key) {
$found += empty($lsm_tree->get($key)) ? 0 : 1;
}
$this->assertEqual($found, count($keys), "every row is found");
}
/**
* walkCrossedByMergeIsDoneAgainTestCase checks that a lookup whose
* walk of the tiers a merge's renames fell inside walks again. The
* first walk here sees the merge count rise by two, as a whole merge
* makes it, and gets a key's row twice, as a walk between the renames
* can; the lookup gives the row once.
*/
public function walkCrossedByMergeIsDoneAgainTestCase()
{
$format = ["PRIMARY KEY" => ["KEY", 16], "VALUE" => "TEXT"];
$plain = $this->createTree($format, 50, 2, "crossed");
$key = str_pad("key1", 16, "0", STR_PAD_LEFT);
$plain->put(["KEY" => $key, "VALUE" => "one"]);
$plain->flush();
$lsm_tree = new CrossedWalkTree($plain->folder, $format, 50, 2);
$values = array_column($lsm_tree->get($key), "VALUE");
$this->assertEqual($values, ["one"], "the row is given once");
$this->assertEqual($lsm_tree->walks, 2, "the tiers are walked again");
}
/**
* Checks a lookup whose file has gone for good gives up quietly,
* returning no rows and logging nothing. The failed read used to
* warn on every lookup, filling a live error log.
*/
public function keyWhoseFileHasGoneIsQuietTestCase()
{
$format = ["PRIMARY KEY" => ["KEY", 16], "VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, 20, 1, "gone");
for ($i = 0; $i < 30; $i++) {
$key = str_pad("key$i", 16, "0", STR_PAD_LEFT);
$lsm_tree->put(["KEY" => $key, "VALUE" => "value$i"]);
}
$lsm_tree->flush();
$key = str_pad("key7", 16, "0", STR_PAD_LEFT);
$this->assertTrue(!empty($lsm_tree->get($key)),
"the key is found while its file is there");
$data_files = [];
foreach (glob($lsm_tree->folder . "/*/A/*/" .
LSMTree::DATA_FILE_PREFIX . "*") as $data_file) {
$data_files[] = $data_file;
}
$this->assertTrue(!empty($data_files),
"the tree has data files to take away");
foreach ($data_files as $data_file) {
unlink($data_file);
}
$warnings = 0;
set_error_handler(function ($number) use (&$warnings) {
/* a handler sees suppressed diagnostics too, so count only
what the error log would have been given */
if (error_reporting() & $number) {
$warnings++;
}
return true;
});
$rows = $lsm_tree->get($key);
restore_error_handler();
$this->assertEqual([], $rows,
"a key whose file has gone comes back as no rows");
$this->assertEqual(0, $warnings,
"and puts no warning in the error log while doing so");
}
/**
* Checks a key is still found after another process has replaced
* the file it sits in. A merge elsewhere writes new data files and
* a new list naming them; this process's cached list still names
* the old file, so every lookup used to fail three times over and
* give up.
*/
public function keyFoundAfterAnotherProcessMovesItsFileTestCase()
{
$format = ["PRIMARY KEY" => ["KEY", 16], "VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, 20, 1, "moved");
$key = str_pad("key7", 16, "0", STR_PAD_LEFT);
for ($i = 0; $i < 30; $i++) {
$this_key = str_pad("key$i", 16, "0", STR_PAD_LEFT);
$lsm_tree->put(["KEY" => $this_key, "VALUE" => "value$i"]);
}
$lsm_tree->flush();
$rows = $lsm_tree->get($key);
$this->assertEqual("value7", $rows[0]["VALUE"],
"the key is found, and the file lists are now cached");
/* do on disk what a merge in another process does: each data
file gets a new name, still sorting at or below the keys it
holds, and the list naming it is rewritten */
$lists = glob($lsm_tree->folder . "/*/A/F*/" . LSMTree::INDEX_FILE);
$this->assertTrue(!empty($lists), "there are file lists to rewrite");
foreach ($lists as $list) {
$folder = dirname($list);
$names = array_filter(explode("\n", file_get_contents($list)));
$renamed = [];
foreach ($names as $name) {
$new_name = str_replace("key", "jey", $name);
rename("$folder/$name", "$folder/$new_name");
$renamed[] = $new_name;
}
file_put_contents($list, implode("\n", $renamed));
}
$rows = $lsm_tree->get($key);
$this->assertEqual("value7", $rows[0]["VALUE"] ?? "",
"and is found again though its file has moved");
}
/**
* A merge empties a tier and later writes a tier of the same name
* with other rows. The record lists of the first tier were cached
* by file name, so the merge that came later read the first tier's
* rows in place of the new ones and every key came back with its
* first two partitions repeated. The tree is driven here the way the
* index bundle drives it: one slot per partition, a merge after
* each, so that Tier 1 is emptied and written again.
*/
public function tierRewrittenUnderSameNameMergesNewRowsTestCase()
{
$format = ["PRIMARY KEY" => ["TERM", 16], "PARTITION" => "INT"];
$lsm_tree = $this->createTree($format, 100000, 2, "rewrite");
$key = str_pad("00000002", 16, "_");
$partitions = 6;
for ($partition = 0; $partition < $partitions; $partition++) {
$lsm_tree->selectPutSlot(file_exists($lsm_tree->folder .
"/Tier0000/A") ? "B" : "A");
for ($term = 1; $term <= 3; $term++) {
$lsm_tree->put(["TERM" => str_pad(sprintf("%08d", $term),
16, "_"), "PARTITION" => $partition]);
}
$lsm_tree->flush();
$lsm_tree->mergeTiers();
}
$seen = array_map('intval', array_column($lsm_tree->get($key),
"PARTITION"));
sort($seen);
$this->assertEqual(range(0, $partitions - 1), $seen,
"Every partition's row survives merges that rewrite a tier");
}
/**
* A dictionary buffer can hold two rows for one term, since a term
* that is on pages of two partitions is put once for each. Written
* as two records with the same key, a read finds one of them and the
* other row is lost, so a term answers for fewer partitions than it
* was given. The two rows are merged in the buffer instead, and this
* case reads the key back and asks for both.
*/
public function twoRowsForOneKeyInABufferBothSurviveTestCase()
{
$format = ["PRIMARY KEY" => ["TERM", 16], "PARTITION" => "INT",
"NUM_DOCS" => "INT"];
$lsm_tree = $this->createTree($format, 100000, 2, "two_rows");
$key = str_pad("00000002", 16, "_");
$lsm_tree->put(["TERM" => $key, "PARTITION" => 0,
"NUM_DOCS" => 5]);
$lsm_tree->put(["TERM" => $key, "PARTITION" => 1,
"NUM_DOCS" => 6]);
$lsm_tree->flush();
$rows = $lsm_tree->get($key);
$seen = array_map('intval', array_column($rows, "PARTITION"));
sort($seen);
$this->assertEqual([0, 1], $seen,
"Both rows put for one key in a buffer are read back");
$docs = array_map('intval', array_column($rows, "NUM_DOCS"));
sort($docs);
$this->assertEqual([5, 6], $docs,
"Each row keeps the values it was put with");
}
/**
* A data file is named for the first key it holds, and the lowest
* term of a crawl's dictionary starts nearly every partition's list,
* so two flushes can name the same file. Writing over the file drops
* every row already in it, which is a term answering for the last
* partitions only. This case flushes twice into one slot without a
* merge between, which is what a run interrupted mid-merge leaves,
* and asks for every partition back.
*/
public function flushOverAFileOfTheSameNameKeepsItsRowsTestCase()
{
$format = ["PRIMARY KEY" => ["TERM", 16], "PARTITION" => "INT",
"NUM_DOCS" => "INT"];
$lsm_tree = $this->createTree($format, 100000, 2, "same_file");
$partitions = 12;
for ($partition = 0; $partition < $partitions; $partition++) {
$lsm_tree->selectPutSlot(file_exists($lsm_tree->folder .
"/Tier0000/A") ? "B" : "A");
for ($term = 1; $term <= 3; $term++) {
$lsm_tree->put(["TERM" => str_pad(sprintf("%08d", $term),
16, "_"), "PARTITION" => $partition,
"NUM_DOCS" => $partition]);
}
$lsm_tree->flush();
if ($partition % 3 == 2) {
$lsm_tree->mergeTiers();
}
}
$lsm_tree->mergeTiers();
for ($term = 1; $term <= 3; $term++) {
$key = str_pad(sprintf("%08d", $term), 16, "_");
$seen = array_map('intval', array_column($lsm_tree->get($key),
"PARTITION"));
sort($seen);
$this->assertEqual(range(0, $partitions - 1), $seen,
"Term $term answers for every partition it was put for");
}
}
/**
* keysWhoseNamesSortOutOfKeyOrderAreFoundTestCase checks that every key
* can be looked up after a merge when the URL-encoded names of the
* files holding the keys sort in another order than the keys. Here =
* is written as %3D, which sorts before - and the digits, and a key's
* \xFE and \xFF bytes are escaped where the key is stored.
*/
public function keysWhoseNamesSortOutOfKeyOrderAreFoundTestCase()
{
$format = ["PRIMARY KEY" => ["KEY", 16], "VALUE" => "TEXT"];
$lsm_tree = $this->createTree($format, 50, 2, "key_order");
$keys = [];
foreach (["ab", "ab=", "ab-", "abc"] as $start) {
foreach (["-", ".", "0", "=", "c"] as $letter) {
$keys[] = str_pad("$start{$letter}x", 16, "_");
}
}
$keys[] = str_pad("ab\xFEx", 16, "\xFF");
$keys[] = str_pad("ab\xFFx", 16, "\xFE");
sort($keys, SORT_STRING);
foreach (["A", "B"] as $at => $slot) {
$lsm_tree->selectPutSlot($slot);
foreach ($keys as $i => $key) {
if ($i % 2 == $at) {
$lsm_tree->put(["KEY" => $key, "VALUE" => "value$i"]);
}
}
$lsm_tree->flush();
}
$lsm_tree->mergeTiers();
foreach ($keys as $i => $key) {
$values = $lsm_tree->get($key);
$this->assertEqual("value$i", $values[0]["VALUE"] ?? "",
"Found the value of key $i");
}
}
}
/**
* CrossedWalkTree is an LSMTree whose first walk of the tiers is crossed
* by a merge: while reading tier 0 it adds two to the merge count, as
* mergeTier does around its renames, and gives the tier's rows twice.
*/
class CrossedWalkTree extends LSMTree
{
/**
* $walks counts the walks of tier 0, one for each walk of the tree.
* @var int
*/
public $walks = 0;
/**
* getTier gives tier $tier's rows for $key, twice on the first walk of
* tier 0, after adding two to the merge count.
*
* @param int $tier the tier to read
* @param string $key the key to look up
* @return mixed the rows, as LSMTree::getTier gives them
*/
public function getTier($tier, $key)
{
$rows = parent::getTier($tier, $key);
if ($tier == 0) {
$this->walks++;
if ($this->walks == 1) {
$this->addToMergeGeneration();
$this->addToMergeGeneration();
$rows = array_merge($rows ?? [], $rows ?? []);
}
}
return $rows;
}
}
- Yioop Repo - Seekquarry