CentOSへKongをインストールする

目標

CentOSへKongをインストールする。

マイクロサービスをAPI Gatewayパターンで実装するため、API Gatewayの構築を考えている。 KongがマイクロサービスのAPI Gatewayとして必要な機能を備えているように見えるため、検証のため今回インストールまで行った。

Kongとは

getkong.org

インストール

環境

$ cat /etc/redhat-release
CentOS Linux release 7.3.1611 (Core)

公式のInstallationへ行くと、DockerやVagrantなど色々なインストール方法がでてくる。 今回はCentOSの項目に従ってインストールを進めていく。 getkong.org

1. Install the Package

パッケージからインストールを行う。

$ wget https://github.com/Mashape/kong/releases/download/0.10.3/kong-0.10.3.el7.noarch.rpm
$ yum install kong-0.10.3.el7.noarch.rpm

2.Configure your database

DB設定を行う。

Kong supports both PostgreSQL 9.4+ and Cassandra 3.x.x as its datastore.

ということなので、今回はPostgreのv9.6をインストールする。

Postgresql downloadページ PostgreSQL: Linux downloads (Red Hat family)

Postgresqlのインストールから起動

$ yum install https://download.postgresql.org/pub/repos/yum/9.6/redhat/rhel-7-x86_64/pgdg-centos96-9.6-3.noarch.rpm

# Install the client packages
$ yum install postgresql96

# Optionally install the server packages:
$ yum install postgresql96-server

# Optionally initialize the database and enable automatic start:
$ /usr/pgsql-9.6/bin/postgresql96-setup initdb
$ systemctl enable postgresql-9.6
$ systemctl start postgresql-9.6

インストール、起動が完了したら、Kong用のDBとDB Userの設定を行う。

$ su - postgres
bash$ psql
$ CREATE USER kong; CREATE DATABASE kong OWNER kong;
$ \q
bash$ psql -l
                                         データベース一覧
   名前    |  所有者  | エンコーディング |  照合順序   | Ctype(変換演算子) |      アクセス権
-----------+----------+------------------+-------------+-------------------+-----------------------
 kong      | kong     | UTF8             | ja_JP.UTF-8 | ja_JP.UTF-8       |
 postgres  | postgres | UTF8             | ja_JP.UTF-8 | ja_JP.UTF-8       |
 template0 | postgres | UTF8             | ja_JP.UTF-8 | ja_JP.UTF-8       | =c/postgres          +
           |          |                  |             |                   | postgres=CTc/postgres
 template1 | postgres | UTF8             | ja_JP.UTF-8 | ja_JP.UTF-8       | =c/postgres          +
           |          |                  |             |                   | postgres=CTc/postgres
(4 行)

3.Start Kong

$ kong start
Error: /usr/local/share/lua/5.1/kong/cmd/start.lua:21: [postgres error] could not get current migrations: [postgres error] FATAL: ユーザ"kong"のIdent認証に失敗しました

上記のエラーが出たので解決する。

/var/lib/pgsql/9.6/data/pg_hba.conf の 82行目を以下のように書き換えた

$vi /var/lib/pgsql/9.6/data/pg_hba.conf
81 # IPv4 local connections:
82 - host    all             all             127.0.0.1/32            ident
81 # IPv4 local connections:
82 + host    all             all             127.0.0.1/32            trust

Postgreを再起動して再度Kongを起動する

$ systemctl restart postgresql-9.6
$ kong start
2017/07/24 17:14:17 [info] Kong started

Kongが動いたので、確認のためcurlで8001ポートへリクエストを投げる。

