vendor/github.com/syndtr/goleveldb/leveldb/table/table.go

   1 // Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com>
   2 // All rights reserved.
   3 //
   4 // Use of this source code is governed by a BSD-style license that can be
   5 // found in the LICENSE file.
   6
   7 // Package table allows read and write sorted key/value.
   8 package table
   9
  10 import (
  11         "encoding/binary"
  12 )
  13
  14 /*
  15 Table:
  16
  17 Table is consist of one or more data blocks, an optional filter block
  18 a metaindex block, an index block and a table footer. Metaindex block
  19 is a special block used to keep parameters of the table, such as filter
  20 block name and its block handle. Index block is a special block used to
  21 keep record of data blocks offset and length, index block use one as
  22 restart interval. The key used by index block are the last key of preceding
  23 block, shorter separator of adjacent blocks or shorter successor of the
  24 last key of the last block. Filter block is an optional block contains
  25 sequence of filter data generated by a filter generator.
  26
  27 Table data structure:
  28                                                          + optional
  29                                                         /
  30     +--------------+--------------+--------------+------+-------+-----------------+-------------+--------+
  31     | data block 1 |      ...     | data block n | filter block | metaindex block | index block | footer |
  32     +--------------+--------------+--------------+--------------+-----------------+-------------+--------+
  33
  34     Each block followed by a 5-bytes trailer contains compression type and checksum.
  35
  36 Table block trailer:
  37
  38     +---------------------------+-------------------+
  39     | compression type (1-byte) | checksum (4-byte) |
  40     +---------------------------+-------------------+
  41
  42     The checksum is a CRC-32 computed using Castagnoli's polynomial. Compression
  43     type also included in the checksum.
  44
  45 Table footer:
  46
  47       +------------------- 40-bytes -------------------+
  48      /                                                  \
  49     +------------------------+--------------------+------+-----------------+
  50     | metaindex block handle / index block handle / ---- | magic (8-bytes) |
  51     +------------------------+--------------------+------+-----------------+
  52
  53     The magic are first 64-bit of SHA-1 sum of "http://code.google.com/p/leveldb/".
  54
  55 NOTE: All fixed-length integer are little-endian.
  56 */
  57
  58 /*
  59 Block:
  60
  61 Block is consist of one or more key/value entries and a block trailer.
  62 Block entry shares key prefix with its preceding key until a restart
  63 point reached. A block should contains at least one restart point.
  64 First restart point are always zero.
  65
  66 Block data structure:
  67
  68       + restart point                 + restart point (depends on restart interval)
  69      /                               /
  70     +---------------+---------------+---------------+---------------+---------+
  71     | block entry 1 | block entry 2 |      ...      | block entry n | trailer |
  72     +---------------+---------------+---------------+---------------+---------+
  73
  74 Key/value entry:
  75
  76               +---- key len ----+
  77              /                   \
  78     +-------+---------+-----------+---------+--------------------+--------------+----------------+
  79     | shared (varint) | not shared (varint) | value len (varint) | key (varlen) | value (varlen) |
  80     +-----------------+---------------------+--------------------+--------------+----------------+
  81
  82     Block entry shares key prefix with its preceding key:
  83     Conditions:
  84         restart_interval=2
  85         entry one  : key=deck,value=v1
  86         entry two  : key=dock,value=v2
  87         entry three: key=duck,value=v3
  88     The entries will be encoded as follow:
  89
  90       + restart point (offset=0)                                                 + restart point (offset=16)
  91      /                                                                          /
  92     +-----+-----+-----+----------+--------+-----+-----+-----+---------+--------+-----+-----+-----+----------+--------+
  93     |  0  |  4  |  2  |  "deck"  |  "v1"  |  1  |  3  |  2  |  "ock"  |  "v2"  |  0  |  4  |  2  |  "duck"  |  "v3"  |
  94     +-----+-----+-----+----------+--------+-----+-----+-----+---------+--------+-----+-----+-----+----------+--------+
  95      \                                   / \                                  / \                                   /
  96       +----------- entry one -----------+   +----------- entry two ----------+   +---------- entry three ----------+
  97
  98     The block trailer will contains two restart points:
  99
 100     +------------+-----------+--------+
 101     |     0      |    16     |   2    |
 102     +------------+-----------+---+----+
 103      \                      /     \
 104       +-- restart points --+       + restart points length
 105
 106 Block trailer:
 107
 108       +-- 4-bytes --+
 109      /               \
 110     +-----------------+-----------------+-----------------+------------------------------+
 111     | restart point 1 |       ....      | restart point n | restart points len (4-bytes) |
 112     +-----------------+-----------------+-----------------+------------------------------+
 113
 114
 115 NOTE: All fixed-length integer are little-endian.
 116 */
 117
 118 /*
 119 Filter block:
 120
 121 Filter block consist of one or more filter data and a filter block trailer.
 122 The trailer contains filter data offsets, a trailer offset and a 1-byte base Lg.
 123
 124 Filter block data structure:
 125
 126       + offset 1      + offset 2      + offset n      + trailer offset
 127      /               /               /               /
 128     +---------------+---------------+---------------+---------+
 129     | filter data 1 |      ...      | filter data n | trailer |
 130     +---------------+---------------+---------------+---------+
 131
 132 Filter block trailer:
 133
 134       +- 4-bytes -+
 135      /             \
 136     +---------------+---------------+---------------+-------------------------------+------------------+
 137     | data 1 offset |      ....     | data n offset | data-offsets offset (4-bytes) | base Lg (1-byte) |
 138     +-------------- +---------------+---------------+-------------------------------+------------------+
 139
 140
 141 NOTE: All fixed-length integer are little-endian.
 142 */
 143
 144 const (
 145         blockTrailerLen = 5
 146         footerLen       = 48
 147
 148         magic = "\x57\xfb\x80\x8b\x24\x75\x47\xdb"
 149
 150         // The block type gives the per-block compression format.
 151         // These constants are part of the file format and should not be changed.
 152         blockTypeNoCompression     = 0
 153         blockTypeSnappyCompression = 1
 154
 155         // Generate new filter every 2KB of data
 156         filterBaseLg = 11
 157         filterBase   = 1 << filterBaseLg
 158 )
 159
 160 type blockHandle struct {
 161         offset, length uint64
 162 }
 163
 164 func decodeBlockHandle(src []byte) (blockHandle, int) {
 165         offset, n := binary.Uvarint(src)
 166         length, m := binary.Uvarint(src[n:])
 167         if n == 0 || m == 0 {
 168                 return blockHandle{}, 0
 169         }
 170         return blockHandle{offset, length}, n + m
 171 }
 172
 173 func encodeBlockHandle(dst []byte, b blockHandle) int {
 174         n := binary.PutUvarint(dst, b.offset)
 175         m := binary.PutUvarint(dst[n:], b.length)
 176         return n + m
 177 }