シェルスクリプトでsprintfのようなことをする

僕はシェルスクリプトを触ったことがほぼないのですが、C言語でいうsprintfのようなことをしたくて手間取ったのでメモです。シェルはbashです。

シェルスクリプトでprintfのようなことをするにはprintfコマンドを使って下記のようにします。

value=1
printf "aaa%03d\n" $value

今回は整形済みの結果を変数に代入したかったので、sprintfのようなものはないのかと思って探しました。結果的には、下記のようにしてprintfコマンドの結果を代入することでsprintfのようなことができました。

value=1
result=$(printf "aaa%03d" $value)

シェルスクリプトの文法を知っていれば当たり前なのでしょうが、「シェルスクリプト sprintf」などのキーワードからこの書き方を検索するのが結構大変だったので。

Objective-Cで文字列をUTF-16に変換→復元すると文字化けする

iPhoneアプリを作っているときに、文字列をUTF-16に変換してから復元すると文字化けするという困った現象にぶちあたりました。

下記のコードを実行します。

NSString *str = @"はろーわーるど";

// UTF-16のchar配列を取得
const char *chars = [str cStringUsingEncoding:NSUTF16StringEncoding];

// 得られたchar配列からNSStringを作成
NSString *str2 = [NSString stringWithCString:chars encoding:NSUTF16StringEncoding];

// 出力
NSLog(@"%@", str2);

結果は次の通りです。

漰贰ﰰ輰ﰰ謰椰

見事、文字化けしました。

原因調査 (1) - エンディアンを指定する

Objective-Cで定義されているUTF-16関連の文字コードには、他にも次のようなものが見つかりました。UTF-16に変換する際のエンディアンを指定できるようです(エンディアンとは)。

  • NSUTF16LittleEndianStringEncoding
  • NSUTF16BigEndianStringEncoding

では、NSUTF16StringEncodingの代わりにこれらを使ってみましょう。

NSString *str = @"はろーわーるど";
const char *chars = [str cStringUsingEncoding:NSUTF16LittleEndianStringEncoding];
NSString *str2 = [NSString stringWithCString:chars encoding:NSUTF16LittleEndianStringEncoding];
NSLog(@"%@", str2);

結果は次の通りです。

はろーわーるど

なんと、文字化けしませんでした。NSUTF16BigEndianStringEncodingでも同様でした。どうやらエンディアンがあやしそうです。

原因調査 (2) - NSUTF16StringEncoding時のエンディアンを調べる

では、NSUTF16StringEncodingを指定して変換した文字列を、それぞれのエンディアンを指定して復元してみましょう。

NSString *str = @"はろーわーるど";
const char *chars = [str cStringUsingEncoding:NSUTF16StringEncoding];
NSString *str2 = [NSString stringWithCString:chars encoding:NSUTF16LittleEndianStringEncoding];
NSLog(@"%@", str2);

結果は次の通りです。

はろーわーるど

どうやら、NSUTF16StringEncodingを指定してUTF-16に変換した際にはリトルエンディアンになっているようです。ビッグエンディアンとして復元すると当然ながら文字化けしました。

続いて、それぞれのエンディアンUTF-16に変換したものを、NSUTF16StringEncodingを指定して復元してみましょう。

NSString *str = @"はろーわーるど";
const char *chars = [str cStringUsingEncoding:NSUTF16LittleEndianStringEncoding];
NSString *str2 = [NSString stringWithCString:chars encoding:NSUTF16StringEncoding];
NSLog(@"%@", str2);

結果は次の通りです。

漰贰ﰰ輰ﰰ謰椰

トルエンディアンでは文字化けしました。では、ビッグエンディアンで復元してみましょう。

NSString *str = @"はろーわーるど";
const char *chars = [str cStringUsingEncoding:NSUTF16BigEndianStringEncoding];
NSString *str2 = [NSString stringWithCString:chars encoding:NSUTF16StringEncoding];
NSLog(@"%@", str2);

結果は次の通りです。

はろーわーるど

