c10k 문제..

참고 : http://www.kegel.com/c10k.html , https://en.wikipedia.org/wiki/Continuation , https://en.wikipedia.org/wiki/Green_threads , https://en.wikipedia.org/wiki/State_machine_replication , https://en.wikipedia.org/wiki/VxD , http://www.cyberciti.biz/faq/linux-increase-the-maximum-number-of-open-files/ , http://stackoverflow.com/questions/5635362/max-thread-per-process-in-linux , http://www.lowtek.com/sockets/select.html , https://en.wikipedia.org/wiki/Zero-copy

머신의 성능이 충분해진 시대에 10000개의 클라이언트에 어떻게 서비스를 제공할 것인가에 대한 질문에서 출발한 이야기인데.. 참고 사이트는 사실 꽤 오래전 이야기에 시스템 레벨에서의 I/O최적화에 대한 히스토리를 주로 모아뒀고 OS나 서버사이드 어플리케이션들에 오랬동안 논의 되었던 해결책들이 하나둘씩 적용되고 있으며 또한 이미 사용되고 있다.

요즘같이 스케일아웃 솔루션들이 잘 나와있는 시대에는 별 의미 없는 이야기 일 것 같아 보이기도 하지만 전체 시스템의 I/O 응답성을 높이기 위해 한번쯤 생각해 볼만한 주제인 것 같아 간단히 정리해 보기로 하였다.

I/O 전략

네트워킹 소프트웨어 디자이너를 위한 몇가지 옵션들..

• 단일 쓰레드에서 다중 I/O 호출 발행 여부와 어떻게 발행할 것인지에 대해
• 다중 쓰레드나 동시성을 얻을 수 있는 프로세스를 사용할 수 있는 곳에 블러킹/동기식 호출 사용하지 않기.
• I/O 시작에 넌블러킹 호출을 사용하고 해당 채널에서 다음 I/O를 시작할 준비가 되었음을 알 수 있는 준비 알림 사용하기. 일반적으로 디스크 I/O가 아닌 네트워크 I/O에 유효함.
• I/O 시작에 비동기 호출을 사용하고 I/O가 끝났을 때 완료 알림 사용하기. 네트워크와 디스크 I/O 모두에 유효함.
• 개별 클라이언트에 대해 서비스를 어떻게 제어할 것인지에 대해
• 각각의 클라이언트에 하나의 프로세스 할당(고전적인 유닉스 접근방식, fork()와 같은..)
• 단일 OS 레벨 쓰레드가 다수의 클라이언트에 서비스를 제공하는 경우. 각 클라이언트는 다음에 의해 컨트롤 됨
• 사용자 레벨 쓰레드(GNU 상태 쓰레드나 Green 쓰레드를 사용하는 Java) - Green 쓰레드는 커널 레벨이 아닌 VM 레벨에서 동작하며 단일 코어 CPU를 사용할때 유효한 방식이라 JVM 1.3 이후에는 사용되지 않고 있습니다.
• 상태 머신 - 복제된 다수의 서버를 이용한 분산 시스템
• 컨티뉴에이션 - 최근 유행하기 시작한 펑셔널프로그래밍의 비동기 프로그래밍 기법
• 각각의 클라이언트에 하나의 OS 레벨 쓰레드 할당(네이티브 쓰레드를 사용하는 Java)
• 각각의 활성 상태의 클라이언트에 OS 레벨 쓰레드 할당(아파치 프론트엔드와 함께 Tomcat을 사용하거나 NT의 I/O completion port나 쓰레드풀을 사용)
• 표준 커널 서비스를 사용하거나 일부 코드를 커널에 포함시키는 방법(커스텀 드라이버, 커널 모듈 혹은 VxD - Virtual xxx Driver)

인기있어 보이는 몇가지 조합

쓰레드별로 다수의 클라이언트를 처리하며 넌블러킹 I/O와 함께 참조할 파일 디스크립터의 대기 상태를 select()나 poll()을 이용해 물어 처리(level triggered)하는 방식이 있는데 디스크 I/O가 블러킹 모드를 사용할 경우 병목이 발생할 수 있다.

파일 디스크립터의 대기 상태 변화시 알림을 받는 형태(edge triggered)로 처리하는 방법 있으며 프로그래밍 실수에 대해 관대하지 않은 방식이라 이벤트를 하나라도 놓친다면 해당 연결은 영원히 멈춘 상태가 될 수 있다.

비동기 I/O를 사용하는 경우는 큐를 이용한 신호(보통 유니크한 키값)와 값을 전달 하는 방식이며 기본적인 동작 방식은 작업이 완료된 상태 알림(edge triggered)을 받으면 큐에 담아 전달하는 형태이다.

