Zenn
🦔

Data Encoding Format と Scheme

2023/10/22に公開
datastructure
tech

データエンコードフォーマット

  • データフォーマットやスキーマが変更されると、しばしばアプリケーションも変更が必要になる
  • 多くの場合デプロイは以下のように実施される
    • サーバーサイドの場合: ローリングアップグレード:
      サービスのダウンタイムなしで新規Versionをデプロイできる
      1. 新しいVersionのデプロイを数nodeずつ実施
      2. 新しいVersionが正常に動作しているかをチェックしながら全てのnodeに対して反映する
    • クライアントサイドの場合: しばらくの間ユーザーはアップデートをインストールしてくれない可能性がある

新旧Versionのコードと新旧データフォーマットがシステム内で共存する可能性があるため、システム側は互換性をどちらに対しても担保する必要がある

  • 後方互換性
    • 古いコードによって書かれたデータを新しいコードが読めること
  • 前方互換性
    • 新しいコードによって書かれたデータを古いコードが読めること

-> 新旧データをサポートするためにも、データフォーマットの特性を理解して適切な変更をかけていくことが求められる

言語固有フォーマット

多くの場合、各種言語ではメモリオブジェクトをバイトの並びにエンコードする機能があるため、少ないコード量でインメモリのオブジェクトの保存とリストアが可能

  • Java: java.io.Serializable
  • Ruby: Marshal
  • Python: pickle

言語固有フォーマットの問題点

  • 言語に依存しており、他言語での読み込みが困難
    • 他言語で作られたアプリとの結合が困難になるため
  • 言語固有のデコーディングライブラリは、受け取ったデータに基づいて任意のクラスのインスタンスを作成するため、セキュリティのリスクになり得る
    • 攻撃者が特定のクラスのインスタンスを作成することで、そのクラスの副作用を利用して任意のコードをリモート実行できる
  • PCリソースを無駄遣いする傾向にある
    • パフォーマンス: Encode/DecodeにかかるCPU時間
    • サイズ効率の悪いエンコーディング: Encode後のデータ量

JSON, XML, CSV, etc

Human Readableなデータフォーマット(=Unicode文字列)ではあるが、いくつかの問題点が指摘されている

  • 数値のEncodingに関して曖昧さがある
    • XML,CSV では数値 or 文字列なのかが明確でない
    • JSON では明確に定義されているが以下の点において曖昧さが残る
      • 整数値なのか?
      • 浮動小数点数値なのか?
  • バイナリ文字列（文字列のEncodingがなされていないByteの並び）をサポートしていない
    • Base64を使ってバイナリデータをEncodeする回避策は多く利用されている
    • しかし、Base64でEncodeしたデータはデータ量が33%増加してしまう
  • XML,JSON では、それぞれのフォーマットとは別に利用できるスキーマがあるが、XML/JSONスキーマを使わないアプリケーションは適切な Encoding/Decoding をHard Codingする必要がある
    • スキーマについて
      • データ型: 各フィールドや要素が持つべきデータ型（例：文字列、数値、真偽値など）を定義
      • 必須フィールド: あるフィールドや要素が必須であるか、オプションであるかを指定
      • 制約: データの値に対する制約を定義 ex: 最大長/最大値/最小値
      • 構造: 複合的なオブジェクトやリストの内部構造を定義
      • Default値
      • ...etc
  • CSVにはスキーマがないため、それぞれの列や行の意味の定義はアプリケーションが担わないといけない

上記のような問題点はあるが、JSON,XML,CSVは多くの目的を十分に満たすことはできる

Binary Encoding

  • 組織内で利用されるデータの場合、最小公倍数のような Encoding Format を使わなければならないといった圧力は弱くなる
  • datasetが小さければ利点を無視できるが、テラバイト級のデータ量を扱う場合、データフォーマットの選択の影響は非常に大きくなる

上記のように大きなdatasetを扱うようなケースで利用されるのが、Binary Encodingになる

  • JSON: MessagePack, BSON, BJSON, UBJSON, BISON, Smile
  • XML: WBXML, Fast Infoset

Sample: Message Pack