見事、元通りです。どうやらNSUTF16StringEncodingを指定してUTF-16文字列を復元した際にはビッグエンディアンと解釈されるようです。

結論

Objective-CのNSStringクラスについて、

  • cStringUsingEncodingメソッドにNSUTF16StringEncodingを指定すると、出力文字列はリトルエンディアンとなる
  • stringWithCString:encoding:メソッドにNSUTF16StringEncodingを指定すると、入力文字列はビッグエンディアンと解釈される

ようです。素晴らしい仕様ですね!

Single Property Indexを作らないとComposite Indexも作成されない?

昨日行われたappengine ja night #9で話題になった次の二つについて試してみました。

  • プロパティa、bに対してSingle Property Indexは作らずにComposite Indexだけを作った場合、a=1、b=2、c=3のようなフィルタを使えばComposite Index + ZigZag Scanを試せるんじゃないか。
  • プロパティa、bに対してSingle Property Indexは作らずにComposite Indexだけを作った場合、a=1のようなaだけを使ったフィルタは機能するか。

結果

Single Property Indexを作らなかったEntityは、Composite Indexテーブルに登録されないように見えます。下記コードの三つのQueryの結果はすべて空でした。Entity#setUnindexedPropertyメソッドを利用した場合は、Composite Indexも含めてIndexテーブルに書き込む処理が省略されているのかもしれません。

実行結果はこちら。何も出てこないのでまったく面白くないですがw

ソース

package org.koherent.appengine.ajn9;

import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

import javax.servlet.http.*;

import com.google.appengine.api.datastore.DatastoreService;
import com.google.appengine.api.datastore.DatastoreServiceFactory;
import com.google.appengine.api.datastore.Entity;
import com.google.appengine.api.datastore.Query;
import com.google.appengine.api.datastore.Query.FilterOperator;

@SuppressWarnings("serial")
public class CompositeIndexTestServlet extends HttpServlet {
	public void doGet(HttpServletRequest request, HttpServletResponse response)
			throws IOException {
		response.setContentType("text/plain");
		response.setCharacterEncoding("UTF-8");

		DatastoreService datastore = DatastoreServiceFactory
				.getDatastoreService();
		List<Entity> entities = new ArrayList<Entity>();
		Entity entity;
		Query query;
		Iterable<Entity> results;
		PrintWriter out = response.getWriter();

		//////////////////////////////////////////////////////////////
		// (0) Preparation: Puts entities
		//     (The composite index for "a" and "b" exists)
		entity = new Entity("kind", "keyName1");
		entity.setUnindexedProperty("a", 1); // propertyName = "a", value = 1
		entity.setUnindexedProperty("b", 1);
		entity.setProperty("c", 3);
		entities.add(entity);

		entity = new Entity("kind", "keyName2");
		entity.setUnindexedProperty("a", 1);
		entity.setUnindexedProperty("b", 2);
		entity.setProperty("c", 3);
		entities.add(entity);

		entity = new Entity("kind", "keyName3");
		entity.setUnindexedProperty("a", 2);
		entity.setUnindexedProperty("b", 2);
		entity.setProperty("c", 3);
		entities.add(entity);

		datastore.put(entities);

		//////////////////////////////////////////////////////////////
		// (1) Combinations of the composite index and zigzag scan

		query = new Query("kind");
		query.addFilter("a", FilterOperator.EQUAL, 1); // composite index
		query.addFilter("b", FilterOperator.EQUAL, 2); // composite index
		query.addFilter("c", FilterOperator.EQUAL, 3); // zigzag scan

		results = datastore.prepare(query).asIterable();
		for (Entity result : results) {
			out.print("(1) ");
			out.println(result.getKey().getName()); // keyName2
		}

		//////////////////////////////////////////////////////////////
		// (2) Filtering by the first property of the composite index

		query = new Query("kind").addFilter("a", FilterOperator.EQUAL, 2);

		results = datastore.prepare(query).asIterable();
		for (Entity result : results) {
			out.print("(2) ");
			out.println(result.getKey().getName()); // keyName3
		}

		//////////////////////////////////////////////////////////////
		// (3) Must use the composite index
		query = new Query("kind");
		query.addFilter("a", FilterOperator.EQUAL, 2);
		query.addFilter("b", FilterOperator.GREATER_THAN_OR_EQUAL,
				Long.MIN_VALUE);
		query.addFilter("b", FilterOperator.LESS_THAN_OR_EQUAL,
				Long.MAX_VALUE);

		results = datastore.prepare(query).asIterable();
		for (Entity result : results) {
			out.print("(3) ");
			out.println(result.getKey().getName()); // keyName3
		}
	}
}
<?xml version="1.0" encoding="utf-8"?>
<datastore-indexes>
	<datastore-index kind="kind" ancestor="false">
		<property name="a" direction="asc" />
		<property name="b" direction="asc" />
	</datastore-index>