클라이언트당 쓰레드를 할당하여 서비스를 하는 경우는 쓰레드당 사용되는 스택사이즈에 신경을 써야 하는데 메모리 비용의 문제가 발생할 수 있는 방식이다.

파일핸들러에서의 최대로 열 수 있는 파일수의 제약

최대로 열 수 있는 파일수의 제약이 있기 때문에 이런 제약에 걸린다면 OS의 설정 파일을 손봐야 할수도 있다. 리눅스의 경우 cat /proc/sys/fs/file-max를 이용해 값을 확인 할 수 있다.

쓰레드상의 제약

가상메모리를 소진시키지 않기 위해선 쓰레드당 할당된 스택의 크기에 주의할 필요가 있으다. 프로세스당 최대 쓰레드의 수가 제한되어 있으며 기본값은 시스템 메모리 크기에 따라 자동으로 계산 되며 런타임에 변경 가능하다. 리눅스의 경우 cat /proc/sys/kernel/thread-max를 이용해 값을 확인 할 수 있다. 시스템에서 쓰레드당 할당되는 메모리 묶음의 크기는 cat /proc/sys/vm/max_map_count를 이용해 확인할 수 있다. 해당 값들을 변경하게 될 경우 메모리 파편화와 오버커밋도 고려해야 하는 문제가 있다.

Java와 관련한 이슈

NIO에서 넌블러킹 I/O를 지원하고 있으니 일부 제약이 있긴 하지만 NIO를 사용할 수 있다면 사용하길 추천한다.

다른 팁들

• Zero-copy 이용하기 - CPU의 복사 시간에 낭비되는 자원을 줄여 네트웍의 효율을 높이는 방법이다. HSA 같은경우 CPU와 GPU간에 포인터를 전달할 수도 있다.
• 네트웍에서 부분 프레임만 지속적으로 보내는 상황 피하기.
• 과부하 상황에 재치있게 행동하기 - 과부하 상황에서 유입되는 접속수를 낮춤으로 퍼포먼스 양상을 개선하고 전체적인 에러율을 낮추는 방법을 선택할 수도 있다. 요즘은 유연하게 스케일 아웃을 할 수 있는 방향으로 가고 있다.
• 쓰레드별 워킹 디렉토리를 갖는 비 POSIX 쓰레드를 사용할 수 있다. FTP서버에서 이점이..
• 프로세스가 아닌 어플리케이션 레벨의 캐싱.

원문에서는 좀더 상세한 내용을 다루고 있으니 관심있는 분들은 원문을 참고하길 바라며 일부 링크의 경우는 세월이 많이 흘러 유실된 경우가 있지만 관련 자료들은 대부분 검색을 통해 확인할 수 있으니 참고하시길 바라며..

EBNF(Extended Backus-Naur Form)

참고 : http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form , http://www.w3.org/TR/REC-xml/#sec-notation

1. 정의

컴퓨터 과학에서 Extended Backus-Naur Form(EBNF)는 메타구문 표기법 중에 하나로 context-free grammar(컴퓨터 프로그래밍 언어나 다른 포멀랭귀지를 정식으로 설명하는 방법)를 표현하는데 사용되어진다. Backus-Naur Form(BNF) 메타구문 기술법의 확장형이다.

• ISO는 EBNF를 표준으로 채택함(ISO/IEC 14977)

2. 기초

EBNF는 컴퓨터 언어의 문법을 설명하는 코드로 터미널심볼과 넌터미널 생성 규칙(어떤 방식으로 터미널심볼이 규칙에 맞는 순서로 조합될 수 있는지를 통제하는 제약사항)으로 구성되어 있다. 터미널심볼의 예로 알파누메릭 문자, 문장 부호 그리고 공백 문자들을 들 수 있다.

EBNF는 생성 규칙에 있어 심볼의 시퀀스 각각을 넌터미널에 할당하는 것으로 정의하고 있다.

digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit excluding zero ;

식의 왼편에 할당된 digit은 넌터미널로 정의 되고 수직바는 선택적임을 나타내며 터미널심볼은 인용부호로 감싸지며 뒤를잇는 세미콜론은 종료문자를 나타낸다. 그러므로 digit은 0이거나 1 또는 2 또는 3.... 또는 9까지의 수가 될 수 있는 digit excluding zero이다

생성 규칙은 연속되는 터미널 또는 넌터미널을 포함하며 각각은 콤마로 구분된다.

twelve = "1" , "2" ;
two hundred one = "2" , "0" , "1" ;
three hundred twelve = "3" , twelve ;
twelve thousand two hundred one = twelve , two hundred one ;