以下に Json データを Message Pack で Encode した例を記載する

  • Json Case(空白を除くと 81bytes)
{
    "userName": "Martin",
    "favoriteNumber": 1337,
    "interests": ["daydreaming", "hacking"]
}

  • データ量としては、66bytes になり僅かに短くなる

    • この程度の僅かな領域の削減(parseを高速化)のために、あえあて人間が読めないフォーマットにするメリットがあるかは不明

  • Message Pack

    1. 先頭の 0x83 について
      1. 0x80 は、後続のbyte配列が obejct byte配列であることを示す
      2. 0x03 は、3 fields 存在することを示す
      • 4bitに収まらない16以上fieldをobjectが持っている場合、先頭の識別子が代わり、field数は 2or4byte で encode される
    2. 2番目の 0xa8について
      1. 0xa0 は、文字列を示す
      2. 0x08 は、文字列の長さを示す
    3. 続く8bytesはfiled name を ASCII で表現したもの

message pack

Apache Thrift and Protocol Buffers

  • どちらも Encode するための Scheme を必要とする

以下に、Protocol Buffersのデータ構造を記載する

message Person {
    required string user_name      = 1;
    optional int64 favorite_number = 2;
    repeated string interests      = 3;
}

protocol buffer

Protocol Buffers(protobuf)は、数値を効率的に encode すために Varint Encodingを利用

  1. 1337 をバイナリで表現すると、10100111001となる
  2. 7ビットのグループに分割
    1. 必要に応じて最初のグループに0を追加して7ビットにする(0を使い化すると-> 0001010 0111001)
      1. 最初の7ビット: 0111001
      2. 次の7ビット: 0001010
  3. 各7ビットのグループの先頭に"続きビット(1=続きあり,0=続きなし)"を追加
    1. 0111001 の前に続きビットを追加: 10111001
    2. 0001010 の前に続きビットを追加: 00001010
  4. 16進数に変換
    1. バイナリ表現 10111001 00001010 を16進数に変換すると、B9 0A となる

required,optional が指定されているが、これはフィールドのエンコードには影響しない

field tag と scheme Evolution

field tagの追加・削除について

  • 新しい field tag 番号を加えることで、新規のfieldを追加することが可能
    • 古いコードが新しいコードによって書かれたデータを読み取ろうとした場合、古いコードは認識できないタグtag番号を持つ新規fieldを無視する
  • 前方互換性について
    • データ型のアノテーションを見れば、parserはskipするbyte数を判断できる -> それによって、新しいコードによって書かれたデータを古いコードが読めるため前方互換性が担保される
  • 後方互換性について
    • それぞれのfieldがuniqueなtag番号を持ってさえいれば、tag番号の意味が変わることはないため、新しいコードは常に古いデータを読み込むことが可能
      • 注意点
        • 新規で追加するfieldは必ずoptionalになる(requiredにはできない)
        • 削除については、追加時と同様optionalのfieldのみ削除可能であり、必須fieldは削除できない

field tagのデータ型変更について

  • 型変更できる場合はあるが、値の精度が低くなったり、切り捨てられてしまうリスクがある
    • 例えば、32bit整数 -> 64bit整数に変更した場合
      • 古いコードは32bit長の変数に格納することになる.デコードされた64bit長の値が32bit長に収まらなかったら、その値は切り詰められる

Apache Avro

  • Binary Encoding Formatの一つ
  • Avroには2つのschemeが存在する
    • Avro IDL: 人間が編集することを意図したもの
    • JSON base: 機械が読み取りやすいもの

Avro IDL

record Person {
  string userName;
  union { null, long } favoriteNumber = null;
  array<string> interests;
}

Json base

{
  "type": "record",
  "name": "Person",
  "fields": {
    {"name": "userName", "type": "string"},
    {"name": "favoriteNumber", "type": ["null", "long"], "default": null},
    {"name": "userName", "type": {"type": "array", "items": "string"}}
  }
}
  • Avroにはtag番号がないため、このスキーマを使って上記をencodeすると、Avroのbinary encodingでは、32bytesになる.
  • byte arrayをみるとfieldやfield data型を示すものがないことがわかる
    • Encodingに含まれているのは、連結された値のみ
    • 文字列は単に長さのprefixに続いてUTF-8のbyteが続いているのみ(そのencodeさられたデータが文字列であるかは示していない)
    • 整数のEncodingには可変長のVarintEncodingが利用されている