</datastore-indexes>

補足

最初からEntity#setUnindexedPropertyメソッドを使うとそもそもComposite Indexが作成すらされなかったので、一度Entity#setPropertyメソッドを使ってComposite Indexを作成させてから上記のコードに差し替えました。

当然ですが、Entity#setPropertyを使った場合は次のような結果になりました。

(1) keyName2
(2) keyName3
(3) keyName3

App Engine上で順位・平均・中央値等を計算するライブラリを作る

先日のエントリー「Google App Engineでランキングやページングを実現する」にたくさんのブックマークをいただきありがとうございます。まさかここまで盛り上がると思っていなかったので驚いています。

前のエントリーでSkip ListではなくB-treeによる実装について書きましたが、色々と検討した結果Skip Listでライブラリを実装しようと思います。ライブラリはGoogle App Engine for Java (GAE/J) 用で、次の機能を実装したいと思います。

  • ソートキー(得点など)から順位計算
  • ソートキーから値を取得
  • 順位から値を取得
  • ソートキーで範囲検索(inclusive、exclusive設定可)
  • 順位で範囲検索(inclusive、exclusive設定可)
  • 範囲(全体も可)に対して次の項目を計算
    • 個数
    • 合計値
    • 平均値
    • 中央値
    • 最小値
    • 最大値

ディスカッション

前回のSkip Listの実装は試験的なものだったので、実用を考えると色々と検討しなければなりません。これまでに @kazunori_279さん、@kibayosさん、@itawasaさんらを中心に、どのようにSkip Listを実装すべきかについて議論してきたのでまとめておきます(きれいに切り分けられているわけではないですが一応議題別にまとめてます)。

以下、単にノードと書いた場合Skip Listのノードを指しているものとします(Datastoreのノードの場合はそのように明記します)。また、log_Mは底がMの対数関数を表すものとします。

ノードのブロック化について
  1. 1ノード1エンティティで実装すると、log_2(N)回程度のDatastoreアクセスが発生する。N=100万なら20回。Datastoreは1回1回のアクセスが遅いので辛い。Skip Listは連結リストのように順々にたどっていくので並列getもできない。
  2. B-treeのようにM分木的な実装ができればlog_M(N)にでき、M=1024程度にしておけば2〜4回程度のDatastoreアクセスで目的のノードまでたどり着ける。
  3. B-treeだとLock-freeにならないからSkip Listのノードをうまくブロック化した方がいいんじゃないか。
  4. Skip Listのノードをブロック化する場合、同一階層の横につながったノードをブロックにすることになる。
最上位階層への更新の集中について
  1. Skip Listに順位などの付加情報を加える場合、更新時に必ず最上位階層まで更新が波及する。ブロック化されていると最上位階層を表す特定のエンティティに更新が集中する。
  2. しかも、DatastoreでCAS的な動作を再現しようとすると、トランザクションでget→putとなり重い。
  3. トランザクションを使うので並列putもできない。更新対象に成り得るノードを同一のエンティティグループにするとSkip Listの大部分を同一のエンティティグループにすることになってしまう。
  4. putはスケールしなくても、getだけはスケールするというのでよいのでは?
  5. LogCounterのような仕組みで最上位階層に対する更新対象エンティティを分散して高速化できないか。