생략되거나 반복되는 것에 대한 표현은 중괄호를 통해 나타낼 수 있다 {.....}

natural number = digit excluding zero , { digit } ;

이경우는 첫째 자리는 1-9중 하나 뒷 자리는 없을 수도 혹은 중괄호의 값(0-9의 숫자)이 임의의 자릿수 만큼 반복될 수 있는것을 나타낸다.

임의 선택은 대괄호를 통해 나타낼 수 있다 [.....] 이는 대괄호 안의 값이 단 한번 혹은 없을 수도 있다는 것을 나타낸다.

integer = "0" | [ "-" ] , natural number ;

그렇기 때문에 integer는 0이거나 -부호가 있거나 없는 natural number가 된다.

3. 심볼 테이블
 

용법	표기법
definition	=
concatenation	,
termination	;
alternation	|
option	[...]
repetition	{...}
grouping	(...)
terminal string	...
terminal string	'...'
comment	(*...*)
special sequence	?...?
exception	-

4. simple EBNF

XML의 정규문법은 simple EBNF표기법을 사용한다. 문법상 각 규칙은 형식상 하나의 심볼로 정의 되어진다.

symbol ::= expression

심볼은 정규 언어의 시작 기호인 경우 대문자 머릿글로 그렇지 않은 경우는 소문자 머릿글로 쓰여진다. 문자열이 표기된 그대로를 사용해야 할 경우 인용부호로 감싸서 표현한다. 오른 편에 표기된 식(expression)의 내부 아래에 소개될 규칙을 이용하여 단일 혹은 복수의 문자로 구성된 문자열과 매칭시키는데 사용되어진다.

#xN

N은 진수 정수이며 ISO/IEC 10646에서 정의 된 코드 포인트(예를 들자면 ASCII는 128 코드포인트로 구성되어 있고 범위는 0에서 7F까지이다)를 의미하며 식에서 표현하는 것은 N에서 정의된 문자와 일치한다.

[a-zA-Z], [#xN-#xN]

표기된 범위 내의 어떠한 문자도 포함 된다.

[abc], [#xN#xN#xN]

열거된 문자들 중 어떠한 문자라도 될 수 있고 열거형과 범위는 하나의 괄호셋으로 조합 될 수 있다.

[^a-z], [^#xN-#xN]

표기된 범위 이외의 어떠한 문자도 포함 된다.

[^abc], [^#xN#xN#xN]

열거된 문자가 아닌 어떠한 문자라도 될 수 있고 사용할 수 없는 값의 열거형과 범위는 하나의 괄호셋으로 조합 될 수 있다.

"string"

큰따옴표 안에 표기된 그대로의 문자열이 포함된다.

'string'

작은따옴표 안에 표기된 그대로의 문자열이 포함된다.

이 심볼들은 다음의 좀더 복잡한 패턴들로 조합될 수 있다. A와 B는 간단한 식들을 나타낸다.

(expression)

expression은 단위로 취급 되며 다음 리스트에 설명된 것과 같이 조합될 수 있다.

A?

A이거나 혹은 없거나; 선택적 A

A B

A에 연이어 B가 따라옴. 이 연산자는 |(alternation) 연산자보다 상위 우선순위를 갖는다; 예를 들면 A B | C D 는 (A B) | (C D)로 볼 수 있다.

A | B

A이거나 혹은 B이거나

A - B

B를 제외한 A에 해당하는 어떠한 문자

A+

단일 혹은 복수개의 A. 이 연산자(concatenation)는 |(alternation) 연산자보다 상위 우선순위를 갖는다; 예를 들면 A+ | B+는 (A+) | (B+)로 볼 수 있다.

A*

0개 이거나 혹은 복수개의 A. 이 연산자(concatenation)는 |(alternation) 연산자보다 상위 우선순위를 갖는다; 예를 들면 A* | B*는 (A*) | (B*)로 볼 수 있다.

문서 생성시 사용되는 또다른 표기법은 다음과 같다.

/* ... */

코멘트

[ wfc: ... ]

적격성 제약; XML문서의 생성과 연관된 적격의 문서(wel-formed documents)에 대한 제약 사항을 이름을 통해 판별한다. (well-formedness constraint : XML 기본 문법을 위반하지 않았는지 여부에 대한 제약)

[ vc: ...]

유효성 제약; XML문서의 생성과 연관된 유효한 문서(valid documents)에 대한 제약 사항을 이름을 통해 판별한다. (validity constraint : XML문서는 DTD에 문서에 대해 정의 되어 있는데 이것에 대한 위반 여부를 판단하는 제약)