100行PHP解析LevelDB SSTableファイル

LevelDBのSSTableファイルを開いて、中のkey-valueデータを解析して印刷して、SSTableフォーマットを理解する必要があるのは見てもいいです.
概略解析手順:

末尾のFooter情報を先に読み出し、Footerは48バイトに固定され、Index blockがファイル中で

オフセットしていることがFooterから分かる.

はIndex Blockを解析し、Index Blockから各Data Blockのファイル内の位置を知ることができる.Index Blockの各項目はkey-value構造であり、valueが格納されているのは対応するData Blockの位置と大きさであり、keyは対応するData Blockの中で最大のkeyであり、まだ少し大きいkeyである.例えば、Data Blockの中で最大のkeyはhelloであり、Index Blockのkeyはhelloa

である.

各Data Blockを解析し、各key-value対

を得る.

$data = file_get_contents('testdb/000009.ldb');
$size = strlen($data);
// footer = meta block handle + index block handle + padding + 8-byte magic number
// footer is fixed 48 byte, parse from this offset
$offset = $size - 48;

// meta block is used for performance, so we can skip parse it
list($metaBlockOffset,$metaBlockSize,$offset) = decodeBlockHandle($offset);
list($idxBlockOffset,$idxBlockSize,$offset) = decodeBlockHandle($offset);

// when parsed one k-v item from index block, this callback function will run
$handleIndexBlockItem = function($key, $seq, $kType, $valBegin, $valLen) {
    global $data;
    list($datablockOffset,$datablockSize,) = decodeBlockHandle($valBegin);
    readBlock($datablockOffset, $datablockSize, function ($key, $seq, $kType, $valBegin, $valLen) {
        global $data;
        $value = substr($data, $valBegin, $valLen);
        echo $key . ' = ' . $value . PHP_EOL;
    });
};
readBlock($idxBlockOffset, $idxBlockSize, $handleIndexBlockItem);

function readBlock($offset, $size, $itemCallback) {
    global $data;
    $blockType = ord($data[$offset]);
    $blockChecksum = decodeInt32($offset+1);
    $restartNum = decodeInt32($offset+$size-4);
    printf("Block: offset=%s, size=%d, type=%d, num_of_restarts=%d, crc32c=%d
", 
        dechex($offset), $size, $blockType, $restartNum, $blockChecksum);
    $cur = $offset;
    $currentSharedKey = '';
    while ($cur != $offset+$size-4-$restartNum*4) {
        // format: shared key length | unshared key length | value length | unshared key | value
        $begin = $cur;
        list($shareLen, $len) = decodeVarInt($cur);
        $cur += $len;
        list($unshareLen, $len) = decodeVarInt($cur);
        $cur += $len;
        list($valLen, $len) = decodeVarInt($cur);
        $cur += $len;

        $unsharedKey = substr($data, $cur, $unshareLen-8);
        if ($shareLen === 0) {
            $currentSharedKey = $unsharedKey;
        }
        // key format: user's binary key | 7-byte sequence number | 1-byte type code
        $key = substr($currentSharedKey, 0, $shareLen) . $unsharedKey;
        $int = decodeInt64($cur+$unshareLen-8);
        $seq = $int >> 8;
        $kType = $seq && 0xff; // enum ValueType { kTypeDeletion = 0x0, kTypeValue = 0x1 };

        $cur += $unshareLen;
        $valBegin = $cur;
        if (is_callable($itemCallback)) {
            $itemCallback($key, $seq, $kType, $valBegin, $valLen);
        }
        $cur += $valLen;
    }
}

function decodeBlockHandle($offset) {
    global $data;
    list($blockOffset, $offsetLen) = decodeVarInt($offset);
    list($blockSize, $sizeLen) = decodeVarInt($offset+$offsetLen);
    return [$blockOffset, $blockSize, $offset+$offsetLen+$sizeLen];
}

function decodeVarInt($offset) {
    global $data;
    $len = 0;
    $result = 0;
    while (true) {
        $byte = ord($data[$offset+$len]);
        $result |= ($byte & 0x7f) << (7 * $len);
        $len++;
        if (($byte & 0x80) === 0) {
            // stop when first bit of byte is 0
            break;
        }
    }
    return [$result, $len];
}

function decodeInt32($offset) {
    return decodeFixedInt($offset, 32);
}
function decodeInt64($offset) {
    return decodeFixedInt($offset, 64);
}
function decodeFixedInt($offset, $bitLen) {
    global $data;
    $result = 0;
    for ($i = 0; $i != $bitLen / 8; $i++) {
        $byte = ord($data[$offset+$i]);
        $result |= $byte << (8*$i);
    }
    return $result;
}