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 156 type blockHandle struct { 157 offset, length uint64 158 } 159 160 func decodeBlockHandle(src []byte) (blockHandle, int) { 161 offset, n := binary.Uvarint(src) 162 length, m := binary.Uvarint(src[n:]) 163 if n == 0 || m == 0 { 164 return blockHandle{}, 0 165 } 166 return blockHandle{offset, length}, n + m 167 } 168 169 func encodeBlockHandle(dst []byte, b blockHandle) int { 170 n := binary.PutUvarint(dst, b.offset) 171 m := binary.PutUvarint(dst[n:], b.length) 172 return n + m 173 } 174