/lib/piece/blog/begin.php
/lib/piece/blog/entries.php
조토 블로그-zhoto.tistory.com 으로 이사 ::

'IT 이야기'에 해당되는 글 4건

  1. 2007/06/07 수도쿠(sukodo) 알고리즘
  2. 2007/05/02 [20061108] apache ab를 이용한 벤치마크
  3. 2007/02/13 검색엔진 관련 자료
최근 들어 수도쿠에 관심이 많아졌다. 심심할 때 한 두개씩 풀어보는데,
그냥 푸는니 뭔가 알고리즘을 만들면 좋지 않을까 해서 머리를 굴려봤다.
그러나 세상에 머리를 굴리는 것보다 찾는 것이 좋을 때가 있다.
벌써 세줄 짜리 코드가 나왔다.
http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html

위 코드에 대한 한글 소개도 이미 있다.
http://www.0daedorm.com/blog/entry/3줄짜리-스도쿠-풀이-코드

이는 아래 네줄 짜리 알고리즘을 개량한 것이다.
http://www.ecclestoad.co.uk/blog/2005/05/25/sudoku_solver_in_four_lines.html

스토쿠를 웹으로 구현하는 방법도 있다.
http://www.ibm.com/developerworks/kr/library/x-xformssudoku1/

그리고 스도쿠 해법에 대한 여러가지 방법론도 있다.
http://en.wikipedia.org/wiki/Algorithmics_of_Sudoku

스도쿠에 대한 모든 것을 알 수 있는 링크도 있다.
http://bigbluehouse.tistory.com/67

스도쿠 해법에 대한 자세한 내용이 많이 있다.
http://www.sudokuoftheday.com/

2006년 11월 08일 작성

1. 기본정보

apache 에는 ab 라고 하는 벤치마크 툴이 포함되어 있다. ab를 이용하면 특정 서버 또는 웹 프로그램의 성능을 테스트해볼 수 있다. 보통 ab는 다음과 같은 위치에 설치된다.

/usr/local/apache/bin/ab

ab 실행과 관련된 명령과 옵션은 다음과 같다.

