OpenBSD: PostgreSQL 導入と設定

1. PostgreSQL パッケージのインストール.

$ su
password:
# pkg_add postgresql-server
quirks-2.9 signed on 2014-08-02T11:06:13Z
postgresql-server-9.3.4p0:postgresql-client-9.3.4p0: ok
useradd: Warning: home directory `/var/postgresql' doesn't exist, and -m was not specified
postgresql-server-9.3.4p0: ok
The following new rcscripts were installed: /etc/rc.d/postgresql
See rc.d(8) for details.
Look in /usr/local/share/doc/pkg-readmes for extra documentation.
#

2. ロケールを設定し PostgreSQL の新しいデータベースクラスタを作成する.

# su - _postgresql
$ export LC_CTYPE=ja_JP.UTF-8
$ initdb -D /var/postgresql/data -U postgres -E UTF-8 -A md5 -W
The files belonging to this database system will be owned by user "_postgresql".
This user must also own the server process.

The database cluster will be initialized with locales
  COLLATE:  C
  CTYPE:    ja_JP.UTF-8
  MESSAGES: C
  MONETARY: C
  NUMERIC:  C
  TIME:     C
initdb: could not find suitable text search configuration for locale "ja_JP.UTF-8"
The default text search configuration will be set to "simple".

Data page checksums are disabled.

creating directory /var/postgresql/data ... ok
creating subdirectories ... ok
selecting default max_connections ... 40
selecting default shared_buffers ... 128MB
creating configuration files ... ok
creating template1 database in /var/postgresql/data/base/1 ... ok
initializing pg_authid ... ok
Enter new superuser password:
Enter it again:
setting password ... ok
initializing dependencies ... ok
creating system views ... ok
loading system objects' descriptions ... ok
creating collations ... not supported on this platform
creating conversions ... ok
creating dictionaries ... ok
setting privileges on built-in objects ... ok
creating information schema ... ok
loading PL/pgSQL server-side language ... ok
vacuuming database template1 ... ok
copying template1 to template0 ... ok
copying template1 to postgres ... ok
syncing data to disk ... ok

Success. You can now start the database server using:

    postgres -D /var/postgresql/data
or
    pg_ctl -D /var/postgresql/data -l logfile start

$ exit

3. PostgreSQL の起動スクリプトと停止スクリプト

# ed /etc/rc.local
/etc/rc.local: No such file or directory
a
if [ -x /usr/local/bin/pg_ctl ]; then
        echo -n ' postgresql'
        su -l _postgresql -c "nohup /usr/local/bin/pg_ctl start \
            -D /var/postgresql/data -l /var/postgresql/logfile \
            -o '-D /var/postgresql/data' >/dev/null"
fi
.
w
227
q
# ed /etc/rc.shutdown
/etc/rc.shutdown: No such file or directory
a
if [ -f /var/postgresql/data/postmaster.pid ]; then
        su -l _postgresql -c "/usr/local/bin/pg_ctl stop -m fast \
            -D /var/postgresql/data"
        rm -f /var/postgresql/data/postmaster.pid
fi
.
w
188
q
#

4. 再起動後, postgresql のロケールを確認

# reboot
(snip)
$ su - _postgresql
Password:
Sorry
$ psql -U postgres -l
Password for user postgres:
                                List of databases
   Name    |  Owner   | Encoding | Collate |    Ctype    |   Access privileges
-----------+----------+----------+---------+-------------+-----------------------
 postgres  | postgres | UTF8     | C       | ja_JP.UTF-8 |
 template0 | postgres | UTF8     | C       | ja_JP.UTF-8 | =c/postgres          +
           |          |          |         |             | postgres=CTc/postgres
 template1 | postgres | UTF8     | C       | ja_JP.UTF-8 | =c/postgres          +
           |          |          |         |             | postgres=CTc/postgres
(3 rows)

$

XREA: 楕円 DSA 鍵でログイン

環境の確認

 この手順が記録されたときのローカルホストとリモートホストの環境は

# : ThinkPad X61
$ uname -sr
OpenBSD 5.6
$ ssh -V
OpenSSH_6.7, LibreSSL 2.0

# : XREA
$ uname -sr
Linux 2.6.27.59-smp
$ ssh -V
OpenSSH_6.6p1 OpenSSL 0.9.8za 5 Jun 2014

となっています。

 ECDSA (楕円 DSA) は OpenSSL 5.7 (参照: OpenSSH 5.7 リリースノート)

Changes since OpenSSH 5.6
=========================

Features:

 * Implement Elliptic Curve Cryptography modes for key exchange (ECDH)
   and host/user keys (ECDSA) as specified by RFC5656. ECDH and ECDSA
   offer better performance than plain DH and DSA at the same equivalent
   symmetric key length, as well as much shorter keys.

から対応なので, ローカルホストとリモートホストの OpenSSH のバージョンが 5.7 以上で対応しているかどうか事前に確認しておきましょう.

楕円 DSA 鍵の強度

 The Case for Elliptic Curve Cryptography によれば, 楕円 DSA の 521 ビットは, RSA の 15360 ビット相当の強度があるようです.

1. ホームディレクトリに .ssh ディレクトリを作り, 鍵を生成する.

 ローカルホストのホームディレクトリで .ssh ディレクトリを作成・移動後, ssh-keygen コマンドで秘密鍵のパスフレーズを入力し鍵のペア (公開鍵と秘密鍵) を生成します.

$ cd
$ pwd
/home/your
$ mkdir .ssh
$ cd .ssh
$ ssh-keygen -t ecdsa -b 521
Generating public/private ecdsa key pair.
Enter file in which to save the key (/home/your/.ssh/id_ecdsa):
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /home/your/.ssh/id_ecdsa.
Your public key has been saved in /home/your/.ssh/id_ecdsa.pub.
The key fingerprint is:
1e:5e:32:27:23:3a:02:6f:fb:e3:b7:66:59:37:aa:77 your@your.domain
The key's randomart image is:
+---[ECDSA 521]---+
|                 |
|                 |
|                 |
|                 |
|.     . S o      |
| o   . +.Oo      |
|  + o  ooo .     |
| . o..= o E      |
|  .oo=o+ .       |
+-----------------+
$ ls
id_ecdsa id_ecdsa.pub

二つの鍵ファイル id_ecdsa (秘密鍵) と id_ecdsa.pub (公開鍵) が生成されました.

2. 認証鍵を XREA にアップロードし, authorized_keys ファイルに登録する.

 先ほど生成した認証鍵のファイル id_ecdsa.pub を, リモートホストである XREA に scp コマンドでアップロードします.

$ scp ./id_ecdsa.pub your@your.com:.
The authenticity of host 'your.com (XXX.XXX.XXX.XXX)' can't be established.
ECDSA key fingerprint is 1e:5e:32:27:23:3a:02:6f:fb:e3:b7:66:59:37:aa:77.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'your.com,XXX.XXX.XXX.XXX' (ECDSA) to the list of known hosts.
your@your.com's password:
id_ecdsa.pub    100%  274    0.3KB/
$

ssh 関連のコマンド (scp, sftp なども含む) でサーバに接続する際, そのサーバとの接続が初めてのときに限り, 上記のように警告のメッセージが表示されます. 今回は「yes」と入力しリモートホストの公開鍵をローカルホストの known_hosts ファイルに登録しました.

$ pwd
/home/your/.ssh
$ ls
id_ecdsa id_ecdsa.pub known_hosts
$

 次は ssh で XREA にログインし id_ecdsa.pub を authorized_keys に登録します. 今回鍵の登録は初めてなので .ssh と authorized_keys を作成してから id_ecdsa.pub を登録していますが, 既に authorized_keys がある場合は authorized_keys に上書きしないように気をつけてください.

$ ssh your@your.com
your@your.com's password: 
Last login: Thu Feb  5 00:02:32 2015 from your-IP

> cd                                    
> pwd                                   
/virtual/your
> mkdir .ssh                            
> chmod 700 .ssh                        
> cd .ssh                               
> mv ../id_ecdsa.pub ./                 
> touch authorized_keys                 
> cat id_ecdsa.pub >>authorized_keys    
> chmod 600 authorized_keys             
> rm id_ecdsa.pub                       
> logout                                
Connection to your.com closed.

$

 鍵の登録が正しく完了していれば, 秘密鍵のパスフレーズのみで XREA にログインすることができます.

$ ssh your@your.com
Enter passphrase for key '/home/your/.ssh/id_ecdsa': 
Last login: Thu Feb  5 00:04:57 2015 from your-IP

> pwd
/virtual/your
> logout
Connection to your.com closed.

$

以上で, おしまいです.

参考サイト

GitHubユーザーのSSH鍵6万個を調べてみた
SSH接続エラー回避方法:.ssh/known_hostsから特定のホストを削除する/削除しないで対処する3つの方法

さらに詳しく

LinuxでSSH -- 秘密鍵のパスフレーズ入力の省略など.

A. サンダラムの篩

 1934 年, インドの数学科の学生サンダラム (Sundaram) によって, 素数を求めるアルゴリズム「サンダラムの篩」が発見されました.

 このアルゴリズムでは, $1$ から $n$ までの整数から

$i + j + 2ij \leqq n \quad (i,j \in N, \ 1 \leqq i \leqq j)$

の形に表わすことができる整数を取り除きます. この形で表わせる任意の整数を $k$ とし $2k + 1$ とすれば, 奇数の合成数が得られます (後述). これがサンダラムの篩の核心になります.

素数と合成数

 $n > 1$ の整数は次の二種類に分かれます.

  素数   $1$ と $n$ 以外の約数がない (例えば $2, 31, 73$ など).
  合成数  $1$ と $n$ 以外の約数がある (例えば $8, 49, 72$ など).

また合成数は次の三種類に分かれます.

  偶数の合成数  偶数と偶数の積 (例えば $2 \times 4 = 8$ など).
  偶数の合成数  偶数と奇数の積 (例えば $8 \times 9 = 72$ など).
  奇数の合成数  奇数と奇数の積 (例えば $7 \times 7 = 49$ など).

したがって整数 $n > 1$ は, 素数または合成数で, 合成数だけを篩い落せば素数が残されるという訳です.

理論的な根拠

 まず正の整数を

$1, \ 2, \ 3, \ \cdots\cdots$

のように大きさの順序に並べ, それぞれの整数を $2n+1$ に代入すれば

$3, \ 5, \ 7, \ \cdots\cdots$

で, 偶数の合成数だけを取り除いた数列が得られます. 残ったのは素数と奇数の合成数からなる数列で, あとは奇数の合成数を取り除くことができれば, 素数だけが残る数列が得られることになります.

 さて奇数の合成数は

$(2i+1)(2j+1) \quad (1 \leqq i \leqq j)$

の形で表わすことができます. ここで

$(2i+1)(2j+1)=2(i+j+2ij)+1$

とすれば

$k=i+j+2ij$

$(2i+1)(2j+1)=2k+1$

を得ます. 言い換えれば $k$ を

$k=4, \ 7, \ 10, \ 12, \ 13, \ 16, \ 17, \ \cdots\cdots$

のように大きさの順序に並べ, それぞれの整数を $2k + 1$ に代入すれば奇数の合成数が得られます.

 いま正の整数を

$1, \ 2, \ 3, \ \cdots\cdots$

のように大きさの順序に並べ, それらの中から $k$ を取り除けば

$1, \ 2, \ 3, \ 5, \ 6, \ 8, \ 9, \ 11, \ 14, \ 15, \ \cdots\cdots$

で, $k$ を篩った数列が得られます. この数列のそれぞれの整数を $2n+1$ に代入すれば

$3, \ 5, \ 7, \ 11, \ 13, \ 17, \ 19, \ 23, \ 29, \ 31, \ \cdots\cdots$

が得られます. ここで $k$ を $2n+1$ にしたと仮定すれば, それは奇数の合成数になるので, 最後に得られた数列は偶数の合成数と奇数の合成数を篩った数列, すなわち素数の数列 (ただし $2$ を除く) となります.

C による実装

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_PRIMES 1000000

void
sundaram(void)
{
    int *sieve = (int *) calloc(MAX_PRIMES/2, sizeof(int));
    if (sieve == NULL)
        return;

    int i, j, k;
    for (i = 1; i < sqrt(MAX_PRIMES); i++)
        for (j = i; (k = i+j+2*i*j) < MAX_PRIMES/2; j++)
            sieve[k] = 1;

    printf("2\n");
    for (i = 1; i < MAX_PRIMES/2; i++)
        if (sieve[i] == 0)
            printf("%d\n", 2*i+1);

    free(sieve);
}

int
main(void)
{
    sundaram();

    return EXIT_SUCCESS;
}

実行例

$ time ./a.out | wc -l
  664579
    0m1.11s real     0m1.06s user     0m0.02s system
$

Cython による実装

from libc.stdlib cimport calloc, free

cdef enum:
    MAX_PRIMES = 1000000

cdef sundaram():
    cdef bint *sieve = <bint *> calloc(MAX_PRIMES//2, sizeof(bint))

    cdef i, j, k
    i = 1
    while i < MAX_PRIMES ** 0.5:
        j = i
        k = i + j + 2 * i * j
        while k < MAX_PRIMES//2:
            sieve[k] = 1
            j += 1
            k = i + j + 2 * i * j
        i += 1

    print(2)
    i = 1
    while i < MAX_PRIMES//2:
        if sieve[i] == 0:
            print(2*i+1)
        i += 1

    free(sieve)

sundaram()

実行例

$ time python run.py | wc -l
  664579
    0m10.96s real     0m10.89s user     0m0.02s system
$

A. 試し割り法

 試し割り法 (Trial division) は, 素因数分解アルゴリズムの中では最も効率の悪い方法ですが, 簡単に理解することができます. 試し割り法の基本的な考えは, 素因数に分解される整数 $n$ を $n$ より小さい整数で, ただ割っていくことです.

 $n$ の素因数を出力するだけなら,

def junk(n):
    """"""
    for i in range(2, n):
        while n % i == 0:
            n //= i
            print(i)
    if n > 1:
        print(n)

最小の素因数 $2$ から繰り返し割っていけば, 割り切れる整数に素数が残っていくことは明らかなので、あとは残った $n$ が $n > 1$ であるならば, それが最後の素因数となります.

 $n$ を素因数分解したとき, $\sqrt{n}$ 以上の素因数は多くても一つしか含まれないので, 最大の因数は $\sqrt{n}$ としていいことがわかります。例えば $n=360$ のとき, 最大の因数は $\sqrt{n}\ \fallingdotseq\ 18.97367$ となります. ここで $\lfloor \sqrt{n} \rfloor = 18$ としてしまうと誤差がでるため, $\lfloor \sqrt{n} \rfloor + 1$ もしくは $\lceil \sqrt{n} \rceil$ とします.

Python による実装 (1)

def trial_division(n):
    """"""
    if n == 1:
        return [1]
    factors = []
    for i in range(2, int(n**0.5) + 1 + 1):
        while n % i == 0:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

実行例

trial_division(360)
[2, 2, 2, 3, 3, 5]

計算量

$\pi(2^{n/2})$