スケーリングについて
  1. Skip Listだと開始ノードが決まっているので、getでも特定エンティティ(つまり、Datastoreの特定のノード)にアクセスが集中する。スケールしないのでは?
  2. Skip Graphだと開始ノードを分散できる。でも、Skip GraphはSkip Listを多重にしたようなものなので、順位等の付加情報をつけると更新時にその「多重」分をすべて更新しなければならなくなる。
  3. 特定エンティティにアクセスが集中した場合にスケールしないのは普通のDatastoreでも同じでは?
  4. 特定のキーではなく、ランキング(大抵は一つのkind相当)へのすべてのアクセスが特定エンティティに集中するのが問題。MemcacheをかませばMemcacheの限界までは捌けるか。
不整合について
  1. 通常のSkip Listは更新中に参照しても不整合が起こらないが(追加時は下位階層から、削除時は上位階層から順番に操作すれば全体の構造としては常に正しい)、順位等の付加情報があると上位階層と下位階層で一時的な不整合が起こる(101個のデータが格納されているのに上位階層ではサイズが100だったり)。
  2. 一時的な不整合は事実上問題ないかもしれないが、30秒ルール等で処理が打ち切られた場合は問題になる。
イテレーションについて
  1. ブロック化されたノードの結合が起こった場合、イテレーション時にブロックが消失してしまい途中からたどれなくなる可能性がある(イテレーション中のブロック内の更新は無視で良い?)。
  2. 削除は物理削除ではなく論理削除にして、cronでVACUUM的な処理で不要なエンティティを削除するという方法で対処できないか。
ブロックの分割・結合について
  1. ノードをブロック化した場合、ノードを分割したり結合したりする際に同時に上位階層のポインタの付け替えが必要になるが、これをアトミックに行うことができない。
  2. ノードをたどっている途中でこれが起こると、下位階層に進んだときに、そのブロックの中に対象のノードが存在しないケースが起こりうる。
  3. 存在しない場合は、次のブロックをたどるなどで対処できる?結合・分割の手順とからめて要検討(必ず左と結合とか)。

今後の議論についてはTwitter上の#gae_rankerで行いたいと思います。良いアイディアをお持ちの方は教えていただけると助かります。議論は適宜、ブログやTogetter等でまとめていきます。

appengine ja night #8での発表

Skip Listの実装についてappengine ja night #8にて発表させていただくことになりました。ご興味のある方はご参加下さい…と言いたいところですが、毎回のことながらappengine ja nightは大人気ですでにキャンセル待ちが68名です…。Ustreamで中継も行われるようなのでそちらをどうぞ。

Google App Engineでランキングやページングを実現する

昨日一昨日、Google App Engine (GAE)に関する日本最大の勉強会(だと思う)appengine ja night #7 (ajn7)が行われました。

その中で『ランキング問題』が話題に上がりました。『ランキング問題』とは、何十万件もの点数のデータがあるときに、App Engine上で、「◯点は何位です」と高速に求めることは難しい、という問題です。(◯ページ目を表示、というページングもこれと同じ種類の問題になります。)

ajn7では「上位でない限り正確な順位は必要ないのではないか」という話になりましたが、Skiplistを用いた検索アルゴリズムを使えば正確かつ高速に順位を求めることができるのではないかと思い、実装&検証してみました。

ランキング(順位取得)のデモ

下記ページで順位取得のデモを動かしています。スコア(点数)を入力すると順位と取得にかかった時間が表示されます(時間にはばらつきが大きいため、取得が遅い場合は何回か試してみて下さい)。

このデモでは、順位は事前に計算されておらずアクセス時にその場で計算しています(事前に計算しておく方法は、挿入時に後ろの順位をすべて付け替える必要があるため、現実的ではありません)。また、このデモでは順位を入力しても新しいデータは挿入されないようにしています(順位取得の時間だけを計測するデモのため)。