# Kong is running
$ curl 127.0.0.1:8001
{"timers":{"running":0,"pending":5},"configuration":{"admin_error_log":"logs\/....

正常に動作していれば、上記のようなjsonレスポンスが返ってくる。

実際にAPIを登録してみる

以下3つのキーを指定する

• name
• upstream_url
• uris

http://httpbin.org/ip を登録してみる。

$ curl -i -X POST \ 
>   --url http://localhost:8001/apis \
>   --data 'name=example-api' \
>   --data 'upstream_url=http://httpbin.org/ip' \
>   --data 'uris=/httpbin/ip' \

HTTP/1.1 201 Created
Date: Mon, 24 Jul 2017 10:25:00 GMT
Content-Type: application/json; charset=utf-8
Transfer-Encoding: chunked
Connection: keep-alive
Access-Control-Allow-Origin: *
Server: kong/0.10.3

{"http_if_terminated":true,"id":"9f15037b-c303-4da6-ae12-465d48998f79","retries":5,"preserve_host":false,"created_at":1500891900000,"upstream_connect_timeout":60000,"upstream_url":"http:\/\/httpbin.org\/ip","upstream_read_timeout":60000,"https_only":false,"upstream_send_timeout":60000,"strip_uri":true,"name":"example-api","uris":["\/httpbin\/ip"]}

以下のリクエストを送信する。

$ curl -i -X GET \
>   --url http://localhost:8000/httpbin/ip \
>
HTTP/1.1 200 OK
Date: Mon, 24 Jul 2017 10:27:25 GMT
Content-Type: application/json
Content-Length: 44
Connection: keep-alive
Server: meinheld/0.6.1
Access-Control-Allow-Origin: *
Access-Control-Allow-Credentials: true
X-Powered-By: Flask
X-Processed-Time: 0.000926971435547
Via: kong/0.10.3
X-Kong-Upstream-Latency: 335
X-Kong-Proxy-Latency: 264

{
  "origin": "127.0.0.1, xxx.xxx.xxx.xxx"
}

すると、localhost:8000へのリクエストがhttpbin.org/ipへ転送され、その結果が返ってくる。

削除する場合はDELETEメソッドを使う

$ curl -i -X DELETE \  --url http://localhost:8001/apis/example-api

まとめ

検証はこれから。

マイクロサービスアーキテクチャ

#16/20 BFS: Shortest Reach in a Graph [Cracking the Coding Interview Challenges]

16 BFS: Shortest Reach in a Graph

www.hackerrank.com

以下の形式の入力が与えられる。

2
4 2
1 2
1 3
1
3 1
2 3
2

最初の行には、クエリの数を示す整数が示される。後続の行は、各クエリを次の形式で示す。

• 最初の行には、グラフ内のノードの数nとエッジの数mのそれぞれの値をスペースで区切りの2つの整数で示す。
• 後続の各行には、スペースで区切られた2つの整数が含まれており、ノードからノードに接続するエッジが示される。
• 最後の行には、開始ノードのインデックスを示す1つの整数が示される。

出力は、開始ノードから各ノードへの距離を出力する。1つのエッジの距離は6、エッジで繋がっていないノードへの距離は-1 とする。

上記入力の場合、解答は以下となる。

6 6 -1
-1 6

solution

この問題は、無向グラフの探索問題である。 幅優先探索(BFS)アルゴリズムで解いている。以下、rubyでの解。

class Node
    def initialize
        @neighbors = []
    end
    
    def addNeighbor(id)
        @neighbors << id if !@neighbors.index(id)
    end
    
    def getNeighbors
        return @neighbors
    end
end

class Graph
    DIST = 6
    
    def initialize
        @nodes = []
    end
    
    def addNode(node)
        @nodes << node
    end
    
    def shortestReach(startId)
        dist = Array.new(@nodes.size, -1)
        dist[startId] = 0
        queue = []
        queue << startId
   
        while (!queue.empty?)
            nodeId = queue.shift
            @nodes[nodeId].getNeighbors.each do |neighbor|
                if dist[neighbor] == -1
                    queue << neighbor
                    dist[neighbor] = dist[nodeId] + DIST
                end
            end
        end
        return dist
    end
    
end

input = $stdin.read.split("\n")
q = input.shift.to_i

q.times do
    n, edges = input.shift.split(" ").map(&:to_i)
    graph, nodes = Graph.new, []

    n.times { nodes << Node.new }
    
    for i in 0..edges-1
        ary = input.shift.split(" ").map(&:to_i)
        idx1, idx2 = ary[0] - 1, ary[1] - 1
        nodes[idx1].addNeighbor(idx2) if nodes[idx1]
        nodes[idx2].addNeighbor(idx1) if nodes[idx2]
    end
    
    nodes.each { |node| graph.addNode(node) }
    
    startId = input.shift.to_i - 1
    dist = graph.shortestReach(startId)
    dist.delete_at(startId)
    puts dist.join(" ") # output answer here
end

グラフ理論

グラフ理論 - Wikipedia

BFS(breadth first search: 幅優先探索)とは

幅優先探索 - Wikipedia

感想

BFSアルゴリズム自体は難しくないが、有向or無向、深さ優先or幅優先、訪問済みを無視するかどうか、など一歩処理を間違えると期待する答えが得られなくなるので注意する。

#15/20 DFS: Connected Cell in a Grid [Cracking the Coding Interview Challenges]

#15 DFS: Connected Cell in a Grid

www.hackerrank.com

以下のような入力が与えられる。

4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0

1行目にn行、2行目にm列、それ以降はn行m列分のマトリックスがスペース区切りで与えられる。 マトリックス内で、1のセルが隣接している(縦横斜め)領域を調べ、マトリックス内での最大領域数を出力する。

上記入力の場合、1が隣接している最大領域は5となるので、5を出力する。

5

solution

再帰ありDFS(depth first search)で解いた。以下、rubyでの解。

一度訪問した箇所を再度調べる必要はないので、訪問済みの位置には0をセットしている。

#!/bin/ruby

class Solution

    def initialize(matrix)
        @matrix = matrix
    end

    def getBiggestResion
        matrix = @matrix.clone
        maxSize = 0

        for row in 0..(matrix.size - 1)
            for column in 0..(matrix[row].size - 1)
                if matrix[row][column] == 1
                    size = getResionSize(matrix, row, column)
                    maxSize = size if maxSize < size
                end
            end
        end
        return maxSize
    end
    
    private
        def getResionSize(matrix, row, column)
            return 0 if row < 0 || column < 0 || row >= matrix.size || column >= matrix[row].size
            return 0 if matrix[row][column] == 0

            size, matrix[row][column] = 1, 0
            for r in (row - 1)..(row + 1)
                for c in (column - 1)..(column + 1)
                    if r != row || c != column
                        size += getResionSize(matrix, r, c)
                    end
                end
            end
            return size
        end
end

input = $stdin.read.split("\n")
n, m, matrix = input.shift.to_i, input.shift.to_i, []
input.each_with_index { |v, i| matrix[i] = v.split(" ").map(&:to_i) }
puts (Solution.new(matrix)).getBiggestResion

github.com

DFS(depth-first search: 深さ優先探索)とは

深さ優先探索 - Wikipedia

まとめ

スタックでやる再帰なしより、再帰で書く方が楽だと思う。

都内から江ノ島へ自転車日帰りツーリング

休みに予定がぽっかり空いてしまったので、たまには自転車で日帰り旅でもしようかな、と思い江ノ島に行ってきた。 江ノ島は世田谷区からちょうど往復100kmなので、ロードバイクなら十分日帰り可能だ。

ロードバイク

GIANTのDEFY3。確か今はもうDEFYシリーズは売られてないと思う。 通勤用に2013年に購入して、まだまだ現役。

ルート

google 先生に聞くと、246号線のルートがサジェストされた。まあいいんだけど、往復でルートを変えたかったので、行きは丸子橋を通るルートで、帰りは246号線を走るルートを走ることにした。

往路

*google map のオプションで有料道路と高速道路を不使用にチェック

復路

飯田牧場に寄って、246号線で帰るルート。

*google map のオプションで有料道路と高速道路を不使用にチェック

出発

暑い一日になりそうなので、早朝に出発する。 50kmならゆったりペースでも3時間半あれば着くかな、という見積もり。

6:15 世田谷区(三軒茶屋駅)出発

写真は丸子橋を渡るところ。

9:15 頃、江ノ島海岸到着

この時間はまだまだ人はまばらだけど、昼にかけてどんどん人が増えてきそうな気配がある。

江ノ島入り口

江ノ島の入り口で記念撮影。途中道を間違えたりしながら、ここまで約51kmだった。

江ノ島神社

enoshimajinja.or.jp

奥津宮、中津宮、辺津宮の３つがあり、それぞれ3姉妹の女神がお祀りされている。

• 奥津宮の多紀理比賣命（たぎりひめのみこと）
• 中津宮の市寸島比賣命（いちきしまひめのみこと）
• 辺津宮の田寸津比賣命（たぎつひめのみこと）

なるほど。この3女神さらに弁財天女(七福神の一柱でもある弁才天)と称され、才能や財宝を招いてくれるそうだ。 それぞれ参拝をした。

サムエルコッキング苑

サムエル・コッキングというイギリス出身貿易商の庭園らしい。 有料で、あまり興味はわかなかったので入場しなかった。

江の島サムエル・コッキング苑 - Wikipedia

しらす問屋 とびっちょ

人気店。開店30分前に行ってみたが、すでにかなりの人が店前にいる。 整理券の発行機が店頭に置いてあり、60という数字が見え、諦めた。 食べたい人は、早めに発券機で整理券を取っておいた方がいいだろう。

同じように生しらすや海鮮丼を提供している店はたくさんあるのに、開店前に行列ができているのはこの店だけだ。 周り店とどう違うのか。

せっかくなので、店頭売っていた生しらすを買って食べた。500円。おいしいけど、もうちょっと量が欲しかったな。

飯田牧場

自転車乗りが結構集まるみたいで、せっかくなので帰りに寄ってみることにした。 話通り、自転車が沢山止まっていて圧倒された。 シングルのミルクジェラートを注文した。美味しい。ジェラートは最強。

店内にはろんぐらいだぁす、という自転車マンガが置いてあって、知らなかったけどこのマンガに飯田牧場が出てるみたいだ。 所謂聖地だったか。

15時頃には帰宅。

感想

とにかく暑かったけど、久しぶりの自転車旅、最高だった。輪行もそろそろやってみたい。

#14/20 Binary Search: Ice Cream Parlor [Cracking the Coding Interview Challenges]

#14 Binary Search: Ice Cream Parlor

www.hackerrank.com

アイスクリーム屋で、持っているお金を全てを使い切って2個のアイスクリームを購入したい。 その組み合わせを見つける、という問題。

アイスクリーム屋には、様々なフレーバーのアイスがあり、それぞれ値段とユニークなIDが定められている(IDは与えられる入力順に1から始まる)。

以下のような入力が与えられる。

2
4
5
1 4 5 3 2
4
4
2 2 4 3

1. 1行目はアイスクリーム屋に行く回数
2. 2行目以降は3行単位で、1.所持金、2.フレーバーの総数、3.フレーバーのコストが繰り返される。

解答は2個のアイスクリームのIDをスペース区切りで、ID昇順で出力する。上記入力場合、解答は以下となる。

1 4
1 2

solution

問題タイトルどおり、バイナリーサーチを使って解いた。

#!/bin/ruby

def binarySearch(ary, key, min, max)
    return -1 if max < min
    
    mid = min + (max - min) / 2
    if key < ary[mid]
        return binarySearch(ary, key, min, mid -1)
    elsif key > ary[mid]
        return binarySearch(ary, key, mid + 1, max)
    else
        return mid
    end
end

def getFlavorId(menu, value, excludeIdx = nil)
    menu.each_with_index do |v, i|
        if v == value
            if excludeIdx && excludeIdx == i
                next
            else
                return i + 1
            end
        end
    end
    return -1
end

def find(menu, money)
    sorted = menu.sort
    len = menu.size
    sorted.each_with_index do |v, i|
        complement = money - v
        result = binarySearch(sorted, complement, i + 1, len - 1)
        if result != -1
            flavor1 = getFlavorId(menu, v)
            flavor2 = getFlavorId(menu, sorted[result], flavor1 - 1)
            return [flavor1, flavor2].sort if flavor2 != -1
        end
    end
    return []
end


input = $stdin.read.split("\n")
trips = input.shift.to_i
trips.times do
    money, n, menu = input.shift.to_i, input.shift.to_i, input.shift.split(" ").map(&:to_i)
    puts find(menu, money).join(" ")
end

github.com

Binary Search(2分探索)とは

二分探索 - Wikipedia

#13/20 DP: Coin Change [Cracking the Coding Interview Challenges]

#13 DP: Coin Change

www.hackerrank.com

タイトルどおり、Dynamic Programming で解く問題。

以下のような入力が与えられる。

4 3
1 2 3

4 3 # {コインの組み合わせで達成したい値} {コインの種類数}
1 2 3 # コインの種類。この場合、価値が1, 2, 3の3種類のコインが存在するということになる

各コインが無限に利用可能である場合、達成したい値(上記の場合4)を達成する組み合わせが何通り存在するかを計算する。

上記の入力の場合

• 1,1,1,1
• 1,1,2
• 2,2
• 1,3

の4種類の組み合わせがあるため、4を出力すれば良い。

solution

以下 ruby での解。

#!/bin/ruby

def solution(coins, target)
    lenCoins = coins.size
    table = Array.new(lenCoins + 1).map{Array.new(target + 1,0)}
    for i in 0..lenCoins
        table[i][0] = 1
    end

    for i in 1..lenCoins
        for j in 1..target
            table[i][j] = coins[i - 1] <= j ?
                table[i - 1][j] + table[i][j - coins[i -1]]
                : table[i - 1][j]
        end
    end
    return table[lenCoins][target];
end

input = $stdin.read.split("\n")
n, m = input[0].split(" ").map(&:to_i)
coins = input[1].split(" ").map(&:to_i)
puts solution(coins, n)

動的計画法に倣って、まず小さい問題に分割、ボトムアップで順次に解を得ていくというアプローチで解いた。 ソースコード内table配列が全ての部分結果を保持する。

追加するコインの値がtarget値より大きい場合

table[i - 1][j] を参照する 。合計値をオーバーするためこの場合、既に算出している自身より1ワイズ小さいコインの結果を参照する。

追加するコインの値がtarget値以下の場合

table[i - 1][j] + table[i][j - coins[i -1]] を参照する。 自身のコインを追加できる場合、目標値は(target - コインの値)と考えることができるので既に算出済みの table[追加するコインindex][(target - 追加するコインの値)] を加算している。

github.com

Dynamic Programming(動的計画法)とは

動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

動的計画法 - Wikipedia

感想

動的計画法、すらすらと書けないなあ。解いてみるとすごくシンプルなんだけど。

#12/20 Merge Sort: Counting Inversions [Cracking the Coding Interview Challenges]

#12 Merge Sort: Counting Inversions

www.hackerrank.com

以下のようなインプットが与えられる。

2  
5  
1 1 1 2 2  
5  
2 1 3 1 2

• 1行目はデータセットの総数
• 2行目以降はデータセットの総数分だけ以下の入力の繰り返し
  • データの要素の数が整数で与えられる
  • スペース区切りで上記要素の数だけ整数が与えられる

与えられたデータをマージソートし、swapした回数を出力する。 上記のインプットの場合、2個のデータセットが与えられるので、それぞれに対して マージソートを行いswap数を出力する。

0  
4   

solution

以下、rubyでの解。

class Solution

    def initialize(ary)
        @ary = ary
        @swaps = 0
    end

    def mergeSort(ary = @ary)
        return ary if (len = ary.size) <= 1
        ary = ary.clone
        mid = len == 2 ? 1 : len / 2
        list1 = ary.slice(0, mid)
        list2 = ary.slice(mid, len - mid)

        return merge(self.mergeSort(list1), self.mergeSort(list2))
    end

    def getSwaps
        return @swaps
    end

    private
        def merge(list1, list2)
            len1, len2 = list1.size, list2.size
            result = Array.new(len1 + len2)
            a, b, i, j, k = list1[0], list2[0], 0, 0, 0
            loop {
                if a <= b then
                    result[i] = a
                    i += 1
                    j += 1
                    break unless j < len1
                    a = list1[j]
                else
                    # count number of swaps here
                    @swaps += len1 - j
                    result[i] = b
                    i += 1
                    k += 1
                    break unless k < len2
                    b = list2[k]
                end
            }
            while j < len1 do
                result[i] = list1[j]
                i += 1
                j += 1
            end
            while k < len2 do
                result[i] = list2[k]
                i += 1
                k += 1
            end
            return result
        end
end

input = $stdin.read.split("\n")
d = input.shift.to_i
d.times do |v|
    n, ary = input.shift.to_i, input.shift.split(" ").map(&:to_i)
    s = Solution.new(ary)
    s.mergeSort
    puts s.getSwaps
end

github.com

マージソートとは

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする。 （ナイーブな）クイックソートと比べると、最悪計算量は少ない。ランダムなデータでは通常、クイックソートのほうが速い。

マージソート - Wikipedia