<?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
*
* @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\library\data_structures;
use seekquarry\yioop\library as L;
use seekquarry\yioop\configs as C;
/**
* LSMTree holds sortable records in a log structured merge tree: rows are
* written into a small in-memory buffer, the buffer is written out as a
* file of a tier, and tiers are merged into larger ones as they fill.
* Yioop keeps a crawl's dictionary in one, where each key is a term and
* its rows say which partition holds the term's postings.
*
* @author Chris Pollett
*/
class LSMTree
{
/**
* Maximum number of records held in an in-memory block before
* the block is sealed and written out as the next on-disk file
*/
const BLOCK_FACTOR = 10000;
/**
* Maximum number of records the per-instance LRU read-cache
* (record_cache) can hold
*/
const RECORD_CACHE_SIZE = 100;
/**
* Filename prefix for a data file within a tier folder. A data file
* holds a run of records sorted by key and is named for the first
* key it holds.
*/
const DATA_FILE_PREFIX = "D";
/**
* Filename prefix used by the in-memory block-bookkeeping files
*/
const FOLDER_PREFIX = "F";
/**
* Filename within a tier folder that lists the data files sealed in
* that folder, in key order
* in tier order
*/
const INDEX_FILE = "index.txt";
/**
* How many times get walks the tiers again when a merge has taken
* away a file a tier index named
*/
const READ_TRIES = 3;
/**
* What a tier returns when a file its index named could not be read,
* as against false, which says the key is not in that tier
*/
const READ_AGAIN = "read again";
/**
* Most bytes the vByte count of records at the start of a row's values
* takes, for the five bytes a 32 bit count can need
*/
const MAX_COUNT_BYTES = 5;
/**
* Maximum bytes of a single data file before LSMTree rolls over to the
* next file. Merging two tiers of 800,000 dictionary rows wrote 155
* files at this size against 1,228 at 32KB, so a merge syncs and later
* deletes an eighth as many files, and 2,000 lookups with nothing
* cached took 0.52 seconds against 1.21.
*/
const MAX_FILE_SIZE = 262144;
/**
* Most seconds removeAsideTiers spends deleting merged tiers' files
* in one call, so the indexer goes back to indexing between calls
*/
const ASIDE_REMOVAL_SECONDS = 1;
/**
* Filename storing the highest tier index currently in use by
* this LSMTree on disk
*/
const MAX_TIER_FILENAME = "max_tier.txt";
/**
* MERGE_GENERATION_FILE names the file, in the tree's folder, holding
* a count mergeTier adds one to just before it puts a merged tier in
* place and again once it has moved the merged tiers aside. The count
* is odd only between those two renames, when a lookup could find a
* key's rows in both the merged tier and an old one, or in neither.
*/
const MERGE_GENERATION_FILE = "merge_generation.txt";
/**
* Microseconds get waits before reading the merge generation again
* while it is odd
*/
const MERGE_WAIT_MICROSECONDS = 10000;
/**
* Most times get waits MERGE_WAIT_MICROSECONDS for a merge's two
* renames to finish before it reads the tiers as they are
*/
const MERGE_WAITS = 100;
/**
* Most tiers mergeTiersSpread leaves with both slots full. A lookup
* reads both slots of a full tier, so this bounds the slots it reads
* beyond one a tier.
*/
const MAX_FULL_TIERS = 2;
/**
* Subfolder-name prefix used for each tier directory (combined
* with a zero-padded index, e.g. "Tier0001")
*/
const TIER_PREFIX = "Tier";
/**
* REMOVING_PREFIX starts the name a merged tier's folder is given once
* the merge is in place, until removeAsideTiers has deleted it. The
* name does not start with TIER_PREFIX, so neither a lookup nor
* getMaxTier sees the folder.
*/
const REMOVING_PREFIX = "removing-";
/**
* $base_slot names which of a tier's two slots, A or B, the next put
* writes into. A caller sets it with selectPutSlot before a run of
* puts, so a run that follows an unmerged one does not write over
* the files the earlier run left.
* @var string
*/
public $base_slot = "A";
/**
* $put_slot is the tier object the current run of puts writes into,
* made on the first put of the run and kept until the tree is
* flushed.
* @var Tier
*/
public $put_slot = null;
/**
* $table_tools is the PackedTableTools object that packs a row into
* the bytes a record holds and unpacks those bytes back into a row,
* following the column format the tree was made with.
* @var PackedTableTools
*/
public $table_tools;
/**
* $max_tier holds, for each tree folder this process has read, the
* number of the highest tier the tree holds and the second it was
* read from the file in that folder, so a lookup knows how many
* tiers it has to walk. Another process can raise or lower that
* number, as a rebuild of the whole dictionary does, so a number
* read in an earlier second is read again from the file.
* @var array
*/
public static $max_tier = [];
/**
* __construct opens the tree kept in a folder, making the folder
* when it is not there yet. The column format says what a row holds
* and which column is the key; the two sizes say how large a data
* file may grow and how many data files a folder of a tier holds.
*
* @param string $folder the folder for storing the LSMTree files
* @param array $format the column names, keys and types for this
* LSMTree object
* @param int $max_file_size cap in bytes for an individual tier
* slot file before it rolls over to the next tier
* @param int $block_factor number of fixed-size records per disk
* block; controls B+-tree fan-out within each tier slot
* @param bool $read_only whether the tree is opened only to be read,
* as a search does; a reader leaves an unfinished merge for a
* process that writes the tree to undo
*/
public function __construct(public $folder, $format,
public $max_file_size = self::MAX_FILE_SIZE,
public $block_factor = self::BLOCK_FACTOR, $read_only = false)
{
if (empty($format['PRIMARY KEY'][1]) || $format['PRIMARY KEY'][1] < 0) {
throw new \Exception(
"LSMTree class requires fixed lengthed keys");
}
if (!file_exists($folder)) {
mkdir($folder);
chmod($folder, 0777);
}
/* A tier merge a stopped process left part way is removed, or
completed if it had committed, before any tier is read. */
$undone_steps = [];
if (!$read_only) {
/* A tier's files are written once, synced and renamed into
place by mergeTier, and never grow, so a checkpoint of
their lengths is of no use. A checkpoint in the tree's
folder is removed before undo, which would read the size
of every file it lists. */
@unlink($folder . "/" . UndoLog::CHECKPOINT_NAME);
$undo_log = new UndoLog($folder);
$undone_steps = $undo_log->undo();
foreach ($undone_steps as $undone_step) {
L\crawlLog(
"LSMTree undid an unfinished $undone_step in $folder");
}
foreach ($undo_log->checkpoint_notes as $note) {
L\crawlLog("LSMTree checkpoint: $note");
}
}
/* An undone or completed merge may leave a different highest
tier than the one stored, so it is worked out again. */
$this->getMaxTier(!empty($undone_steps));
$this->table_tools = new PackedTableTools($format);
}
/**
* Returns the on-disk folder path for a given tier of the LSM tree.
*
* @param int $tier zero-based tier index
* @return string absolute filesystem path to the tier's folder,
* built as "$this->folder/TIER_PREFIX####" with the index
* zero-padded to 4 digits
*/
public function getTierFolder($tier)
{
return $this->folder . "/" . self::TIER_PREFIX .
sprintf("%'.04d", $tier);
}
/**
* True if the given tier currently has slot A populated on disk.
*
* @param int $tier zero-based tier index
* @return bool true when the tier folder contains its "A" slot
* file (i.e. the tier currently holds an SSTable)
*/
public function occupiedTier($tier)
{
return file_exists($this->getTierFolder($tier) . "/A");
}
/**
* getMaxTier gives the number of the highest tier this tree holds, so
* a lookup knows how many tiers to walk and a merge knows where to
* stop. It reads the number from the tree's max_tier.txt file at
* most once a second, since another process, such as a rebuild of
* the whole dictionary, can change it while this process runs. When
* asked to recompute, it looks at the tier folders on disk instead
* and writes what it finds back to that file.
*
* @param bool $recompute true to work the number out from the tier
* folders on disk, false to read it from max_tier.txt
* @return int the number of the highest tier the tree holds
*/
public function getMaxTier($recompute = false)
{
$now = time();
$held = self::$max_tier[$this->folder] ?? null;
if (!$recompute && $held !== null && $held[1] == $now) {
return $held[0];
}
$max_path = $this->folder . "/" . self::MAX_TIER_FILENAME;
if (!$recompute && file_exists($max_path)) {
$max_tier = intval(file_get_contents($max_path));
self::$max_tier[$this->folder] = [$max_tier, $now];
return $max_tier;
}
$tier_path = $this->folder . "/" . self::TIER_PREFIX;
$tiers = glob($tier_path . "*");
sort($tiers);
$last_tier = (!empty($tiers) && count($tiers) > 0) ?
$tiers[count($tiers) - 1] : $this->folder . "/" .
self::TIER_PREFIX . "0";
$max_tier = intval(substr($last_tier,
strlen($tier_path)));
L\filePutContentsWhole($max_path, $max_tier);
self::$max_tier[$this->folder] = [$max_tier, $now];
return $max_tier;
}
/**
* Within a tier select which of the two slots (A or B) to write
* entry data to
*
* @param string $letter "A" or "B" identifying the destination slot;
* any other value falls through to "B"
*/
public function selectPutSlot($letter)
{
$this->base_slot = ($letter == "A") ? "A" : "B";
$this->put_slot = null;
}
/**
* Appends a record into the currently-selected slot at tier 0,
* creating the Tier writer lazily on the first call after a
* slot selection.
*
* @param array $row record to insert (PackedTableTools-shaped)
*/
public function put($row)
{
if (empty($this->put_slot)) {
$put_folder = $this->getTierFolder(0) . "/" . $this->base_slot;
$this->put_slot = new Tier($put_folder, $this->table_tools, "w",
$this->max_file_size, $this->block_factor);
}
$this->put_slot->put($row , false);
}
/**
* Flushes any in-memory data into the active slot at tier 0.
*/
public function flush()
{
if (!empty($this->put_slot)) {
$this->put_slot->flush();
}
}
/**
* Merges any tiers with both slots filled in the LSTM into
* a tier in a slot one level higher
*/
public function mergeTiers()
{
L\crawlLog("..Begin LSMTiers Merging Tiers..");
$max_tier = $this->getMaxTier();
L\crawlLog("....begin Max Tier is: $max_tier");
for ($i = 0; $i <= $max_tier; $i++)
{
$tier_folder = $this->getTierFolder($i);
if (file_exists($tier_folder . "/B")) {
L\crawlLog("....Merging Tier $i");
$this->mergeTier($i);
} else {
L\crawlLog("....Tier $i doesn't need to be merged.");
}
}
$max_tier = $this->getMaxTier(true);
L\crawlLog("....end Max Tier is: $max_tier");
/* A program that merges tiers but is not the indexer, which calls
removeAsideTiers between files, still deletes what it moved
aside, a second's worth at each merge. */
$this->removeAsideTiers();
L\crawlLog("..End LSMTiers Merging Tiers..");
}
/**
* mergeTiersSpread merges tier 0 when both its slots are full, so the
* next partition has a slot to go in, and then at most one higher
* tier, the lowest with both slots full. mergeTiers merges every full
* tier at once, and on a large dictionary a run of tiers 0, 1 and 2
* stopped the indexer for 28 seconds; this way that work is spread
* over the merges of several partitions. A tier whose merge needs a
* slot in the tier above, both of whose slots are full, merges that
* tier first.
*/
public function mergeTiersSpread()
{
L\crawlLog("..Begin LSMTiers Merging Tiers, one above tier 0..");
$merged = [];
if ($this->tierIsFull(0)) {
$this->mergeTierWithRoom(0, $merged);
}
/* One higher tier merges at each call, and more while over
MAX_FULL_TIERS tiers are full, since a lookup reads both slots
of a full tier. */
$merged_higher = 0;
$max_tier = $this->getMaxTier(true);
for ($i = 1; $i <= $max_tier; $i++) {
if (!$this->tierIsFull($i)) {
continue;
}
$full = 0;
for ($j = $i; $j <= $max_tier; $j++) {
$full += $this->tierIsFull($j) ? 1 : 0;
}
if ($merged_higher > 0 && $full <= self::MAX_FULL_TIERS) {
break;
}
$this->mergeTierWithRoom($i, $merged);
$merged_higher++;
}
$this->getMaxTier(true);
L\crawlLog("....merged tiers: " . (empty($merged) ? "none" :
implode(", ", $merged)));
$this->removeAsideTiers();
L\crawlLog("..End LSMTiers Merging Tiers..");
}
/**
* mergeGeneration reads the count in MERGE_GENERATION_FILE, which is
* odd while a merge is between putting its merged tier in place and
* moving the merged tiers aside. A tree no merge has touched has none
* and gives 0.
*
* @return int the count
*/
public function mergeGeneration()
{
return intval(@file_get_contents($this->folder . "/" .
self::MERGE_GENERATION_FILE));
}
/**
* addToMergeGeneration adds one to the count in MERGE_GENERATION_FILE,
* writing it whole. mergeTier calls it before and after its two
* renames.
*/
public function addToMergeGeneration()
{
L\filePutContentsWhole($this->folder . "/" .
self::MERGE_GENERATION_FILE, $this->mergeGeneration() + 1);
}
/**
* tierIsFull says whether both slots, A and B, of tier $tier hold
* rows, so the tier must merge before a lower tier merges into it.
*
* @param int $tier the tier to look at
* @return bool whether both slots are full
*/
public function tierIsFull($tier)
{
return file_exists($this->getTierFolder($tier) . "/B");
}
/**
* mergeTierWithRoom merges tier $tier into the tier above, first
* merging the tier above, and so on up, where that tier has both its
* slots full. mergeTiersSpread calls it.
*
* @param int $tier the tier to merge
* @param array &$merged the tiers merged so far, added to
*/
public function mergeTierWithRoom($tier, &$merged)
{
if ($this->tierIsFull($tier + 1)) {
$this->mergeTierWithRoom($tier + 1, $merged);
}
L\crawlLog("....Merging Tier $tier");
$this->mergeTier($tier);
$merged[] = $tier;
}
/**
* emptyTier takes the folder of tier $tier out of the tree once
* mergeTier has put the tier's rows in the merged tier and the merge
* has committed. The folder moves aside to $removing_folder in one
* rename, which a lookup sees as the tier being gone, and
* removeAsideTiers deletes its files later, a second at a time, so a
* merge of a large tier does not stop the indexer while thousands of
* files are deleted. Where the rename fails, as it can on Windows
* while a file in the folder is open, it is deleted in place.
*
* @param int $tier tier to take out of the LSMTree
* @param string $removing_folder the folder it is moved to
*/
public function emptyTier($tier, $removing_folder)
{
$tier_folder = $this->getTierFolder($tier);
if (!file_exists($tier_folder) ||
@rename($tier_folder, $removing_folder)) {
return;
}
$db_class = C\NS_DATASOURCES . ucfirst(C\p('DBMS')) . "Manager";
$db = new $db_class();
$db->unlinkRecursive($tier_folder, true);
}
/**
* removeAsideTiers deletes the files of tiers emptyTier moved aside,
* for at most $seconds, and each folder once it is empty. The indexer
* calls it after each file it processes. A folder a stopped process
* left is deleted the same way.
*
* @param float $seconds most time to spend deleting
* @return bool whether any moved aside tier is left to delete
*/
public function removeAsideTiers($seconds = self::ASIDE_REMOVAL_SECONDS)
{
$give_up = microtime(true) + $seconds;
$folders = glob($this->folder . "/" . self::REMOVING_PREFIX . "*",
GLOB_ONLYDIR) ?: [];
foreach ($folders as $folder) {
$entries = new \RecursiveIteratorIterator(
new \RecursiveDirectoryIterator($folder,
\FilesystemIterator::SKIP_DOTS),
\RecursiveIteratorIterator::CHILD_FIRST);
foreach ($entries as $entry) {
$entry->isDir() ? @rmdir($entry->getPathname()) :
@unlink($entry->getPathname());
if (microtime(true) > $give_up) {
return true;
}
}
@rmdir($folder);
}
return false;
}
/**
* Compares the keys in two LSMTree entries and returns
* -1 is $entry_a < $entry_b, 0 if $entry_a == $entry_b,
* and 1 if $entry_a > $entry_b
*
* @param string $entry_a first LSMTree entry
* @param string $entry_b first LSMTree entry
* @return int result of comparison as described above
*/
public function compare($entry_a, $entry_b)
{
$key_len = $this->table_tools->key_len;
return strncmp($entry_a, $entry_b, $key_len);
}
/**
* mergeEncodedEntries combines two entries with the same key, both as
* a tier file stores them, with their 255 bytes encoded, into one
* entry in the same form. A row holds its key, a count of records in
* vByte form, then the records, and encoding works byte by byte, so
* the merged row is the encoded key and new count followed by each
* row's encoded records as they stand. Only the start of each row is
* decoded, which matters for a word found in thousands of partitions,
* whose row is long. mergeTier calls it where both tiers hold a key.
*
* @param string $entry_a first entry, encoded
* @param string $entry_b second entry, encoded, with the same key
* @return string the merged entry, encoded
*/
public function mergeEncodedEntries($entry_a, $entry_b)
{
$key_len = $this->table_tools->key_len;
$head_len = $key_len + self::MAX_COUNT_BYTES;
$count = 0;
$records = "";
foreach ([$entry_a, $entry_b] as $entry) {
$head = L\decode255(substr($entry, 0, 2 * $head_len));
$pos = $key_len;
$count += L\vByteDecode($head, $pos);
$records .= substr($entry, strlen(L\encode255(
substr($head, 0, $pos))));
}
return L\encode255(substr(L\decode255(substr($entry_a, 0,
2 * $key_len)), 0, $key_len) . L\vByteEncode($count)) . $records;
}
/**
* Merges two tier slots of the same tier $tier into a single tier slot
* at tier $tier + 1. If fewer than two slots filled at a given tier
* than does nothing.
*
* @param int $tier tier to perform merging for
*/
public function mergeTier($tier)
{
$tier_folder = $this->getTierFolder($tier);
if (!file_exists($tier_folder . "/B")) {
return;
}
if (!file_exists($tier_folder . "/A")) {
rename($tier_folder . "/B", $tier_folder . "/A");
return;
}
$a_tier = new Tier($tier_folder . "/A", $this->table_tools);
$b_tier = new Tier($tier_folder . "/B", $this->table_tools);
$next_tier_folder = $this->getTierFolder($tier + 1);
$target_folder = ($this->occupiedTier($tier + 1)) ?
$next_tier_folder . "/B" : $next_tier_folder . "/A";
/* The merged tier is written under a name readers do not look at
and renamed into place when whole, so a search during the merge
reads only the two tiers being merged. The undo log removes a
merge left part way; once the merged tier is in place the merge
commits, and a stop after that removes the merged tiers. */
$writing_folder = $target_folder . ".writing-" . getmypid();
$undo_log = new UndoLog($this->folder);
$step_id = $undo_log->begin("merge of tier $tier", [],
[$next_tier_folder, $writing_folder, $target_folder]);
if (!file_exists($next_tier_folder)) {
mkdir($next_tier_folder);
}
$target_tier = new Tier($writing_folder, $this->table_tools, "w",
$this->max_file_size, $this->block_factor);
$target_tier->defer_index = true;
/* Rows are read and written as the tier files store them, with
their 255 bytes encoded; only the key is decoded, from at most
twice its length of encoded bytes. Where both tiers hold a key,
mergeEncodedEntries joins the two rows without decoding their
records. */
$key_len = $this->table_tools->key_len;
$key_of = function ($row) use ($key_len) {
if ($row === false) {
return false;
}
$key = substr($row, 0, $key_len);
return (strpos($key, "\xFE") === false) ? $key :
substr(L\decode255(substr($row, 0, 2 * $key_len)), 0,
$key_len);
};
$a_row = $a_tier->next(false);
$b_row = $b_tier->next(false);
$a_key = $key_of($a_row);
$b_key = $key_of($b_row);
$cnt = 0;
while(!empty($a_row) || !empty($b_row)) {
$cmp = (empty($b_row)) ? -1 : ((empty($a_row)) ? 1 :
strcmp($a_key, $b_key));
if ($cmp < 0) {
$target_tier->putEncoded($a_row, $a_key);
$a_row = $a_tier->next(false);
$a_key = $key_of($a_row);
} else if ($cmp > 0) {
$target_tier->putEncoded($b_row, $b_key);
$b_row = $b_tier->next(false);
$b_key = $key_of($b_row);
} else {
$target_tier->putEncoded($this->mergeEncodedEntries(
$a_row, $b_row), $a_key);
$a_row = $a_tier->next(false);
$a_key = $key_of($a_row);
$b_row = $b_tier->next(false);
$b_key = $key_of($b_row);
}
$cnt++;
/* The clock is read once every thousand rows, not for each. */
if ($cnt % 1000 == 0) {
L\crawlTimeoutLog("......have merged $cnt items of Tier " .
"$tier.");
}
}
$target_tier->flush();
$target_tier->writeDataIndex();
/* The merged tier's files reach the disk before the tier takes its
place, and the rename reaches it before the merged tiers go. */
UndoLog::syncPaths([$writing_folder]);
$this->addToMergeGeneration();
rename($writing_folder, $target_folder);
UndoLog::syncPath($next_tier_folder);
/* Files read before are cached by path, and the renamed tier's
paths may be those of an earlier tier emptied since, so the
cache is cleared. */
Tier::$cache = [];
/* Readers find tiers up to the stored highest one, so it is
updated as soon as the merged tier is in place, before the
tiers it replaces are removed. */
$this->getMaxTier(true);
/* Each merge moves its tier to a folder of its own name, so a tier
merged again before the last one is deleted does not collide. */
$removing_folder = $this->folder . "/" . self::REMOVING_PREFIX .
basename($tier_folder) . "-" . str_replace(".", "",
sprintf("%.6F", microtime(true)));
$undo_log->commit($step_id, [$tier_folder, $removing_folder]);
$this->emptyTier($tier, $removing_folder);
$this->addToMergeGeneration();
/* The merged tier was synced before it was renamed into place, so
it is not synced or checkpointed again. */
$undo_log->finish($step_id);
}
/**
* get gives the records stored in the LSMTree under $key, or an empty
* array if the tree does not hold it. Where a merge takes a file away
* mid-lookup, the tiers are walked again.
* @param string $key to look up in current LSMTree
* @param int $offset starting record item associated with this key
* to return
* @param int $limit maximum number of record items associated with this
* key to return, null == till end
* @param bool $newest_first whether to count $offset and $limit from
* the newest record rather than the oldest, and give the records
* newest first. Lower tiers hold newer records, so such a walk
* starts at tier 0 and stops once it has $offset + $limit
* records, where the oldest first walk starts at the highest
* tier
* @return array of items associated with this key in the LSMTree
*/
public function get($key, $offset = 0, $limit = null,
$newest_first = false)
{
$max_rows = $offset + ($limit ?? 0);
for ($try = 0; $try < self::READ_TRIES; $try++) {
/* A walk that starts between a merge's two renames, or sees
the count change by its end, could hold a key's rows twice
or not at all, so it waits for the renames and walks again
when they fell inside it. */
$generation = $this->mergeGeneration();
for ($wait = 0; $wait < self::MERGE_WAITS &&
$generation % 2 == 1; $wait++) {
usleep(self::MERGE_WAIT_MICROSECONDS);
$generation = $this->mergeGeneration();
}
$max_tier = $this->getMaxTier();
$rows = [];
$file_gone = false;
if (!file_exists($this->getTierFolder($max_tier))) {
/* The highest tier this process held for this second has
been merged away by another process, so the stored one
is read again. */
unset(self::$max_tier[$this->folder]);
$max_tier = $this->getMaxTier();
}
$tiers = ($newest_first) ? range(0, $max_tier) :
range($max_tier, 0);
foreach ($tiers as $i) {
$add_rows = $this->getTier($i, $key);
if ($add_rows === self::READ_AGAIN) {
/* A merge moved the rows into a tier this walk has
already read, so walk again rather than carry
on. */
$file_gone = true;
break;
}
if (is_array($add_rows)) {
/* A tier gives its rows oldest first, its A slot's
before its newer B slot's. */
if ($newest_first) {
$add_rows = array_reverse($add_rows);
}
// use array_merge rather than + or get wrong results
$rows = array_merge($rows, $add_rows);
}
/* Every tier past this one holds older rows, so a newest
first walk is done once it has the rows asked for. */
if ($limit > 0 && (count($rows) > $max_rows ||
$newest_first && count($rows) == $max_rows)) {
break;
}
}
if (!$file_gone && $this->mergeGeneration() != $generation) {
$file_gone = true;
}
if (!$file_gone) {
if ($offset > 0 || $limit > 0) {
$rows = array_slice($rows, $offset, $limit);
}
return $rows;
}
clearstatcache();
}
L\crawlLog("LSMTree could not read a file holding a key after " .
self::READ_TRIES . " tries, so the key is being reported as " .
"absent. Tree: " . $this->folder);
return [];
}
/**
* Returns the values associated with a key in a given Tier of the
* LSMTree
*
* @param int $tier tier to get values from
* @param string $key key to look up values for
* @return array values associated with $key (unpacked)
*/
public function getTier($tier, $key)
{
/* A tier's B slot holds rows waiting to be merged: a partition just
put into the dictionary, or a merge a stopped process left to
be done again. Reading it too means a search finds those rows. */
$rows = null;
foreach (["A", "B"] as $slot_name) {
$slot_folder = $this->getTierFolder($tier) . "/$slot_name";
if (!file_exists($slot_folder)) {
continue;
}
$slot = new Tier($slot_folder, $this->table_tools);
$slot_rows = $slot->get($key);
if ($slot_rows === self::READ_AGAIN) {
return $slot_rows;
}
if (!empty($slot_rows)) {
$rows = array_merge($rows ?? [], $slot_rows);
}
}
return $rows;
}
}
/**
* Splits a string containing one row of data for the LSMTree into the
* key and a string for the values.
*
* @param string $entry string encoded row to be split
* @param PackedTableTools $table_tools which has the format used to
* encode the entry
* @return array [$key, $values (as a string)]
*/
function entryToKeyValues($entry, $table_tools)
{
$key_len = $table_tools->key_len;
$key = substr($entry, 0, $key_len);
$values = substr($entry, $key_len);
return [$key, $values];
}
/**
* Auxiliary Class used to manage a single Tier from the Logarithmic Merge Tree
* structure
*/
class Tier
{
/**
* For data that has not been flushed to disk, the first key in sorted
* order
* @var string
*/
public $first_active_key;
/**
* @var int
*/
public $iterator_folder_index;
/**
* @var array
*/
public $iterator_folders;
/**
* @var int
*/
public $iterator_file_index;
/**
* @var array
*/
public $iterator_files;
/**
* @var int
*/
public $iterator_entry_index;
/**
* @var array
*/
public $iterator_entries;
/**
* @var string
*/
private $records;
/**
* $last_key is the key of the last entry in $records, kept by put so
* that a row with the same key is found without decoding that entry.
* @var string
*/
private $last_key = "";
/**
* @var string
*/
private $active_filename;
/**
* $written_folders holds, for a tier being written, the names of its
* folders in order, read from the disk at the first flush and kept by
* flush after that; null before the first flush.
* @var array
*/
public $written_folders = null;
/**
* $written_files holds, for a tier being written, the names of the
* data files in its last folder as keys, kept by flush.
* @var array
*/
public $written_files = [];
/**
* $defer_index says whether flush leaves the list of a folder's data
* files to be written once, when the folder is full or when
* writeDataIndex is called, rather than after every data file. Set
* for a tier no reader looks at until it is complete.
* @var bool
*/
public $defer_index = false;
/**
* Tier files already read, by the hash of their path, as [stamp,
* records, second last checked]. Public so LSMTree::mergeTier can empty
* it when a merged tier is renamed onto paths an earlier tier used.
* @var array
*/
public static $cache = [];
/**
* Opens (or creates) a tier-slot folder for reading or writing.
*
* @param string $folder file path to where data in this tier is
* to be stored (typically TierNNNN/A or TierNNNN/B under the
* LSMTree root)
* @param PackedTableTools $table_tools used to pack/unpack
* records for this tier
* @param string $mode access mode for data in this tier: "r" for
* read, "w" for write
* @param int $max_file_size maximum bytes per individual data
* file before rolling over
* @param int $block_factor how many data files should be in a
* block folder before making a new block folder
* @return null returned (leaving the instance partially
* initialised) when the folder does not exist and the
* constructor was invoked in read mode
*/
public function __construct(public $folder, public $table_tools,
public $mode = "r",
public $max_file_size = LSMTree::MAX_FILE_SIZE,
public $block_factor = LSMTree::BLOCK_FACTOR)
{
$folder_exists = file_exists($folder);
if (!$folder_exists) {
if ($mode == "w") {
L\makePath($folder);
} else {
return null;
}
}
if ($mode == "w") {
$this->records = "";
}
$this->reset();
}
/**
* Persists the in-memory $this->records buffer to a new data
* file in the active tier folder, rolling over to a new
* sub-folder when the existing one is full.
*
* The names of the tier's folders and of the data files in its last
* folder are read from the disk once, at the first flush, and kept
* in memory after that. Reading them with glob at every flush cost a
* read of a folder of up to BLOCK_FACTOR names for each data file of
* MAX_FILE_SIZE bytes written. Where $defer_index is set, the list of
* data files of a folder is written once, when the folder is full or
* when writeDataIndex is called, rather than at every flush.
*
* @return bool true on a successful write (or no-op when there
* is nothing to flush); false when the tier was opened
* read-only or no records have been put yet
*/
public function flush()
{
if ($this->mode != "w" || empty($this->first_active_key)) {
return false;
}
if (empty($this->records)) {
return true;
}
if ($this->written_folders === null) {
$this->readWriteState();
}
$tiers_changed = false;
if (empty($this->written_folders) ||
count($this->written_files) >= $this->block_factor) {
if (!empty($this->written_folders)) {
$this->writeDataIndex();
}
$active_folder = LSMTree::FOLDER_PREFIX .
rawurlencode($this->first_active_key);
if (!file_exists($this->folder . "/" . $active_folder)) {
mkdir($this->folder . "/" . $active_folder);
chmod($this->folder . "/" . $active_folder, 0777);
}
$this->written_folders[] = $active_folder;
$this->written_files = [];
$tiers_changed = true;
}
$active_folder = end($this->written_folders);
$active_path = $this->folder . "/" . $active_folder;
$data_file = LSMTree::DATA_FILE_PREFIX . rawurlencode(
$this->first_active_key);
$records = $this->records;
if (isset($this->written_files[$data_file]) &&
file_exists("$active_path/$data_file")) {
/* A data file is named for the first key it holds, and two
buffers can start with the same key, as the lowest term of
a crawl's dictionary is on nearly every partition. Writing
over the file would drop every row already in it, so the
two sets of records are merged into one. */
$records = $this->mergeRecordStrings(
file_get_contents("$active_path/$data_file"), $records);
} else {
$this->written_files[$data_file] = true;
}
file_put_contents("$active_path/$data_file", $records);
unset(self::$cache[L\crawlHash("$active_path/$data_file")]);
if (!$this->defer_index) {
$this->writeDataIndex();
}
if ($tiers_changed) {
$this->writeRecords($this->folder . "/" . LSMTree::INDEX_FILE,
self::namesInKeyOrder($this->written_folders));
}
$this->records = "";
return true;
}
/**
* readWriteState reads, at a writer's first flush, the names of the
* tier's folders and of the data files in the last of them, which
* flush then keeps up to date in memory. A tier slot written to
* before, as slot A at tier 0 is between partitions, starts from what
* is already on disk.
*/
public function readWriteState()
{
$old_cwd = getcwd();
chdir($this->folder);
$this->written_folders = self::namesInKeyOrder(
glob(LSMTree::FOLDER_PREFIX . "*") ?: []);
$this->written_files = [];
if (!empty($this->written_folders)) {
chdir(end($this->written_folders));
foreach (glob(LSMTree::DATA_FILE_PREFIX . "*") ?: [] as $name) {
$this->written_files[$name] = true;
}
}
chdir($old_cwd);
}
/**
* writeDataIndex writes the list of the data files of the folder a
* writer is filling, in the order namesInKeyOrder gives, so a reader
* can find them. flush calls it at every flush unless $defer_index is
* set; LSMTree::mergeTier sets that flag, since the tier it writes is
* not read until it is renamed into place, and calls this once at the
* end.
*/
public function writeDataIndex()
{
if (empty($this->written_folders)) {
return;
}
$active_path = $this->folder . "/" . end($this->written_folders);
$this->writeRecords("$active_path/" . LSMTree::INDEX_FILE,
self::namesInKeyOrder(array_keys($this->written_files)));
}
/**
* namesInKeyOrder sorts a list of folder or data file names of a tier
* by the keys they are named for, compared as bytes. That is the
* order the keys are written in, which binarySearch and the iterator
* rely on. A name is a one-letter prefix and a URL-encoded key, and
* sorting the names as text puts a byte written as %XX before the
* letters and digits that it follows in byte order.
*
* @param array $names folder or data file names
* @return array the names sorted by their keys
*/
public static function namesInKeyOrder($names)
{
$keys = [];
foreach ($names as $name) {
$keys[] = rawurldecode(substr($name, 1));
}
array_multisort($keys, SORT_STRING, $names);
return $names;
}
/**
* Returns the record associated with a $key as stored in this tier,
* or false if the tier does not hold it. Returns LSMTree::READ_AGAIN
* if the data file the tier index named has since been merged away.
* @param string $key to look up in this tier
* @return mixed array of values associated with the key, false, or
* LSMTree::READ_AGAIN
*/
public function get($key)
{
$tier_folders = $this->readRecords(
$this->folder . "/" . LSMTree::INDEX_FILE);
$url_encoded_key = rawurlencode($key);
$key_folder = $this->binarySearch(LSMTree::FOLDER_PREFIX .
$url_encoded_key, $tier_folders);
if (!$key_folder) {
return false;
}
$key_path = $this->folder . "/$key_folder";
$data_files = $this->readRecords("$key_path/" . LSMTree::INDEX_FILE);
$data_file = $this->binarySearch(LSMTree::DATA_FILE_PREFIX .
$url_encoded_key, $data_files);
if (!$data_file) {
return false;
}
$table_tools = $this->table_tools;
$key_len = $table_tools->key_len;
/* A search looks up many keys that share a data file, such as the
info: keys of the pages it scores, so the file's entries are
cached in the same form the tier's iterator reads them in. The
copy is checked against the file on each read, as a merge in
another process may have moved its rows. The file is missing
when such a merge renamed it, which is expected. */
$entries = $this->readCached("$key_path/$data_file",
fn($contents) => explode("\xFF", $contents), true);
if ($entries === null) {
/* The lists that named this file are stale, so drop their
cached copies; otherwise the walk that follows reads the
same lists and fails the same way. */
unset(self::$cache[L\crawlHash(
$this->folder . "/" . LSMTree::INDEX_FILE)]);
unset(self::$cache[L\crawlHash(
"$key_path/" . LSMTree::INDEX_FILE)]);
return LSMTree::READ_AGAIN;
}
/* A data file holds each key once, its entries sorted by key, so
the key is found by binary search. Entries are stored with
encode255, so each is decoded before its key is compared. */
$key_length = strlen($key);
$low = 0;
$high = count($entries) - 1;
while ($low <= $high) {
$mid = ($low + $high) >> 1;
$record = L\decode255($entries[$mid]);
$compare = strncmp($record, $key, $key_length);
if ($compare == 0) {
return $table_tools->unpack(substr($record, $key_len));
}
if ($compare < 0) {
$low = $mid + 1;
} else {
$high = $mid - 1;
}
}
return false;
}
/**
* putEncoded appends an entry as another tier stores it, with its 255
* bytes already encoded, so mergeTier copies a row it does not change
* without decoding and encoding it again. $key is the entry's decoded
* key. A row whose key equals the last one in the buffer goes through
* put, which merges the two.
*
* @param string $encoded_entry the entry as a tier file holds it
* @param string $key the entry's key, decoded
* @return bool true on success; false when the tier was opened
* read-only
*/
public function putEncoded($encoded_entry, $key)
{
if ($this->mode != "w") {
return false;
}
if (strlen($this->records) > 0 && $this->last_key === $key) {
return $this->put(L\decode255($encoded_entry));
}
if (strlen($this->records) + strlen($encoded_entry) + 1 >
$this->max_file_size) {
$this->flush();
}
if (empty($this->records)) {
$this->first_active_key = $key;
$this->records = $encoded_entry;
} else {
$this->records .= "\xFF" . $encoded_entry;
}
$this->last_key = $key;
return true;
}
/**
* Appends a record into the tier's in-memory write buffer,
* flushing automatically once the buffer would exceed
* $max_file_size.
*
* @param mixed $row either a pre-packed entry string
* (key . packed_values) when $is_packed is true, or an
* associative array of column values to be packed
* @param bool $is_packed whether $row is already in the
* on-disk packed form; defaults to true
* @return bool true on success; false when the tier was
* opened read-only
*/
public function put($row, $is_packed = true)
{
if($this->mode != "w") {
return false;
}
$table_tools = $this->table_tools;
$key_len = $table_tools->key_len;
if (!$is_packed) {
$key = $row[$table_tools->key_field];
$packed_row = $table_tools->pack($row);
$entry = $key . $packed_row;
} else {
$entry = $row;
}
$encoded_entry = L\encode255($entry);
if (strlen($this->records) + strlen($encoded_entry) + 1 >
$this->max_file_size) {
$this->flush();
}
if (empty($this->records)) {
list($this->first_active_key,) = entryToKeyValues($entry,
$table_tools);
}
if (strlen($this->records) > 0 &&
strncmp($this->last_key, $entry, $key_len) == 0) {
/* Two rows for one key in a single buffer would be written as
two records, and a read finds one of them, so the other
would be lost. They are merged here instead, the way a tier
merge merges a key held by two tiers. */
$at = strrpos($this->records, "\xFF");
$last_start = ($at === false) ? 0 : $at + 1;
$last_entry = L\decode255(substr($this->records, $last_start));
list($last_key, $last_values) = entryToKeyValues($last_entry,
$table_tools);
list(, $values) = entryToKeyValues($entry, $table_tools);
$this->records = substr($this->records, 0, $last_start) .
L\encode255($last_key . $table_tools->mergeRowValues(
$last_values, $values));
return true;
}
$separator = (strlen($this->records) > 0) ? "\xFF" : "";
$this->records .= $separator . $encoded_entry;
$this->last_key = substr($entry, 0, $key_len);
return true;
}
/**
* binarySearch returns the entry in $haystack whose key is the
* largest one that is <= the key of $needle.
*
* Used for tier-folder and data-file lookups, where folder /
* file names are a one-letter prefix and a URL-encoded key, so a key
* falls inside the folder or file whose key is <= it. Keys are
* compared as bytes, the order the data files hold them in; URL
* encoding does not keep that order, since a byte written as %XX
* sorts by its percent sign.
*
* @param string $needle the search key (prefix-tagged and
* URL-encoded)
* @param array $haystack list of folder or file names from an
* INDEX_FILE, sorted by key as readRecords gives it
* @return mixed the matching haystack entry on hit; false when
* $needle is smaller than every entry or $haystack is
* empty
*/
public function binarySearch($needle, $haystack)
{
$low = 0;
$high = count($haystack) - 1;
$key = rawurldecode(substr($needle, 1));
if ($high < 0 ||
strcmp($key, rawurldecode(substr($haystack[$low], 1))) < 0) {
return false;
}
if (strcmp($key, rawurldecode(substr($haystack[$high], 1))) >= 0) {
return $haystack[$high];
}
while ($high - $low > 1) {
$mid = ($high + $low) >> 1;
$cmp = strcmp($key, rawurldecode(substr($haystack[$mid], 1)));
if ($cmp == 0) {
return $haystack[$mid];
} else if ($cmp < 0) {
$high = $mid;
} else {
$low = $mid;
}
}
return $haystack[$low];
}
/**
* Returns the first entry as a packed string in the LSMTree tier. Also
* resets iterator of this object.
*
* @param bool $decode false to give the entry as it is stored, with
* its 255 bytes encoded, as mergeTier copies it
* @return string|bool first entry if exists, else false
*/
public function firstEntry($decode = true)
{
$folder = $this->folder;
$this->iterator_folders = $this->readRecords("$folder/" .
LSMTree::INDEX_FILE);
if (empty($this->iterator_folders) ||
!is_array($this->iterator_folders)) {
return false;
}
$this->iterator_folder_index = 0;
$iterator_folder = $this->iterator_folders[0];
$file_path = "$folder/$iterator_folder";
$this->iterator_files = $this->readRecords( "$file_path/" .
LSMTree::INDEX_FILE);
if (empty($this->iterator_files) ||
!is_array($this->iterator_files)) {
return false;
}
$this->iterator_file_index = 0;
$iterator_file = $this->iterator_files[0];
$this->iterator_entries = $this->readRecords(
"$file_path/{$iterator_file}", "\xFF");
if (empty($this->iterator_entries) ||
!is_array($this->iterator_entries)) {
return false;
}
$this->iterator_entry_index = 0;
return $decode ? L\decode255($this->iterator_entries[0]) :
$this->iterator_entries[0];
}
/**
* Returns the next tier entry as a packed string iterated over by this
* Tier object.
* @param bool $decode false to give the entry as it is stored, with
* its 255 bytes encoded, as mergeTier copies it
* @return string|bool next entry if exists, else false
*/
public function next($decode = true)
{
if (empty($this->iterator_folders)) {
return $this->firstEntry($decode);
}
$this->iterator_entry_index++;
$entry = $this->iterator_entries[$this->iterator_entry_index] ?? false;
if ($entry) {
return $decode ? L\decode255($entry) : $entry;
}
$folder = $this->folder;
$this->iterator_entry_index = 0;
$this->iterator_file_index++;
$file = $this->iterator_files[$this->iterator_file_index] ?? false;
if ($file) {
$iterator_folder = $this->iterator_folders[
$this->iterator_folder_index];
$file_path = "$folder/$iterator_folder/$file";
$this->iterator_entries = $this->readRecords($file_path, "\xFF");
return $decode ? L\decode255($this->iterator_entries[0]) :
$this->iterator_entries[0];
}
$this->iterator_file_index = 0;
$this->iterator_folder_index++;
$iterator_folder = $this->iterator_folders[
$this->iterator_folder_index] ?? false;
if (!$iterator_folder) {
return false;
}
$folder_path = "$folder/$iterator_folder";
$this->iterator_files = $this->readRecords("$folder_path/" .
LSMTree::INDEX_FILE);
if (empty($this->iterator_files) ||
!is_array($this->iterator_files)) {
return false;
}
$file = $this->iterator_files[0];
$file_path = "$folder_path/$file";
$this->iterator_entries = $this->readRecords($file_path, "\xFF");
return $decode ? L\decode255($this->iterator_entries[0]) :
$this->iterator_entries[0];
}
/**
* Resets to the first entry of the tier, the iterator associated with
* the current Tier object.
*/
public function reset()
{
$this->iterator_folder_index = 0;
$this->iterator_folders = [];
$this->iterator_file_index = 0;
$this->iterator_files = [];
$this->iterator_entry_index = 0;
$this->iterator_entries = [];
}
/**
* Write a sequence of string records $lines into the file $filename,
* separating records with delimiter $delimiter. Deletes file from LRU
* cache of read files
*
* @param string $filename name of file to write records to
* @param array $lines records to write to $filename
* @param string $delimiter string used to separate one records from the
* next
*/
/**
* mergeRecordStrings joins two strings of records into one string of
* records in key order. Each string holds encoded entries separated
* by the byte 255 and sorted by key, as a data file of a tier does.
* Where both strings hold the same key, the values are merged into
* one entry the way a tier merge merges them, so no row is lost.
*
* @param string $old_records the records already in the file
* @param string $new_records the records the flush is adding
* @return string the records of both, in key order
*/
function mergeRecordStrings($old_records, $new_records)
{
$table_tools = $this->table_tools;
$key_len = $table_tools->key_len;
$old_entries = ($old_records === "") ? [] :
explode("\xFF", $old_records);
$new_entries = ($new_records === "") ? [] :
explode("\xFF", $new_records);
$out = [];
$at_old = 0;
$at_new = 0;
$num_old = count($old_entries);
$num_new = count($new_entries);
while ($at_old < $num_old || $at_new < $num_new) {
if ($at_new >= $num_new) {
$out[] = $old_entries[$at_old];
$at_old++;
continue;
}
if ($at_old >= $num_old) {
$out[] = $new_entries[$at_new];
$at_new++;
continue;
}
$old_entry = L\decode255($old_entries[$at_old]);
$new_entry = L\decode255($new_entries[$at_new]);
$compare = strncmp($old_entry, $new_entry, $key_len);
if ($compare < 0) {
$out[] = $old_entries[$at_old];
$at_old++;
} else if ($compare > 0) {
$out[] = $new_entries[$at_new];
$at_new++;
} else {
list($key, $old_values) = entryToKeyValues($old_entry,
$table_tools);
list(, $new_values) = entryToKeyValues($new_entry,
$table_tools);
$out[] = L\encode255($key . $table_tools->mergeRowValues(
$old_values, $new_values));
$at_old++;
$at_new++;
}
}
return implode("\xFF", $out);
}
/**
* writeRecords writes a list of lines to a file, joined by the
* delimiter, and drops the cached copy of that file so a later read
* takes the new contents. A tier calls it for its index files, the
* list of the folders of a tier and the list of the data files of a
* folder.
*
* @param string $filename the file to write
* @param array $lines the lines to write, in the order they go in
* @param string $delimiter what to put between two lines, a newline
* by default
*/
function writeRecords($filename, $lines, $delimiter = "\n")
{
file_put_contents($filename, implode($delimiter, $lines));
$name_hash = L\crawlHash($filename);
unset(self::$cache[$name_hash]);
}
/**
* readRecords gives the contents of a file of this tier as a list of
* string records, read through readCached.
*
* @param string $filename name of file to get records for
* @param string $delimiter what separates one record from the next
* @return array of string records, empty if the file is missing
*/
function readRecords($filename, $delimiter = "\n")
{
return $this->readCached($filename, function ($contents) use (
$filename, $delimiter) {
$record = explode($delimiter, $contents);
/* An index file written before its names were kept in key
order lists them sorted as text, so it is put in key order
here, once, before it is cached. */
if (basename($filename) == LSMTree::INDEX_FILE) {
$record = self::namesInKeyOrder($record);
}
return $record;
}) ?? [];
}
/**
* readCached gives the contents of a file of this tier, made into the
* form $make_record gives, from the cache in self::$cache when the
* copy there is still current, and from the file otherwise. The cache
* keeps the files used last, at most RECORD_CACHE_SIZE of them, and
* drops the one used longest ago when full or when the process nears
* its memory limit.
*
* @param string $filename name of the file to read
* @param callable $make_record makes the cached form from the file's
* contents
* @param bool $check_every_read whether to compare the copy with the
* file on each read, rather than at most once a second
* @return mixed the cached form, or null if the file is missing
*/
function readCached($filename, $make_record, $check_every_read = false)
{
$name_hash = L\crawlHash($filename);
$now = time();
$read_start = microtime(true);
/* Another process can rewrite a tier file under the same name: a
queue server merging while this is the web server, or ArcTool
rebuilding the whole dictionary under a running web server. So
a cached copy is used only while the file still has the size
and time it was read with. Asking the file system that on every
read costs a stat call each time, and a query makes thousands,
so a copy checked in this second is handed back as it is and
one checked earlier is checked again. */
if (!$check_every_read && isset(self::$cache[$name_hash]) &&
self::$cache[$name_hash][2] == $now) {
$tmp = self::$cache[$name_hash];
unset(self::$cache[$name_hash]);
self::$cache[$name_hash] = $tmp; //move to end of array
L\AnalyticsManager::addTiming("dictionary files from memory",
$read_start);
return $tmp[1];
}
/* A tier file can be merged away between the folder walk that
named it and this read, so a missing file gives null rather
than a warning. */
clearstatcache(true, $filename);
if (!file_exists($filename)) {
unset(self::$cache[$name_hash]);
return null;
}
/* The inode is part of the stamp because a merged tier is
renamed into place, and its files can have the path, time and
size of files an earlier tier held there. */
$stamp = fileinode($filename) . ":" . filemtime($filename) . ":" .
filesize($filename);
if (isset(self::$cache[$name_hash]) &&
self::$cache[$name_hash][0] == $stamp) {
$tmp = self::$cache[$name_hash];
$tmp[2] = $now;
unset(self::$cache[$name_hash]);
self::$cache[$name_hash] = $tmp; //move to end of array
L\AnalyticsManager::addTiming(
"dictionary files checked on disk and kept", $read_start);
return $tmp[1];
}
$contents = @file_get_contents($filename);
if ($contents === false) {
unset(self::$cache[$name_hash]);
return null;
}
$record = $make_record($contents);
L\AnalyticsManager::addTiming("dictionary files read from disk",
$read_start);
self::$cache[$name_hash] = [$stamp, $record, $now];
if (count(self::$cache) >= LSMTree::RECORD_CACHE_SIZE ||
memory_get_usage() >
L\metricToInt(C\INDEX_FILE_MEMORY_LIMIT) * C\MEMORY_FILL_FACTOR) {
array_shift(self::$cache);
}
return $record;
}
}
- Yioop Repo - Seekquarry