Introduction

The Go1.18 with Generics will come soon. So i’m going to try Generics.

We can use Generics in Go Playground by setting “go dev branch”.

Implementation

1. syntax

You can use Generics by writing bracket and type.

(I’m wondering why generics syntax is bracket [T] instead of gt and lt<T>. )

2. declaring cache client

Cache…

--

--

2021年の振り返りです。

今年はとても充実してた気がします。主にプライベートな面でライフイベントが2つあり、それを無事終えることができました。(正直かなり大変だったと思う。)

来年も妻と楽しく過ごせたらいいなと思います。

仕事面に関しては去年の夏から仕込んでたプロダクトがようやく4月にリリースしました。アーキテクチャから関わりつつ、ひたすらGoのコード書いてて楽しかったです。

またGCPやk8sなど初めて触る技術もあり、大いに成長できた年だったなと思います。

一方で課題も色々見つかったため、これからどうなりたいかを考える時間に10~12月と多くを費やしました。方向性は概ね定まったので来年はそれに関して実行していこうと思います。

それでは良いお年を。

--

--

Introduction

大きいデータを処理するにあたり自分はApache SparkとかDataFlow (Apache Beam) などから入りました。ただもっと理解を深めるには派生元となるHadoopの知識を得たいなと思い調べてみることにしました。また今やKubernatesが当たり前ですが大規模な分散システムとしてはHadoopから始まっているため、そのあたりの知識も今後深めたいと思っています。

今回は概要ということで処理フローを簡単に説明してみます。

What’s Apache Hadoop

ビッグデータのための分散処理フレームワークです。もともとはGoogleがMapReduceとして開発したものを研究論文として発表し、それのオープンソース版がHadoopとなります。

Processing Flow

処理としては 1.Map -> ( 2.Combine) -> 3.Shuffle -> 4.Reduce フェーズになります。 Combine は最適化の中間集計で処理の間に挟まることもあるそうです。

WordCountの例で説明していきます。入力は下記のテキストです。

1.Map

Mapフェーズは、入力に対してkey-valueのリストを返します。最終的にはkeyはディメンションでvalueはメトリクスになるようなイメージです。WordCountの例では、keyが単語となりvalueが登場回数となります。

Mapは1行ずつ呼ばれます。 Mapフェーズの出力は下記になります。

2. Combine

Map の出力を中間集計してくれます。1行目はWorldが2回出現してるのでWorld: 2 、2行目はHadoopが2回出現してるのでHadoop: 2 となっています。

3. Shuffle

Shuffleをする目的は同じkeyのデータが同じマシンにいくことです。つまりパーティショニングになります。データを順位付けしてkeyごとにそれぞれ任意のマシンに送信します。これにより分散して取得したデータをkeyごとに処理することができます。

大規模なソートとデータを移動させるため、もっとも時間がかかる処理となるそうです。

HadoopにおけるShuffle処理の実態はマージソートになるようです。データ全体をソートしながらkeyごとにvalueをコレクションに追加して集約していきます。

Shuffleの結果は下記になります。

4. Reduce

ReduceMapで返したユニークなkeyごとに一度づつ呼び出されます。入力はkeyとコレクションを受け取ります。コレクションはkeyと共に生成されたすべてのvalueになります。

keyごとに合計すると登場回数を計算することができます。

Conclusion

今回はHadoopのMapReduceの処理を簡単に追ってみました。

MapReduce を並列処理でスケールさせるため、Shuffle フェーズが大事だなと感じました。Shuffle 処理だけはマシンパワーが必要でここの効率化が求められるような気がしました。

またShuffle に関しては処理内容が違えど、他の大量データを扱うツールにもある考え方なので深堀りしてみたいです。

次は実際に集計処理を実装してみようと思います。

References

--

--

zetasqlをgoでラップしたツールを作っているのですが、その中でzetasqlの返り値がインデントで表現された出力があり、それをgoyaccでパースしてjsonに変換してみた話です。

パースする文字列

具体的には対象のSQLをzetasqlでパースしASTにした後に、ASTに生えてる debug_string() メソッドを実行するとDebug用に整形された文字列が生成されます。(以降DebugString)

  • 元のSQL
  • zetasqlでパース後に整形された文字列

パース方針

正直最初はこのDebugStringをどうパースしていいかわかりませんでした。ぐぐったらStackOverflowにヒントがあったので、それで実装してみることにしました。

インデントのdepthをインクリメント/デクリメントしながら、Stackを使って依存関係を組むASTを選択するというイメージです。

これを goyacc を使ってパースしていきます。

パース方法

1. Lexer

tokenは下記の9種類。

EOF IDENT NUMBER INDENT LINE_BREAK LBRA RBRA HYPHEN VALUE

INDENTに関しては2 spaceで1 インデントとするので、spaceを数えて2で割った数がインデントとなります。(spaceが1つならskip)

INDENT以外は下記の様にtokenに分解されます。

2. Parser

本題です。まず基本的には SQLExpression にtokenを落とし込みます。規則は下記です。VALUEのありなし、INDENTのありなしで実際は4種類あります。INDENTは長さを2で割ってDepthに入れます。

実装は下記にまとまってます。

https://github.com/naoto0822/zetasql-server/tree/main/pkg/parse

--

--

BigQueryのtableとviewが乱立してたので、viewのSQLをパースすれば無向グラフ作って依存関係を出せると思ったのでやってみました。

方針

方針としてはproject配下のtableかviewの情報を順番に取得して、viewであればクエリパースしてノードの依存に追加するという感じです。

またBigQueryのSQLパーサーがほぼ見つからず、pipにそれっぽいものがあったのでpythonで書きました。

↑SQLパーサーがなかったのでzeta SQLをビルドしてcgoでサーバー作ろうとしましたが断念しました。

ノード

table_idは、`project_id.dataset_id.table_id` です。依存関係があるtableやviewを`nodes`に追加していきます。

グラフ作成

project->dataset->tableと全部のtableのAPIを叩きながらノードを作っていきます。viewであればSQLパーサーにいれて依存するidを取得して、対象のノードとの関連を作ります。

描写

最終的にpipのgraphvizを使いグラフをsvgに吐き出します。ノードを作りつつ依存するものがあればエッジにも追加していきます。

結果

最終的にscriptは組めたのですがtableとviewが膨大で画像がとても大きくなり、文字が潰れてしまってただのドット絵が生成されてしまいました、、、。

理想は下記のようなgraphvizにあるようなグラフを思い浮かべたのですが、、、。

--

--