Skip to content

Storage Format

Jump to bottom
Yuya Uezato edited this page Apr 8, 2019 · 6 revisions

ストレージフォーマット (Version: 1.1)

CannyLS内でlump群を永続化する際に使用されているフォーマット。
"LUmp Storage Format"を略して"lusf"と呼称される。
また、このフォーマットのデータを保持するファイルには、".lusf"という拡張子を付与することが推奨されている。

(0) 共通

  • 整数値のバイト順は、全てビッグエンディアン

(1) 全体構造

ストレージは以下の三つの隣接する領域から構成される:

  1. ヘッダ領域
  2. ジャーナル領域
  3. データ領域

それぞれの領域は、ストレージのヘッダで指定されているブロック境界にアライメントされている。

(2) ヘッダ領域

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Magic Number                          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |        Header Size            |      Major Version            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |        Minor Version          |      Block Size               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      |                     Instance UUID (128 bit)                   |
      |                                                               |
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                     Journal Region Size (64 bit)              |
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                     Data Region Size (64 bit)                 |
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                     Padding (Variable)
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  • Magic Number:
    • "lusf"に固定
    • "lusf"は「LUmp Storage Format」の略
  • Header Size:
    • この後に続くヘッダ部のサイズ
    • 末尾のパディングはサイズには含まれない
  • Major Version:
    • メジャーバージョン番号
    • 現在の値は1
    • このバージョンが異なるフォーマットのストレージは認識できない(互換性をサポートしない)
  • Minor Version:
    • マイナーバージョン番号
    • 現在の値は0
    • 後方互換性が維持される変更の場合には、この値がインクリメントされる
  • Block Size:
    • ストレージのブロックのサイズ
  • Instance UUID:
    • 特定のストレージインスタンスを識別するためのID
  • Journal Region Size:
    • ジャーナル領域のサイズ
  • Data Region Size:
    • データ領域のサイズ
  • Padding:
    • ヘッダ領域の終端位置をブロック境界に合わせるためのパディングバイト列

(3) ジャーナル領域

ジャーナル領域は、以下の二つから構成される:

  1. ヘッダ部
  2. レコード部

より正確には、ジャーナル領域全体は、ヘッダ部の直後からレコード部が続く形になっている。

(3-1) ジャーナル領域: ヘッダ部

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Head Position (64 bit)                |
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Padding (Variable)
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  • Head Position:
    • レコード部中で、先頭ジャーナルレコードの存在する位置
    • なおここでの"位置"は、レコード部における相対位置であり、ジャーナル領域における相対位置ではないことに注意
  • Padding:
    • ヘッダ部の終端をブロック境界に合わせるためのパディング

(3-2) ジャーナル領域: レコード部

レコード部はリングバッファ形式になっており、 その中には以下のレコード列が連続して配置されている:

  1. END_OF_RECORDSレコード (tag=0)
  2. GO_TO_FRONTレコード (tag=1)
  3. PUTレコード (tag=3)
  4. EMBEDレコード (tag=4)
  5. DELETEレコード (tag=5)
  6. DELETE_RANGEレコード (tag=6)

※ 歴史的な理由によりtag=2は欠番

(3-2-1) END_OF_RECORDSレコード

レコード列の終端を示すためのレコード。

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Checksum                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Tag (0)   |
      +-+-+-+-+-+-+-+-+
  • Checksum:
    • レコードのAdler32チェックサム
  • Tag:
    • END_OF_RECORDSレコードであることを示すためのタグ
    • 値は0に固定

(3-2-2) GO_TO_FRONTレコード

リングバッファの終端に到達したことを示すためのレコード。

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Checksum                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Tag (1)   |
      +-+-+-+-+-+-+-+-+
  • Checksum:
    • レコードのAdler32チェックサム
  • Tag:
    • GO_TO_FRONTレコードであることを示すためのタグ
    • 値は1に固定

(3-2-3) PUTレコード

lumpの保存(PUT)が行われたことを記録するためのレコード。

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                           Checksum                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Tag (3)    |                                               |
+-+-+-+-+-+-+-+-+                                               +
|                                                               |
+                                                               +
|                                                               |
+                                                               +
|                            Lump Id                            |
+               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|               |          Data Length          |               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+               +
|                          Data Offset                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  • Checksum (32bit):
    • レコードのAdler32チェックサム
  • Tag (8bit):
    • PUTレコードであることを示すためのタグ
    • 値は3に固定
  • Lump Id (128bit):
    • PUTされたlumpのID
  • Data Length (16bit):
    • lumpデータの長さ
    • ただし、単位は"バイト"ではなく、"ブロック"であることに注意
  • Data Offset (40bit):
    • lumpデータの格納位置を示すデータ領域内のオフセット
    • こちらもブロック単位

(3-2-4) EMBEDレコード

lumpのジャーナル領域への保存が行われたことを記録するためのレコード。

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Checksum                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Tag (4)   |                                               |
      +-+-+-+-+-+-+-+-+                                               |
      |                                                               |
      |                         Lump Id (128 bit)                     |
      |                                                               |
      |               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |               |         Data Length(16 bit)   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Data (Variable)
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  • Checksum:
    • レコードのAdler32チェックサム
  • Tag:
    • EMBEDレコードであることを示すためのタグ
    • 値は4に固定
  • Lump Id:
    • PUTされたlumpのID
  • Data Length:
    • 後ろに続くlumpデータの長さ(バイト単位)
  • Data:
    • lumpデータ

(3-2-5) DELETEレコード

lumpの削除が行われたことを記録するためのレコード。

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Checksum                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Tag (5)   |                                               |
      +-+-+-+-+-+-+-+-+                                               |
      |                                                               |
      |                         Lump Id (128 bit)                     |
      |                                                               |
      |               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |               |
      +-+-+-+-+-+-+-+-+
  • Checksum:
    • レコードのAdler32チェックサム
  • Tag:
    • DELETEレコードであることを示すためのタグ
    • 値は5に固定
  • Lump Id:
    • 削除されたlumpのID

(3-2-6) DELETE_RANGEレコード

lumpの範囲削除が行われたことを記録するためのレコード。

 0                   1                   2                   3  
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            Checksum                           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     Tag(6)    |                                               |
+-+-+-+-+-+-+-+-+                                               +
|                                                               |
+                                                               +
|                                                               |
+                                                               +
|                    Lump Id [Start] (128bit)                   |
+               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|               |                                               |
+-+-+-+-+-+-+-+-+                                               +
|                                                               |
+                                                               +
|                                                               |
+                                                               +
|                     Lump Id [End] (128bit)                    |
+               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|               |
+-+-+-+-+-+-+-+-+
  • Checksum:
    • レコードのAdler32チェックサム
  • Tag:
    • DELETE_RANGEレコードであることを示すためのタグ
    • 値は6に固定
  • Lump Id [Start], Lump Id [End]:
    • 範囲を構成する二つのlumpのID
    • [Start]以上 [End]未満 を満たすIDを有するlumpが削除されたことを意味する

(4) データ領域

以下の形式のlumpのデータ群が格納されている。

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Lump Data (Variable)
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Padding (Variable)
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |         Padding size          |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  • Lump Data:
    • lumpのデータ
  • Padding:
    • lumpデータをブロック境界に合わせるためのパディング
  • Padding size:
    • パディング部のバイトサイズ

各lumpデータの格納部分領域の開始と終端は、ブロック境界に即している必要がある。 個々のlumpデータを具体的にデータ領域のどこに割り当てるかは、アロケータの実装次第 (i.e., 先頭から順番に隙間なく埋められる保証はない)。

Contents:

Clone this wiki locally