さくらのクラウドシェルにデータを持ち込む

# 背景

[さくらのクラウドシェル](https://www.sakura.ad.jp/services/cloudshell/)では、Webブラウザ上でLinuxのシェルを操作することができる。

ただし、執筆時点ではファイルのインポートやエクスポートの機能は無いようである。
ファイル (数十KiB程度まで) の取り出し (エクスポート)は、`base64` コマンドでBase64エンコードしてコピペすることで可能である。
しかし、ファイルの持ち込み (インポート) をしようとしても、貼り付けるデータが長い (数KiB程度～) と高確率でデータが欠損してしまい、うまく持ち込みができなかったり、データが欠損した箇所を探して修復する手間がかかったりしてしまう。

そこで、データに冗長性を付加し、データの貼り付け時に発生する欠損を乗り越えてデータを持ち込む方法を開発することにした。

# 成果物

さくらのクラウドシェルにデータを持ち込むために冗長性を付加するツールを作成した。
データをさくらのクラウドシェル側でデコードする方法も掲載している。

[データ欠損を突破してクラウドシェルにデータを持ち込むやつ](https://mikecat.github.io/encoder4cs/)

# 開発

## データ欠損の観察

まず、データの貼り付け時のデータ欠損がどのような感じで発生しているのかを調べた。

### テストパターンの定性的観察

データ欠損の様子を調べるため、以下のプログラムを用いてテストパターンを生成した。

```perl:tpgen.pl
#!/usr/bin/perl

use strict;
use warnings;

my $width = @ARGV > 0 ? int($ARGV[0]) : 10;

for (my $i = 1; $i <= 1000; $i++) {
	for (my $j = 0; $j < $width; $j++) {
		printf "%05d-%d|", $i, $j;
	}
	print "\n";
}
```

以下のようなテストパターンを生成した。
行番号と行内の位置がわかるようになっている。

```text
00001-0|00001-1|00001-2|00001-3|00001-4|00001-5|00001-6|00001-7|00001-8|00001-9|
00002-0|00002-1|00002-2|00002-3|00002-4|00002-5|00002-6|00002-7|00002-8|00002-9|
00003-0|00003-1|00003-2|00003-3|00003-4|00003-5|00003-6|00003-7|00003-8|00003-9|
00004-0|00004-1|00004-2|00004-3|00004-4|00004-5|00004-6|00004-7|00004-8|00004-9|
00005-0|00005-1|00005-2|00005-3|00005-4|00005-5|00005-6|00005-7|00005-8|00005-9|
(中略)
00996-0|00996-1|00996-2|00996-3|00996-4|00996-5|00996-6|00996-7|00996-8|00996-9|
00997-0|00997-1|00997-2|00997-3|00997-4|00997-5|00997-6|00997-7|00997-8|00997-9|
00998-0|00998-1|00998-2|00998-3|00998-4|00998-5|00998-6|00998-7|00998-8|00998-9|
00999-0|00999-1|00999-2|00999-3|00999-4|00999-5|00999-6|00999-7|00999-8|00999-9|
01000-0|01000-1|01000-2|01000-3|01000-4|01000-5|01000-6|01000-7|01000-8|01000-9|
```

さくらのクラウドシェルで `cat > a.txt` のような `cat` コマンドにより入力内容をファイルに保存するコマンドを実行し、このテストパターンを貼り付けると、データ欠損が発生した。
データ欠損は、

```text
00011-0|00011-1|00011-2|00011-3|00011-4|00011-5|00011-6|00011-7|00011-8|00011-9|
00012-0|00012-1|00012-2|00012-3|00012-4|00012-5|00012-6|00012-7|00012-8|00012-9|
00013-0|00013-1|00013-6|00013-7|00013-8|00013-9|
00014-0|00014-1|00014-2|00014-3|00014-4|00014-5|00014-6|00014-7|00014-8|00014-9|
00015-0|00015-1|00015-2|00015-3|00015-4|00015-5|00015-6|00015-7|00015-8|00015-9|
```

のように1行の一部が欠けることもあれば、

```text
00023-0|00023-1|00023-2|00023-3|00023-4|00023-5|00023-6|00023-7|00023-8|00023-9|
00024-0|00024-1|00024-2|00024-3|00024-4|00024-5|00024-6|00024-7|00024-8|00024-9|
00025-0|00025-1|00025-2|00025-3||00026-2|00026-3|00026-4|00026-5|00026-6|00026-7|00026-8|00026-9|
00027-0|00027-1|00027-2|00027-3|00027-4|00027-5|00027-6|00027-7|00027-8|00027-9|
00028-0|00028-1|00028-2|00028-3|00028-4|00028-5|00028-6|00028-7|00028-8|00028-9|
```

のように複数の行にまたがって欠けることもあった。
さらに、このコマンド実行と貼り付けの実験を数回行うと、データ欠損が発生する場所は毎回変わった。

### テストパターンの定量的調査

以下のプログラムを用い、データ欠損が起きたテストパターンで具体的にどのような欠損が起きているかを調べた。

```perl:tpcheck.pl
#!/usr/bin/perl

use strict;
use warnings;

my $width = @ARGV > 0 ? int($ARGV[0]) : 10;

my $next = 1;
my $final = 1000;

my $ok = 0;
my $currentStreak = 0;
my $minStreak = $final - $next + 1;
my $maxStreak = 0;
my $maxGap = 0;

sub createExpected {
	my $id = $_[0];
	my $expected = "";
	for (my $i = 0; $i < $width; $i++) {
		$expected .= sprintf("%05d-%d|", $id, $i);
	}
	return $expected;
}

while (my $line = <STDIN>) {
	chomp($line);
	my $lineok = 0;
	if ($line =~ /^([0-9]+)-/) {
		my $id = int($1);
		if ($line eq &createExpected($id)) {
			if ($id > $next) {
				my $gap = $id - $next;
				if ($gap > $maxGap) { $maxGap = $gap; }
				$next = $id;
			}
			if ($id == $next) {
				$lineok = 1;
				$ok++;
				$currentStreak++;
				if ($currentStreak > $maxStreak) { $maxStreak = $currentStreak; }
				$next = $id + 1;
			}
		}
	}
	unless ($lineok) {
		if ($currentStreak > 0 && $currentStreak < $minStreak) { $minStreak = $currentStreak; }
		$currentStreak = 0;
	}
}

if ($next <= $final) {
	my $gap = $final + 1 - $next;
	if ($gap > $maxGap) { $maxGap = $gap; }
}

print "ok: $ok\n";
print "min streak: $minStreak\n";
print "max streak: $maxStreak\n";
print "max gap: $maxGap\n";
```

このプログラムは、以下の項目を調査する。

|項目|意味|
|---|---|
|ok|正常な (欠損が発生しなかった) 行の数|
|min streak|正常な行が連続した最低数|
|max streak|正常な行が連続した最高数|
|max gap|連続して欠損した行の最高数|

Firefox を用いた5回の実験で得られたデータは、以下のようになった。

|項目|実験1|実験2|実験3|実験4|実験5|
|---|--:|--:|--:|--:|--:|
|ok|897|912|919|907|913|
|min streak|9|10|10|3|10|
|max streak|21|43|27|24|33|
|max gap|3|3|3|3|2|

ここから、以下のことがわかった。

* 欠損した行から3行しかおかずにまた欠損することがある (min streak より)
* 連続して欠損する行は、3行までのことが多そうである (max gap より)

### テストパターンの行の長さを変えてみる

先ほどのテストパターン生成プログラム `tpgen.pl` は、コマンドライン引数で1行あたりのブロック数を変えることができる。
たとえば、`5` を指定すると、以下のようなテストパターンが生成される。

```text
00001-0|00001-1|00001-2|00001-3|00001-4|
00002-0|00002-1|00002-2|00002-3|00002-4|
00003-0|00003-1|00003-2|00003-3|00003-4|
00004-0|00004-1|00004-2|00004-3|00004-4|
00005-0|00005-1|00005-2|00005-3|00005-4|
(中略)
00996-0|00996-1|00996-2|00996-3|00996-4|
00997-0|00997-1|00997-2|00997-3|00997-4|
00998-0|00998-1|00998-2|00998-3|00998-4|
00999-0|00999-1|00999-2|00999-3|00999-4|
01000-0|01000-1|01000-2|01000-3|01000-4|
```

これを用いて先ほどと同様の実験をしたところ、以下の結果が得られた。
なお、定量的評価を行う際は、`tpcheck.pl` でも `tpgen.pl` と同様にコマンドライン引数でテストパターンの1行のブロック数を指定した。

|項目|実験1|実験2|実験3|実験4|実験5|
|---|--:|--:|--:|--:|--:|
|ok|938|937|921|945|941|
|min streak|21|22|7|22|22|
|max streak|54|60|42|67|48|
|max gap|4|3|7|3|3|

テストパターンの行の長さを半分にしたところ、連続した正常な行の数の最小値 (min streak) は2倍程度になり、連続した欠損した行の数の最大値 (max gap) も2倍前後になっている。
このことから、データの欠損のしかたには「行数」よりも「データの長さ」のほうが関係しそうであることが読み取れる。

### 通信の観察

Webブラウザの開発者ツールで、さくらのクラウドシェルの通信を観察してみた。
すると、以下のことがわかった。

* 端末が送受信するデータは、WebSocketでやり取りされる
* 貼り付けたデータは、最大256バイトのメッセージに分割されて送信される
  * 最初にヘッダ `1` がつき、データは最大255バイトずつ送られる
* 欠損するデータは、メッセージの最後の部分 (接尾辞) のみと推測できる

たとえば、貼り付けの結果以下のデータが入力された。(抜粋)

```text:入力されたデータ
00085-0|00085-1|00085-2|00085-3|00085-4|
00086-0|00086-1|00086-2|00086-3|00086-4|
00087-0|000888-0|00088-1|00088-2|00088-3|00088-4|
00089-0|00089-1|00089-2|00089-3|00089-4|
00090-0|00090-1|00090-2|00090-3|00090-4|
```

この部分の周辺に対応するメッセージは、以下のようになっていた。

```text:送信されたメッセージ 1
181-4|
00082-0|00082-1|00082-2|00082-3|00082-4|
00083-0|00083-1|00083-2|00083-3|00083-4|
00084-0|00084-1|00084-2|00084-3|00084-4|
00085-0|00085-1|00085-2|00085-3|00085-4|
00086-0|00086-1|00086-2|00086-3|00086-4|
00087-0|00087-1|00087-2|00087-3|00087-4|
000
```

```text:送信されたメッセージ 2
188-0|00088-1|00088-2|00088-3|00088-4|
00089-0|00089-1|00089-2|00089-3|00089-4|
00090-0|00090-1|00090-2|00090-3|00090-4|
00091-0|00091-1|00091-2|00091-3|00091-4|
00092-0|00092-1|00092-2|00092-3|00092-4|
00093-0|00093-1|00093-2|00093-3|00093-4|
00094-0|0009
```

「送信されたメッセージ 1」の最後の以下の部分が欠損し、続いて「送信されたメッセージ 2」の (ヘッダの `1` を除く) 先頭から入力が再開されている。

```text:メッセージ 1のうち欠損した部分
7-1|00087-2|00087-3|00087-4|
000
```

よって、だいたい255バイトごとにデータが欠損しやすくなることがわかる。

ブロック数10のテストパターンの1行の長さは81バイト (改行文字を含む) なので、3行では243バイトとなり、255バイトに近い値となっている。
このことから、欠損の状況が「3行」とのかかわりが深くなったことの説明がつきそうである。

## 冗長性の方式の検討

一般的には、データに冗長性を付加して一部のデータが読めなくてももとのデータを復元できるようにする方法として、[ハミング符号](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E7%AC%A6%E5%8F%B7)や[リード・ソロモン符号](https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC%E3%83%89%E3%83%BB%E3%82%BD%E3%83%AD%E3%83%A2%E3%83%B3%E7%AC%A6%E5%8F%B7)などが知られている。
しかし、これらの**誤り訂正方式**は、実装が複雑になる。
これらの方式では**誤っているデータの位置が一見わからない状態から**誤りの位置を特定し、訂正を行うことができる。
しかし、今回の目的では、対処したいのはデータの「誤り」ではなく「欠損」であり、以下の性質を仮定できる。

* データが欠損しているかどうかは簡単にわかる
* 欠損していないデータは信用できる (誤っていないと仮定できる)

よって、誤り訂正方式を用いるのはオーバーキルであると考えられる。

一方、[RAID](https://ja.wikipedia.org/wiki/RAID) は、データを複数のディスクに記録し、一部のディスクが故障しても残りのディスクからデータを復元できるようにする方法である。(RAID 0 を除く)
こちらは、ディスクが故障しているかは判定できることを仮定するため、今回やりたいことに近そうである。

実験により、最悪の場合正常な3行に続いて3行が欠損する可能性があるといえる。
すなわち、最大でデータの50%程度が欠損する可能性がありそうである。

そこで、今回は、実装のコストも考慮し、「数行ごとに同じデータを2回配置する」という単純な方式を採用した。

# 決定したエンコード方法

まず、データを zlib 形式で圧縮する。
これにより、以下の効果が期待できる。

* 貼り付けるデータ量を減らし、データ欠損の影響を少しでも受けにくくする
* データの終わりがわかる
* チェックサムによりデータを検証できる

次に、圧縮したデータを適当なサイズごとに区切り、それぞれBase64エンコードする。
このBase64エンコードしたデータをさらに数行に分割する。
分割した行の列を数回繰り返し、それぞれの行にブロック内のどの位置かを表す記号を追加する。

デコード時は、この行に付けられた記号および行の長さにより、入力された行が正常かどうかを確認する。
そして、以下の動作を行う。

* 期待する正常な行であれば、現在のブロックのデータとして加える
* 正常な行だがもっと後に来るはずのものであれば、来るはずのタイミングまで保持しておく
* 欠損した不完全な行であれば、捨てる (正常な行のデータが含まれていれば、その部分は採用する)

だいたい1ブロック分以上を飛ばすような、大きな欠損には対応しない。
このような大きな欠損がある場合は、zlib 圧縮の展開時にエラーとなるだろう。
欠損のしかたによっては、ブロックの処理時に「ある部分について正常なデータが見つからない (繰り返した行がすべて欠損している)」としてエラーになる可能性もある。

今回は、以下の仕様とした。
3行で255バイト (改行文字を含む) となるようにし、4行ずつのかたまりにして欠損しやすい位置がずれるようにすることで、データが全て欠損する可能性を下げることを狙った。

|項目|仕様|
|---|---|
|分割後1行あたりの入力バイト数|60|
|ブロックを何行に分割するか|4|
|各ブロックを何回繰り返すか|2|
|行に追加する記号|ASCII文字 行の最初と最後に2文字ずつ (合計4文字)|

# 実装

## エンコーダ

```perl:encode.pl
#!/usr/bin/perl

use strict;
use warnings;

use MIME::Base64;
use Compress::Zlib;

# ブロック1個の入力バイト数
my $block_length = 60;
# ブロックを何行ずつ繰り返すか
my $block_set_num = 4;
# ブロックのセットを何回繰り返すか
my $redundant_mult = 2;

my $set_length = $block_length * $block_set_num;
my $block_length_out = int(($block_length * 4 + 2) / 3);

my ($d, $initStatus) = deflateInit();
die "deflateInit failed" unless $initStatus == Z_OK;

my $outputBuffer = "";

binmode(STDIN);
for (;;) {
	my $data = <STDIN>;
	my $end = !defined($data);
	my ($deflated, $deflateStatus) = $end ? $d->flush(Z_FINISH) : $d->deflate($data);
	die "deflate failed" unless $deflateStatus == Z_OK;
	$outputBuffer .= $deflated;
	while ($end ? length($outputBuffer) > 0 : length($outputBuffer) >= $set_length) {
		my $encoded = encode_base64(substr($outputBuffer, 0, $set_length), "");
		$outputBuffer = length($outputBuffer) <= $set_length ? "" : substr($outputBuffer, $set_length);
		$encoded .= "=" x ($block_length_out * $block_set_num - length($encoded));
		for (my $i = 0; $i < $block_set_num * $redundant_mult; $i++) {
			my $b = $i % $block_set_num;
			my $c = chr(0x21 + $i);
			my $e = substr($encoded, $block_length_out * $b, $block_length_out);
			print "$c$c$e$c$c\n";
		}
	}
	if ($end) { last; }
}
```

標準入力からエンコードするデータを読み込み、標準出力にエンコード結果を出力する。

[データ欠損を突破してクラウドシェルにデータを持ち込むやつ](https://mikecat.github.io/encoder4cs/) では、これをJavaScriptに移植したものを利用できる。

## デコーダ

```perl:decode.pl
#!/usr/bin/perl

use strict;
use warnings;

use MIME::Base64;
use Compress::Zlib;

# ブロック1個のエンコード済みバイト数 (Base64部分のみで、位置マークを含まず)
my $block_length_out = 80;
# ブロックを何行ずつ繰り返すか
my $block_set_num = 4;
# ブロックのセットを何回繰り返すか
my $redundant_mult = 2;

my @inputs = ();
for (my $i = 0; $i < $block_set_num * $redundant_mult; $i++) {
	push(@inputs, "");
}

my $input_idx = -1;
my $input_buf = "";

my ($d, $inflateInitStatus) = inflateInit();
die "inflateInit failed" unless $inflateInitStatus == Z_OK;

binmode(STDOUT);
for (;;) {
	for (my $i = 0; $i < $block_set_num * $redundant_mult; $i++) {
		if ($input_idx < 0) {
			my $line = <STDIN>;
			if (defined($line) && $line =~ /([!-(])\1(.*)\1\1/) {
				my $idx = ord($1) - 0x21;
				if (0 <= $idx && $idx < @inputs && length($2) == $block_length_out) {
					$input_idx = $idx;
					$input_buf = $2;
				}
			}
		}
		if ($input_idx == $i) {
			$inputs[$i] = $input_buf;
			$input_idx = -1;
		}
	}
	my $encoded = "";
	for (my $i = 0; $i < $block_set_num; $i++) {
		my $found = "";
		for (my $j = 0; $j < $redundant_mult; $j++) {
			if ($inputs[$i + $block_set_num * $j] ne "") {
				$found = $inputs[$i + $block_set_num * $j];
				last;
			}
		}
		die "data is broken" unless $found ne "";
		$encoded .= $found;
	}
	my ($out, $inflateStatus) = $d->inflate(decode_base64($encoded));
	die "inflate failed" unless $inflateStatus == Z_OK || $inflateStatus == Z_STREAM_END;
	print $out;
	last if $inflateStatus == Z_STREAM_END;
	for (my $i = 0; $i < @inputs; $i++) {
		$inputs[$i] = "";
	}
}
```

標準入力からエンコードされたデータを読み込み、標準出力にデコード結果を出力する。

[データ欠損を突破してクラウドシェルにデータを持ち込むやつ](https://mikecat.github.io/encoder4cs/) では、以下の手法などによりコードの長さを削減し、gzip圧縮およびBase64エンコードしたものを掲載している。

* 不要な空白や改行を削除する
* ~~インタプリタ指定~~おまじない `#!/usr/bin/perl` を削除する
* おまじない `use strict; use warnings;` を削除する
  * これにより、変数宣言を省略できるようになる
* 変数宣言 (`my`) や配列の初期化を省略する
* 変数名を1文字にする
* パラメータを固定し、マジックナンバーやコードの構造に埋め込む

コードの長さを削減したのは、デコーダのデータが貼り付け時に欠損する可能性を減らすためである。

# 今回の手法の有効性

今回開発した方法で 128KiB のランダムデータをさくらのクラウドシェルに持ち込む実験を行った。
ランダムデータなので、圧縮によるデータサイズ削減の効果は期待できず、ほぼ 128KiB 分のデータを貼り付けることになる。
エンコード結果の行数は 4376 行であった。

その結果、「data is broken」エラーが出ることもあるものの、数回リトライすることでデータをさくらのクラウドシェルに持ち込むことに成功した。
失敗した場合も、多くの場合、エラーが出た位置は入力を1000行や2000行読み込んだ後であった。

よって、今回の手法は、たとえば数KiBのソースファイルや、数十KiBの実行可能ファイルなどをさくらのクラウドシェルに持ち込むには十分実用的であると考えられる。