http://appengine.koherent.org/ranking

独自ドメインになっていますが、App Engine上で動いています。http://koherence.appspot.com/rankingからもアクセスできます。

Skiplistとは

Skiplistは1990年に発表されたデータ構造(およびそれを利用した検索アルゴリズム)です。シンプルな実装ながら、平衡木と同じように参照・挿入・削除・置換をすべてO(log N)で実行することができます。

Skiplistの解説はこちらにあります。Skiplistは連結リストを複数組み合わせたようなデータ構造なのですが、電車の特急・急行・各駅停車を乗り継げば効率良く目的の駅に到着できるように、ノード(App Engineのノードではなく、Skiplistのノード。駅に相当する)の間引かれた複数の連結リストを乗り換えながら探索することで、高速な参照・挿入・削除・置換を実現しています。

通常のSkiplistでは平衡木等と同じく「何番目か」という情報を取得することができないので、今回はSkiplistの改良型であるIndexable Skiplistを実装しました。

どの程度のパフォーマンスが出るのか

1万件のデータを登録してパフォーマンスを検証してみました。本当は10万件で検証したかったのですが、それだけの件数をすぐに登録することはできなかったのでとりあえず1万件で検証しました。

0〜999999点のスコアをランダムで100個生成して、それぞれの順位を取得するのに要した時間の平均値および標準偏差を求めました。

実時間 [ms] CPU時間 [ms] API時間 [ms]
平均 2774.7 223.4 709.7
標準偏差 2062.7 102.9 308.6

重要なのは、この結果が導くのは10万件のデータのときに10倍(約27秒)かかるということを意味「しない」ことです。Skiplistでは件数に対して操作時間が対数関数的に増加するため、おそらく10万件で3〜5秒、100万件でも5〜8秒程度で順位を取得できると思います。10万件に関しては追加して実験してみたいと思います。また、今回はputの時間を検証していませんがこれも追加して実験したいと思います。感覚的には順位取得の2、3倍程度の時間がかかっているように思います。

パフォーマンスを考えると、実用の際には頻繁にアクセスされる上位の結果をMemcacheに入れて、個々人の順位を取得する場合だけSkiplistにアクセスするという使い方になるでしょう。

ページングに関しても、基本的にSkiplistで同じように実現できると思います(指定した順位から指定した件数のデータを取得するという操作が可能です)。

考察

Skiplistは連結リストのように順々にノードたどっていくため、これをDatastore上に実装しようとすると一つの順位を得るために何度もDatastoreにアクセスしなければなりません。Datastoreは1回読み書きが遅いので、その点で本来連結リストのようなデータ構造には不向きと言えます。ただ、SkiplistではO(log N)で読み書きが可能なので、件数が増えてもアクセス回数の増加は極めてゆるやかです。ですので、何度もDatastoreにアクセスするのは望ましくないけどそれほど回数は多くならないはず、その上で許容可能な回数におさまるかどうか、というのが検証ポイントでした。今回の結果を見る限り、数秒程度の処理時間を許容できるのであれば数万、数十万件規模のランキングを必要とするシステムでも実用可能なのではないかと思います。

ただし、Skiplistの性質上1件ずつしか更新を行うことができないため、更新が極めて多いシステムでは利用が難しいと思います。仮に1件の更新に5秒が必要とすると、それ以上のペースで更新が行われるシステムでは利用できません。

また、一度の操作で複数回のDatastoreアクセスが必要になるため、通常のDatastore操作に比べて多くのリソースを消費します。特にputの処理では複数のノード(一つのノードを一つのエンティティで表現)のポインタの付け替えが発生するため、リソース消費が激しいです。今回1万件を登録するために、無料枠のQuota*1をCPU Timeで65%以上、Datastore API Callsを8%以上使用してしまいました(ただし、put以外の、データ作成や出力などのすべての処理を含んだ消費量です)。

プログラムのソース

Indexable SkiplistをGoogle Collections LibraryのMultimapとして実装しています。が、現在まだ順位を求める部分だけを実装した中途半端な状態なので、きちんと実装できてからオープンソースのライブラリとして公開したいと思います。