avro

通常Binary DataをParseするには、Scheme中に現れる順序に従ってfieldを見ていき、schemeを使ってそれぞれのfieldのdata型を判断する必要があった.つまり、データの読み書きで利用されるschemeが完全に同じschemeを使わなければならなかった.

  • Writer Scheme: データをencodeする際に利用されるscheme
  • Reader Scheme: データをdecodeする際に利用されるscheme

Avroでは、Writer Scheme/Reader Schemeが完全に同一である必要がない.

  • 例
    • Writer Scheme/Reader Schemeの間でfieldの順序が異なっていても問題ない
      • Scheme解決の際にfield同士を名前でマッチさせるため
    • Writer Schemeには存在するが、Reader Schemeに存在しないfieldについては無視される
    • Reader Schemeが期待するfieldが、Writer Schemeに存在しない場合、Reader Schemeで定義されているdefault valueが適用される

互換性について

  • Avroにおける前方互換性: 新しいVersionのschemeをWriterとして持ち、古いVersionのschemeをReaderとして持てる
  • Avroにおける後方互換性: 新しいVersionのschemeをReaderとして持ち、古いVersionのschemeをWriterとして持てる

上記の特性上、互換性を保つためには、fieldを追加/削除できるのはdefault valueを持っているfieldのみ

Avroでは、default valueには単純にnullを設定することはできず、nullにしたい場合はunion型を利用して、以下のようにunionにnullが選択肢として入っている場合のみnullを設定することができる

union { null, long, string } field;
  • field名を変更しても後方互換性は保たれるが、前方互換性は保たれない
  • union型の選択肢を追加しても後方互換性は保たれるが、前方互換性は損なわれる

Avroの使われ方について

そもそも、どのようにWriter Schemeを知ることができるのか?

  • 大量レコードを持つ大きなファイルの場合
    • この場合ファイルの先頭に1度だけWriter Schemeを含めて置くだけで利用可能になる
  • 個別にレコードが書かれるDatabaseの場合
    • SchemeのVersionのリストをDatabase中に保存して置き、databaseからversion番号に応じたWriter Schemeをfetchすることができる
  • Network経由でレコードを送信する場合
    • Avro RPCプロトコルを利用して解決する

Thrift/ProtocolBuffers and Avro Comparison

  • Avro
    • 動的に生成されたSchemeと相性が良い(RDBMS)
      • 例えば、RDBの内容をファイルにdumpしたものなど
        • Avroを使えば、RDBのschemeをAvroのschemeを容易に生成でき、そのschemeを利用してdatabaseの内容をencodeし、全ての内容をavroオブジェクトコンテナファイルにdumpする
        • それぞれのdatabase tableに対してrecordのschemeを生成すれば、それぞれの列はレコードのfieldになる(databaseの列名はAvroのfield名にmapされる)
        • databaseのschemeが変更された場合、更新されたdatabase schemeから新しいAvroのschemeを生成し、そのschemeでデータをexportすることが可能
    • 動的型付け言語との相性
      • 静的型付き言語のためにコード生成することもできるが、コード生成を全くしなくても利用可能
  • Thrift/ProtocolBuffers
    • scheme変更のtag番号の割り当ては手作業になり、database schemeの列名に合わせてfield tagへのmappingが必要になるため非常に複雑な作業が求められる
    • scheme定義後のコード生成に依存する(安全性を担保することができるので悪いことではない)

Schemeメリット

  • 様々なバイナリJSONよりも遥かにコンパクトになること(encoded dataにfield情報を付与する必要がないため)
  • スキーマはドキュメンテーションの形態の1つとしての価値がある
    • decodeにはschemeが必要になることから、常に最新の状態になっていることが保証される
  • schemeのdatabaseを管理することで、schemeの変更の前方および後方互換性をデプロイに先立ってチェック可能
  • 静的型付き言語のユーザーにとっては、コンパイル時の型チェックができるようになるから、schemeからのコード生成は有益