Usage: ./ab [options] [http://]hostname[:port]/path
Options are:
    -n requests     Number of requests to perform
    -c concurrency  Number of multiple requests to make
    -t timelimit    Seconds to max. wait for responses
    -p postfile     File containg data to POST
    -T content-type Content-type header for POSTing
    -v verbosity    How much troubleshooting info to print
    -w              Print out results in HTML tables
    -i              Use HEAD instead of GET
    -x attributes   String to insert as table attributes
    -y attributes   String to insert as tr attributes
    -z attributes   String to insert as td or th attributes
    -C attribute    Add cookie, eg. 'Apache=1234' (repeatable)
    -H attribute    Add Arbitrary header line, eg. 'Accept-Encoding: zop'
                    Inserted after all normal header lines. (repeatable)
    -A attribute    Add Basic WWW Authentication, the attributes
                    are a colon separated username and password.
    -P attribute    Add Basic Proxy Authentication, the attributes
                    are a colon separated username and password.
    -X proxy:port   Proxyserver and port number to use
    -V              Print version number and exit
    -k              Use HTTP KeepAlive feature
    -d              Do not show percentiles served table.
    -S              Do not show confidence estimators and warnings.
    -g filename     Output collected data to gnuplot format file.
    -e filename     Output CSV file with percentages served
    -h              Display usage information (this message)

ab에서 주로 사용하는 옵션은 -t, -c, -n 이다.

ab -t 10 -c 10 url

이 옵션은 지정된 URL에 대해서 동시 클라이언트© 10개로 10초간 지속해서 최대 가능한 request를 보내고 응답을 받는다. 시간이 정해져 있기 때문에, 결과로 나온 회수로 비교가 가능하다.

ab -n 100 -c 10 url

이 옵션은 지정된 URL에 대해서 동시 클라이언트© 10개로 최대 request(n)을 보내고 응답을 받는다. request가 정해져 있기 때문에, 결과로 나온 값시간으로 비교가 가능하다.
주로 이 두 가지를 방법을 이용해서 사용하는데, 첫번째 방법을 개인적으로 좋아한다.

ab를 실행하면 다음과 같은 화면이 출력된다.

/usr/local/apache/bin/ab -t 1 -c 1 http://localhost/
This is ApacheBench, Version 1.3d <$Revision: 1.73 $> apache-1.3
Copyright (c) 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Copyright (c) 1998-2002 The Apache Software Foundation, http://www.apache.org/

Benchmarking localhost (be patient)
Finished 328 requests
Server Software:        Apache/1.3.36
Server Hostname:        localhost
Server Port:            80

Document Path:          /
Document Length:        1456 bytes

Concurrency Level:      1
Time taken for tests:   1.000 seconds
Complete requests:      328
Failed requests:        0
Broken pipe errors:     0
Total transferred:      584633 bytes
HTML transferred:       479024 bytes
Requests per second:    328.00 [#/sec] (mean)
Time per request:       3.05 [ms] (mean)
Time per request:       3.05 [ms] (mean, across all concurrent requests)
Transfer rate:          584.63 [Kbytes/sec] received

Connnection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0     0    0.0      0     0
Processing:     2     2    0.1      2     5
Waiting:        2     2    0.1      2     5
Total:          2     2    0.1      2     5
WARING: The median and mean for the processing time are not within a normal deviation
        These results are propably not that reliable.
WARING: The median and mean for the total time are not within a normal deviation
        These results are propably not that reliable.

Percentage of the requests served within a certain time (ms)
  50%      2
  66%      2
  75%      2
  80%      2
  90%      3
  95%      3
  98%      3
  99%      3
 100%      5 (last request)

대략적으로 이해하리라고 보고, 궁금한 것은 질문하세요.

 

2. ab 활용하기

ab 결과 화면에 내용과 줄이 많기 때문에 손쉽게 비교하기가 쉽지 않다. 다양한 조건을 넣어가면서 테스트를 하면 그 내용을 정리하기가 쉽지 않다. 특히 벤치마크 테스트에서는 동시에 접속하는 클라이언트 숫자에 따라 결과가 많이 달라진다. 조건을 다양하게 바꾸면서 테스트하면 그 출력 결과를 분석하고 정리하기가 쉽지 않다. 그래서 클라이언트 접속 숫자를 바꾸면서 동일한 조건으로 테스트하고 그 결과를 출력하는 스크립트를 만들어 사용한다.

#!/bin/sh

if [ $# -lt 5 ]; then
  echo "abstress.sh <url> <time> <start> <max> <inc>"
  echo ""
  exit 1
fi

url=$1
tt=$2
start=$3
max=$4
inc=$5

num=$start

while true
do
  /usr/local/apache/bin/ab -t $tt -c $num $url 2>/dev/null > $$

  tps=`cat $$ | grep Requests\ per\ second: | awk '{print $4;exit;}'`
  echo "$num $tps"
  num=`expr $num + $inc`
  if [ $num -gt $max ];then
    exit;
  fi
  sleep 10
done
abstress.sh <url> <time> <start> <max> <inc>
./abstress.sh http://localhost/ 5 10 20 5

스크립트를 실행하면 다음과 같은 화면이 출력된다.

100 326.01
150 323.32
200 304.53

동시 접속을 100, 150, 200 으로 바꿔 가면서 테스트한 결과이다.

 

3. ab 로 벤치마크 계획하기

벤치마크를 하기 위해서는 우선 비교 가능한 시스템이 있어야 한다. 각 시스템은 하드웨어 사양은 다른 것이 좋으며, 어플리케이션 설치는 동일한 조건과 옵션을 가지는 것이 좋다. 벤치마크를 수행하는 도중에는 외부로부터 간섭이 발생하지 않게끔 해야 한다.
벤치마크를 하려면 비교할 웹 프로그램을 설정해야 한다. 가장 이상적인 상태와 가장 문제가 있는 상태까지 각 구간을 나누어서 테스트를 한다.

웹에서 벤치마크를 하려면 제일 먼저 웹 서버가 보통 가지는 능력을 테스트한다. 가장 좋은 방법은 정적인 HTML을 다양하게 테스트해본다.
그 다음으로 php를 사용한다면 echo 만 있는 php를 테스트한다. 이후에는 include 가 어느 정도 있는 경우와 심하게 있는 경우로 나누어서 내부적인 캐싱과 파일 include 능력을 테스트한다.
php에서는 소스 라인수가 특정 규모를 넘어가면 속도가 느려지는 현상이 있는데, 이에 대해서 의미없는 소스라인을 100, 500, 1000, 5000, 10000 정도 나누어서 테스트한다.
DB 와 연결하는 테스트도 중요하다. 만약 postgres를 사용한다면 postgres와 pgpool 모두를 테스트해본다. 각자 단지 connect, close만 하는 경우를 테스트한다. 그리고 select, insert, update, stored procedure 를 이용하는 경우를 나누어서 테스트한다.
이 정도 테스트를 하고 나면 이제 실제 웹 프로그램을 호출하는 테스트를 한다. 웹 프로그램은 보통 메인 페이지와 속도가 느리다고 판단되는 페이지를 몇개 선정해 본다. 각 페이지에서 SQL 문만 빼내서 별도의 웹 프로그램으로 만든 후 각 비교하는 것도 좋다.

분석은 엑셀이 매우 좋다. 파일 업로드가 되면 엑셀로 나온 결과 값을 올려보겠다.

목차
 1. 검색엔진의 역사    6
 2. 정보검색시스템의 구성요소    8
 2.1. 정보검색시스템이란?    8
 2.2. 배경학문    8
 2.3. 구성요소    8
 3. 검색 기법    13
 3.1. Exact match techniques(완전일치 기법)    13
 3.2. Partial match techniques(부분일치 기법)    13
 3.3. Network(네트워크 모델)    15
 3.4. Feedback Methods(피드백 기법)     16
 4. 검색엔진 구조도    18
 5. 색인기 구조도    20
 6. 검색기 구조    23
 7. 웹 로봇을 개발하자 - 개요    24
 7.1. 개요    25
 7.2. 웹 로봇의 구성요소    26
 8. 웹 로봇을 개발하자 ? HTML Parser    28
 9. 웹 로봇을 개발하자 - HTTP 프로토콜에 대해    38
 9.1. HTTP 명세    38
 9.2. Telnet을 이용한 HTTP 응답 확인    43
 10. 웹 로봇을 개발하자 - 소켓 프로그래밍    45
 11. 웹 로봇을 개발하자 - 로봇 배제 표준    49
 11.1. 검색엔진에서 내 홈페이지가 검색당하지 않도록 쓰는 방법    49
 11.2. robots.txt 작성방법    49
 12. 웹 로봇을 개발하자 - 기본 자료구조    52
 12.1. dynamic array    52
 12.2. array-base tree    56
 12.3. array-based trie    58
 13. 웹 로봇을 개발하자 - 소켓 타임아웃에 대해    62
 13.1. 필요성     62
 13.2. 정책     63
 13.3. 방법은?     63
 14. 웹 로봇을 개발하자 - 멀티 쓰레드 로봇    68
 14.1. 화면 설명    68
 14.2. 기본 자료구조    69
 14.3. 수집 시작 루틴    72
 14.4. 쓰래드 처리    75
 14.5. 대용량 웹 로봇을 위해서는?    78
 15. 웹 로봇을 개발하자 - 대용량 웹 로봇 설계    80
 15.1. 전체 시스템 구조    80
 15.2. group table    80
 15.3. newurl table    81
 15.4. timeout table    82
 15.5. thread info    82
 15.6. host policy    83
 15.7. type1 (main thread)    83
 15.8. type2 (normal processing thread)    83
 15.9. type3 (timed out processing thread)    84
 15.10. type4 (alarm thread)    84
 15.11. type5 (robot communication thread)    84
 15.12. type6 (management thread)    85
 15.13. 기타    85
 15.14. Group Table 구조    85
 15.15. UrlTree 구조    85
 15.16. DNS    85
 15.17. DNS Protocol    87
 15.18. 2차 로봇    92
 16. 검색엔진 개발 실습    94
 17. 엔진 개발 실습 -모델링    95
 17.1. 개요    95
 17.2. 순위부여 모델과 실험    95
 17.3. 벡터 공간 모델    96
 18. 엔진 개발 실습 - Term Weight에 대하여    98
 18.1. 문서의 중요도    98
 18.2. 문서를 어떻게 수치화할 것인가?    99
 18.3. 텀의 가중치를 어떻게 계산하는가?    99
 18.4. 문헌의 가중치는?    101
 18.5. 용어 정리    101
 19. 형태소 분석    102
 20. 엔진개발 실습 - 색인 DB 구조 #1    103
 20.1. 색인 DB란 무엇인가?    103
 20.2. 무엇을 색인 DB화 할 것인가?    103
 20.3. 어떻게 구축할 것인가?    105
 21. 엔진개발 실습 - 색인 DB 구조 #2    109
 21.1. 어떻게 구축할 것인가.    109
 21.2. 확장된 검색기능을 제공하기 위한 DB 구축 방법은?    112
 21.3. 기타    113
 22. 엔진개발 실습 - 메모리 관리정책    115
 22.1. 메모리에 상주시킬 데이터들은?    115
 22.2. 쓰래드들이 사용할 메모리는?    117
 22.3. 메모리로 캐시를 구축할 것인가?    118
 23. 엔진개발 실습 ? 논리 연산 처리방법    119
 23.1. 기본 개념    119
 23.2. 입력되는 질의 형태    120
 23.3. 질의 파싱 및 보정    121
 23.4. 결과 처리    123
 24. 엔진개발 실습 ? 빠른 논리 연산방법    124
 24.1. 논리 연산 시 비교 방법들    124
 24.2. 해시 테이블을 사용한 비교 방법    125
 24.3. 포스팅 파일을 어떻게 구축할 것인가?    125
 24.4. 그 외의 고려사항    126
 25. 엔진개발 실습 - 빠른 소팅 방법    127
 25.1. min-heap을 사용한 소팅 방법    127
 25.2. Sorted Map에 대하여    128
 25.3. 결론    130
 26. 동적색인 시스템 구성에 대해    132
 27. 동적 색인 시스템 개요    133
 27.1. 동적 색인 시스템이란?    133
 27.2. 색인 시스템의 분류    133
 27.3. 동적 색인 시스템의 주요 이슈    134
 27.4. 발전 방향    135
 28. 파일 시스템 구축 ? 개요    136
 28.1. 왜 파일 시스템을 구축해야 하는가?    136
 28.2. 파일 시스템 구조    136
 28.3. Level 0 : Physical I/O Layer    138
 28.4. Level 1 : Buffer Manager    139
 28.5. Level 2 : Storage Structures    139
 28.6. Level 3 : Access Methods    140
 28.7. 시스템 평가    140
 28.8. 향후 계획    140
 29. 파일 시스템 구축 - #1 볼륨 구조    141
 29.1. 개요    141
 29.2. 볼륨의 기본 구조    142
 29.3. 볼륨 헤더의 데이터 구조    144
 29.4. 구현 알고리즘    146
 29.5. 향후 계획    150
 30. 파일 시스템 구축 - #2 버퍼 구조    151
 30.1. 개요    151
 30.2. 버퍼의 데이터 구조    151
 30.3. 버퍼 운영 정책    152
 30.4. 구현 알고리즘    153
 30.5. 향후 계획    157
 31. 동적색인에 대해서 #1    158
 32. 검색엔진에 압축은 필수?    160
 33. 파일 시스템 구축 - #3 디렉토리 구조    162
 33.1. 개요    162
 33.2. 디렉토리 페이지 구조    163
 33.3. Trie 페이지 구성    164
 33.4. 파일 디스크립터 페이지 구성    164
 33.5. 메모리 구조    165
 33.6. 파일 생성 절차    167
 33.7. 파일 소멸 절차    167
 33.8. 향후 계획    168
 34. 파일 시스템 구축 - #4 인덱스 파일 구조    169
 34.1. 개요    169
 34.2. 인덱스 파일의 내부 구조    169
 34.3. 루트 페이지 구조    170
 34.4. 노드 페이지 구조    172
 34.5. 리프 페이지 구조    172
 34.6. 구현 알고리즘     173
 34.7. 향후 계획    179
 35. 파일 시스템 구축 - #5 바이너리 파일 구조    180
 35.1. 개요    180
 35.2. 바이너리 파일의 내부 구조    180
 35.3. 바이트 파일에 데이터 쓰기    182
 35.4. 응용    184