その他

今回、僕はajn7に関西のサテライト会場から参加しました。

このサテライト会場は京都GTUGのid:bufferingsさんによって提案され、実施されました。GTUGとはGoogle Technology User Groupの略で、Googleの技術に関するユーザ団体です。GTUGは世界中で活動しており、京都GTUGはその中でも最も活発なグループの一つです。京都GTUGではappengine ja night in kansaiというApp Enigine勉強会を開催しています(まだ1回だけですが、近々第2回が開催されると思います)。App EngineやGoogleの技術(GWTAndroid、...)に興味のある方はぜひ京都GTUGにご参加下さい(僕もつい先日初参加したばかりです)。

また、京都GTUGの活動の会場は、京都リサーチパーク株式会社にご提供いただいています。最近では町屋スタジオという京都らしい施設もオープンされたそうです(そのうち町屋ハッカソンも開催されるとかされないとか)。その他にも様々活動をされているので、興味のある方はチェックしてみて下さい。

*1:一日の無料分のQuotaはCPU TImeが6.50 CPU時間、Datastore API Callsが10,368,000回です。

Indexable B-treeを作る

新幹線で東京に移動している間に前の記事、Google App Engineでランキングやページングを実現するに信じられないくらいのブックマークがついていてびっくりしているのですが、新幹線の中でぼーっと考えているとより高速なランキングを作る方法に気付きました。それはIndexable B-treeを作るということです(Indexable B-treeなんてものがあるのかもわからないです。もしかしたら別の名前で呼ばれているかもしれません)。

今は時間がないので実装して試せないのが残念なのですが、アイディアだけ書いておきます。

B-treeではm分木になっており、各ノードには複数の子ノードへのポインタの配列とどの子ノードに進めばいいかを判別するために子ノードからたどれる値の最小値が入っています。これに加えて、その子ノードからたどれる値の個数も記録しておけばIndexableにできるのではないかと思います。更新時も再帰的に親ノードの個数を書き換えていけばOKです。子ノードからたどれる値の個数ではなく、その子ノードよりも小さい値のノードもすべて含んで、集計した合計個数を格納しておくこともできます。この場合、更新負荷は大きくなりますが(Datastoreで実装する場合には、アクセス回数は変わらないと思います)、参照は早くなります。

B-treeだと何がうれしいかというと、圧倒的にDatastoreアクセスの回数を減らすことができることです。通常のB-treeのように1024分木とか4096分木とかにしてしまえば、10万、100万単位の値からでも、2〜4回程度のDatastoreアクセスで順位(インデックス)を算出することができます。

ただし、一つのノードあたりのバイト数は大きくなってしまうので、Datastore上に実装する場合にその読み書きにどれくらいの時間がかかるかが問題です。エンティティのサイズは、1024分木で数十KB程度になると思います。エンティティのサイズが大きくなってパフォーマンスが落ちてしまうのであれば、mを小さくして(例えば64分木などにして)高速化をはかることもできます。どのmが一番パフォーマンスが良いかは試してみないとわかりません(各バイト数でのエンティティの読み書き速度さえわかれば、計算で概算することはできます。どこかにそんなデータないでしょうか?)。

今すぐにでも実装して検証したいのですが、今週は仕事が詰まっているため時間をとれそうにありません。残念です…。時間が取れ次第検証して、使えそうならライブラリとして公開したいと思います。

DatastoreMapのソースをGitHubにアップする

タイトル通り、DatastoreMap(やMemcacheMap、DatastoreOutputStream等)のソースをGitHubにアップしました。GitHub初めてでよくわかってないけど、これでいいのかな?

GitHub - koher/Koherent-App-Engine-Library-for-Java: Koherent App Engine Library is a library for Google App Engine for Java. It includes "DatastoreMap" which enable to operate Datastores like java.util.HashMap, "DatastoreOutputStream" which enable to write data to Datastores like java.util.FileOutputStream and so on.