データフローの形態

データフローの形態を学習することにより、どの主体がデータをEncodeして、どの主体がdataをDecodeするのかをユースケースごとに整理する

Database経由での Data Flow

  • DatabaseのEncode&Decodeする主体はDatabaseのプロセスになる
    • 書き込みを行うcodeがEncodeする
    • 読み込みを行うcodeがDecodeする
  • 互換性について
    • 後方互換性は必須になる
      • 新しいコードで古いコードで書かれたデータがdecodeできない場合アプリケーションは落ちるため
    • 前方互換性の担保は頻繁に求められる(必須ではない)
      • Databaseは、複数のプロセスが同じデータに対して同時に読み書きすることがよくある
        • Databaseの利用側であるアプリケーションについては、Rolling Upgradeのデプロイ手法をすることが一般的なため、未更新のインスタンスと更新済みのインスタンスが混在することになる
        • そのため、新しいコードで書かれたdatabaseの値が、古いコードで読み込めることを担保することを求められることが頻繁に発生する

-> databaseの下位のストレージに過去の様々なVersionによるschemeでencodeされたデータがあったとしても、単一SchemeでEncodeされたデータかのように扱うことが可能

サービス経由での Data Flow

  • Server-sideがResponseをEncode
  • Client-sideがResponseをDecode

サービスAPIのVersion間で互換性を保たないといけない

RPCについて

  • Webサービスに関して広く使われるアプローチは、RESTやSOAPがある
  • WebサービスはNetwork越しにAPIリクエストを発行する技術

それらの技術は、1970年代から存在する RPC(Remote Procedure Call) の概念に基づいている.
RPCモデルは、リモートにあるネットワークサービスをローカルの関数呼び出しと同じように見せようとする.
しかし、Network経由の呼び出しは、Localの呼び出しとは異なり、以下のような問題点も存在する.

  • Local呼び出しは予測が可能であり、パラメータのみに依存して成功失敗が決まる
  • 失敗したNetwork Requestをリトライした場合、1つ目のRequestが実際には到達していて、Responseだけが失われていたケースなどがある(idempotenceを構築する必要がある)
  • Client/Server間で異なるプログラミング言語で実装されているかもしれないため、RPCのFrameworkは1つの言語から他の言語に変換が必要になる可能性がある

上記の問題を解決するために、様々なFrameworkが開発されてきた

  • Thrift,gRPC(Protocol Buffers), Avro RPCは、それぞれのEncoding Fomratの互換性のルールに従って変更可能
  • SOAPでは、Request/ResponseはXMLスキーマと合わせて指定される
  • RESTful APIでは、ResponseにJSON(without scheme)を、RequestにはJSONあるいは、URLエンコード/formエンコードされたRequest Parameterを使うことが一般的
    • optionのRequest Parameterの追加やResponse Objectへの新しいfieldの追加は互換性を保つ変更だと考えられる

Meesage Passing Data Flow

  • Encodeする主体は、messageを送信するproducer側の処理
  • Decodeする主体は、messageを受け取るconsumer側の処理

直接のRPCと比較して、以下のような利点がある

  • Consumer側が動作していない場合でも、MessageBrokerがBufferとして働くためシステムの信頼性が向上
  • MessageBrokerはConsumer側がクラッシュした時などに、messageを再配信できるためmessageが失われることを防ぐ
  • MessageBrokerを中継先にすることにより、複数のConsumerにmessageを配信できる
  • MessageBrokerによってProducer/Consumerが論理的に分離される

Meesage Passing Data Flow: 互換性について

  • 前方互換性
    • Producerが動いている限り、Brokerは常にmessageを受け付け続ける
    • Rollout Upgradeでデプロイする場合、未更新のインスタンスも動き続けるため、古いVersionで書かれたmessageについても、新しいVersionのコードで読み込めるようにしておく必要がある
  • 後方互換性
    • こちらについても、インスタンスが新旧混在するため、サポートが求められる

Discussion