4.1 직렬/병렬
4.1.1 직렬 병렬이란?
대규모 웹 서비스는 방대한 수의 사용자 요청을 처리해야 하므로 수많은 서버를 배치해서 병렬로 처리하고 있음을 알 수 있다. 주변에 병렬로 처리하는 경우가 많지만 무조건 병렬로 처리한다고 해서 성능이 향상되는 것은 아니다.
예) 여러 개의 물건이 일직선으로 나열돼 있는 것을 직렬, 두 줄 이상으로 나열돼 있는 것을 병렬이라고 한다.
위 그림에서 3차선 도로가 도중에 합류해서 1차선이 되고, 다시 3차선으로 분기하고 있다. 합류점부터 시작되는 1차산 구간은 혼잡해지기 쉽고 사고가 발생하기 쉽다. 1차선 구간은 전체 흐름을 느리게 만드는 병목 지점 이 된다. 이러한 혼잡상황을 해결하는 방법으로는 1차선 구간을 3차선으로 만드는 것이다. 이것은 컴퓨터 세계에서도 마찬가지이다.
특정기간 내에 하나의 CPU로 처리할 수 있는 양에는 한계가 있지만 여러 개의 CPU를 배치하면 처리량을 늘릴 수 있다. 단 다수의 CPU를 이용할 수 있는 처리여야 한다는 전제 조건이 있다. 분담해서 병렬화할 수 없는 처리는 CPU 코어를 아무리 늘려도 효과가 없다. 병렬 처리에서는 합류점, 직렬화 구간, 분기점이 병목지점이 되기 싶다. 병렬 처리를 할 때는 가능한 한 병렬화해서 직렬 부분을 줄이고 어쩔 수 없이 직렬화해야 하는 경우에는 효율성을 높이는 것이 중요하다. 또 병렬화에서는 분담해서 일을 진행한 것을 다시 한 곳에 모으는 데 오버헤드가 걸린다. 무리해서 병렬화하면 직렬 처리에 의해 속도가 느려질 수 있다.
4.1.2 어디에 사용되나?
웹 서버와 AP 서버에서의 병렬화
웹 서버에서는 다수의 이용자가 접속하기 때문에 복수의 프로세스가 분담해서 병렬 처리를 하고 있다. AP 서버에서는 JVM 프로세스가 하나이지만 복수의 스레드가 병렬로 처리하고 있다. Apach HTTP Server에서는 멀티 프로세스 모델 외에도 멀티 프로세스와 멀티 스레드를 모두 이용하는 하이브리드형도 있다.
아파치는 1프로세스 1스레드, JVM은 1프로세스 4 스레드이지만 하나의 CPU 코어를 동시에 사용할 수 있는 것은 1스레드다. 예) 하나의 CPU 코어 밖에 없는 서버에서는 아파치 프로세스를 아무리 늘려도 동시에 실행할 수 있는 것은 1프로세스뿐이다. 프로세스나 스레드 수를 조정할 때는 CPU 코어 수도 함께 고려해야 한다
DB 서버에서의 병렬화
오라클 DB에서는 클라이언트 요청을 접수하는 서버 프로세스가 클라이언트 접속 수만큼 생성된다. 서버 프로세스에는 공유 서버형이라 불리는 하이브리드형도 있어서 멀티 프로세스, 멀티 스레드를 모두 사용할 수 있다. 또 데이터 파일 생성 시 병목 현상이 발생하는 경우 메모리에 캐시된 갱신 완료 데이터를 HDD에 기록하는 DBWR 프로세스 수를 늘려서 병렬화할 수도 있다. 그 외에도 비동기 I/O를 사용해서 OS 측에서 쓰기 처리를 병렬화하는 방법도 있다.
4.1.3 정리
| 직렬 | 병렬 | |
|---|---|---|
| 장점 | 구조가 간단, 설계 구현 난이도가 낮음 | 복수의 리소스를 유용하게 이용가능, 동일 시간당 처리할 수 있는 양 증가 |
| 단점 | 복수의 리소스를 유용하게 이용할 수 없음 | 오버헤드 발생, 구조가 복잡해서 설계 구현 난이도 증가 |
[병렬화시 주의점]
- 직렬 처리 성능은 향상되지 않지만 단위 시간당 처리량을 늘릴 수 있다.
- 합류점, 직렬화 구간, 분기점이 병목 지점이 되기 쉽다.
- 병렬화가 유효한 부분을 파악해서 병렬화하지 않으면 효과가 없다. 오버헤드, 구조 복잡성 등의 단점을 고려하고 단점 이상의 효과를 얻을 수 있는 경우 병렬화한다.
4.2 동기/비동기
4.2.1 동기/비동기란?
누군가에게 일을 부탁하고 그 일이 끝나기까지 잠자코 기다리는 것이 동기, 끝나면 말해 라고 말해두고 다른 일을 하는 것이 비동기다.
[특징]
- 동기는 일이 끝날 때까지 아무것도 하지 않고 기다리기 때문에 그 사이에 다른 일을 할 수 없다. 하지만 일이 끝났는지 여부를 확실하게 확인할 수 있다.
- 비동기는 끝날 때까지 기다리지 않기 때문에 병렬로 다른 일을 할 수 있다. 하지만 일이 끝났는지 여부 확인은 별도의 방법을 이용해야 한다.
4.2.2 어디에 사용되나?
Ajax를 사용하면 비동기 통신을 이용한 병렬 처리가 가능하다. Ajax를 사용한 웹 페이지에서는 비동기 통신이 가능해져서 화면을 보거나 입력하면서 필요한 부분만 갱신할 수 있게 됐다.
예) 구글에 검색어를 일부 입력하면 검색어 후보가 표시된다 -> 구글 검색 엔진 서버에 전송해서 키워드 후보 데이터를 얻어 브라우저에 표시
DBMS에서 사용되는 비동기 I/O : DBMS는 HDD 등의 저장소에 비동기로 쓰기 처리를 할 수 있다. 이것을 비동기 I/O라고 한다. 공유 메모리에 있는 다수의 데이터를 프로세스가 HDD에 기록하는 경우, 비동기 I/O라면 하나의 I/O가 끝나기까지 기다리지 않고 다음 I/O를 발행할 수 있기 때문에 저장소 성능을 충분히 활용할 수 있다. DBMS에서 비동기로 처리하면 쓰기가 끝났는지 확인하지 않고 다음 처리를 진행해서 위험하지 않는지 걱정할 수 있다. DBMS에서는 비동기로 I/O를 요구한 후에 I/O가 끝났는지 여부를 확인하고 있다.
4.2.3 정리
비동기의 본질은 병렬이다. 비동기를 사용시 주의할 점은 처리가 끝나지 않은 상태에서 다른 처리를 진행해도 문제가 없는가, 처리가 끝났는지 확인할 필요가 있는가를 고려해야한다.
4.3 큐
4.3.1 큐란?
Queue는 우리말로 대기 행렬이라 표현할 수 있다. 컴퓨터 세계에서는 여러 곳에 행렬이 존재하고, 하드웨어, OS, 데이터베이스, 애플리케이션 등 거의 모든 곳에서 이 구조가 사용되고 있어 설계나 성능 튜닝 시에 빠질 수 없는 지식이라 할 수 있다. 그리고 큐는 FIFO 구조로 먼저 들어온 요청이 차례대로 처리된다.
4.3.2 어디에 사용되나?
- CPU 처리를 기다리고 있는 프로세스나 스레드 행렬
- 하드 디스크 등의 저장소 읽기 처리를 기다리고 있는 I/O 요구 행렬
- 네트워크 접속 성립을 기다리고 있는 접속 요구 행렬
컴퓨터에서 CPU를 기다리고 있는 프로세스 행렬을 Run Queue라고 한다. 참고로 CPU에서 처리 중인 프로세스를 런큐로 인식할지는 OS 종류에 따라 달라진다.
데이터베이스의 디스크 I/O
프로세스나 스레드가 사용하는 대상이 HDD라는 점이 CPU와 다르다.
오라클 DB의 동작을 보면 두 개의 서버 프로세스와 DBWR 프로세스는 왼쪽 HDD에 I/O를 실시하고 있고, LGWR 프로세스는 오른쪽 HDD에 I/O를 실시하고 있다. 전자는 왼쪽 HDD 데이터에 액세스하고, 후자는 오른쪽 HDD에 액세스 한다. HDD는 데이터가 기록돼 있는 특정 위치에 액세스해야 하기 때문에 CPU처럼 비어 있다는 이유로 다른 것을 사용할 수 없다. 이 점이 HDD와 CPU의 차이점이다.
4.3.3 정리
큐의 특징은 선두에서부터 순서대로 처리된다는 점이다. 여러 처리가 동시에 진행되는 경우에 이 큐가 자주 사용되며 다양한 계층의 여러 부분에서 이 큐가 이용되고 있다.
CPU나 저장소와 같이 복수의 처리가 동시에 진행되는 부분에서는 큐를 많이 이용하기 때문에 성능 문제가 발생하기 쉽다. 성능 문제가 발생하면 큐의 길이(행렬의 길이)를 확인하는 것이 중요하다.
4.4 배타적 제어
4.4.1 배타적 제어란?
배타적 제어는 다른 것을 배제하는 제어다. 여러 사람이 공유하는 물건일 경우 누군가가 그 물건을 사용하고 있으면 다른 사람은 그것을 사용할 수 없다. 컴퓨터 세계에서는 직렬 처리에서는 배타적 제어가 필요 없지만 병렬 처리에서는 필요하다. 배타적 제어를 하는 부분은 병목 현상이 발생하기 쉽다.
예) 회의를 하고 있을 때 회의실 안내문을 ‘사용중’ 이라고 해 두어 다른 사람이 사용할 수 없다는 것을 알린다. 반대로 회의가 끝나면 안내문을 ‘공실’로 바꿔서 다른 사람이 이용할 수 있게 한다. 이것이 바로 배타적 제어다.
일반적으로 OS나 DBMS는 병렬 처리를 위해 배타적 제어를 사용한다. 그리고 병렬 처리 관련 성능 문제에 배타적 제어가 영향을 주는 경우가 꽤 있다. 병렬 처리시 서로 관계없는 동작시에는 필요없지만 대부분 공유 데이터를 이용하고 부분적으로 직렬 처리를 사용해야 하는 경우에 배타적 제어가 필요하다.
- 복수 처리가 공유 자원에 동시에 액세스하면 불일치가 발생할 수 있어 배타적 제어로 보호해 주어야 한다.
- 배타적 제어에서는 특정 처리가 공유 자원을 이용하고 있는 동안 다른 처리가 이용할 수 없게 해서 불일치가 발생하지 않도록 한다.
4.4.2 어디에 사용되나?
DBMS에 사용되는 배타적 제어
오라클 DB에서는 여러 프로세스가 동시에 병행으로 처리를 하고 있지만, 특정 프로세스가 공유 데이터를 변경하고 있는 도중 다른 프로세스가 해당 공유 데이터를 읽거나 동시에 변경하지 못하도록 배타적 제어를 하고 있다. 배타적 제어에는 짧은 시간 동안만 락을 유지하는 래치라는 것이 있어 CPU에서 의미가 없는 처리를 하면서 대기하는 방식이 있다.(스핀락), 또 장시간 락을 유지하도록 큐를 이용해서 관리하는 방식인 슬립락이라는 것도 있다.
OS 커널에 사용되는 배타적 제어
리눅스 커널은 빅 커널락(BKL)이라 불리는 하나의 스핀락으로 유지된다. BKL이 이용되는 부분에서는 처리가 직렬화돼서 동시에 하나의 CPU만 커널 코드를 실행할 수 있다. 따라서 이 부분이 병목 지점이 되기 쉽다. 컴퓨터가 여러 CPU를 활용해서 병렬 실행 가능한 처리를 늘리기 위해 리눅스 커널에서는 BKL로 보호된 커널 코드를 수정했다.
4.4.3 정리
[배타적 제어의 장단점]
| 배타적 제어를 사용하는 경우 | 배타적 제어를 사용하지 않는 경우 | |
|---|---|---|
| 장점 | 공유 데이터의 일관성을 유지할 수 있다 | 병렬로 빠르게 처리할 수 있다 |
| 단점 | 병렬 처리가 안 된다 | 데이터 불일치가 발생할 가능성이 있다 |
4.5 상태 저장/상태 비저장
4.5.1 상태 저장/상태 비저장이란?
정보를 많이 가지고 있는 상태 저장은 세분화된 제어가 가능한 반면에 구조가 복잡하다. 반면 상태 비저장은 고기능은 아니지만 간단하다.
4.5.2 자세히 살펴보자
상태 저장은 부여된 정보에 따라 상태가 전이된다. 이점은 과거 정보를 가져올 수 있어서 정보에 따른 복잡한 처리를할 수 있다는 것이다. 단점은 약간이나마 시스템 복잡성이 커진다.
상태 비저장의 장점은 구조가 간단하다는 것이다. 이런 구조 때문에 성능이나 안정성을 쉽게 향상시킬 수 있다. 단점으로는 복잡한 처리가 어렵다는 점이 있다.
4.5.3 어디에 사용되나?
컴퓨터 내부구조
컴퓨터 내에서는 거의 모든 것에 상태 저장이 사용되고 있다.
네트워크 통신구조
HTTP는 기본적으로 상태 비저장 프로토콜이다. 따라서 매번 같은 데이터를 반환한다. 그래서 HTTP에서는 세션이라는 개념을 사용해서 상태유지 구조를 구현하고 있다.
4.6 가변길이/고정길이
4.6.1 가변길이/고정길이란?
데이터를 저장할 때 해당 데이터를 담을 상자의 크기가 정해져 있는지 여부가 매우 중요하다. 이때 미리 크기가 정해져 있는 경우를 고정 길이, 정해져 있지 않은 경우를 가변 길이라고 한다.
- 가변 길이는 공간을 유용하게 활용할 수 있지만 성능 면에서는 불안정하다. 또 원하는 데이터를 찾으려면 고정 길이에 비해 많은 시간이 걸린다.
- 고정 길이는 쓸데없는 공간이 생기지만 성능 면에서는 안정적이다. 또 크기가 정해져 있어 원하는 것에 쉽게 액세스할 수 있다.
4.6.2 어디에 사용되나?
윈도우즈에는 일반적으로 NTFS라 불리는 파일 시스템이 사용되고 있는데 이 파일 시스템에서는 각종 파일을 고정 길이로 저장하고 있다. 예) memo.txt 는 크기 12byte, 디스크 할당 크기 4096byte 라고 표시된다. 이것은 실제로 12byte 데이터이지만 저장시에는 4096byte를 사용하고 있다는 것을 의미한다.
네트워크는 데이터를 교환할 때 일반적인 이더넷은 1500byte로 TCP/IP 헤더 합계가 40byte이기 때문에 MSS는 1460byte가 된다. 그래서 TCP/IP로 데이터를 전송시 1460byte 정도의 세그먼트로 분할하고, 마지막 남은 것은 1~1460byte 크기로 전송된다.
4.6.3 정리
가변 길이는 데이터 크기를 매번 변경하기 때문에 데이터 전체 양이 줄어든다는 장점이 있으며, 고정 길이는 모두 같은 크기를 이용해서 처리한다. 크기가 균일하기 때문에 관리가 수월하다는 장점이 있다.
4.7 데이터 구조(배열과 연결 리스트)
4.7.1 데이터 구조(배열과 연결 리스트)란?
배열과 연결 리스트는 모두 데이터를 순차적으로 처리하는 구조이지만 구조가 다르기 때문에 성능 측면의 특징도 많이 다르다.
[특징]
- 배열은 데이터를 빈틈없이 순서대로 나열한 데이터 구조
- 연결 리스트는 데이터를 선으로 연결한 데이터 구조
- 탐색이 빠른 것은 배열이고, 느린 것은 연결 리스트
- 데이터 추가, 삭제가 빠른 것은 연결 리스트, 느린 것은 배열
4.7.2 어디에 사용되나?
해시 테이블 구현에는 배열과 연결 리스트가 사용되고 있다. 데이터 추가, 삭제가 빠른 연결 리스트와 탐색이 빠른 배열을 조합한 하이브리드형 데이터 구조가 해시 테이블이다.
예) 오라클 DB에서 SQL을 실행하면 SQL을 Parse한 후 실행해서 결과를 반환하지만 한번 실행된 SQL 관련 정보는 메모리에 저장된다. 그리고 똑같은 SQL이 실행되는 경우 처음부터 파스하는 것이 아니라 이전 실행 시의 정보를 재사용한다. 이렇게 SQL 관련 정보를 관리할 때 사용하는 것이 해시 테이블 구조다. 파스한 SQL을 재사용함으로써 CPU 사용 시간을 절약할 수 있다.
처음 실행된 SQL은 파스를 거쳐 실행된 후에도 메모리에 남는다. 똑같은 SQL이 실행되면 메모리에 있는 것이 재사용된다. 그리고 메모리가 부족하면 실행되고 있지 않은 SQL을 해제한다.
4.7.3 정리
| 배열 | 연결리스트 | |
|---|---|---|
| 장점 | N번째 요소 탐색이 빠르다 | 데이터 추가, 삭제가 빠르다 |
| 단점 | 데이터 추가, 삭제가 느리다 | N번째 요소 탐색이 느리다 |
해시 테이블은 배열과 연결 리스트의 상호 장점만 조합해서 약점을 보완한 데이터 구조라고 할 수 있다. 이외에도 Queue, Stack 등의 데이터 구조도 배열이나 연결 리스트로 구현돼 있다.
4.8 탐색 알고리즘(해시/트리 등)
4.8.1 탐색 알고리즘(해시/트리 등)이란?
책이나 사전에서 무언가를 찾을 때 원하는 키워드를 알고 있으면 색인을 찾거나 특정 주제에 대해 읽고 싶다면 차례를 찾거나 할 것이다. 만약 차례나 색인이 없다면 특정 페이지를 찾기 위해 모든 페이지를 열어봐야 하기 때문에 엄청난 노력이 필요하다.
컴퓨터에서도 데이터를 찾기 쉽도록 정리해 두면 원하는 데이터를 빨리 찾을 수 있다. 데이터 정리 방법을 ‘데이터 구조’, 찾는 방법을 ‘탐색 알고리즘’이라고 한다.
4.8.2 어디에 사용되나?
DBMS에서 SQL 튜닝시에 full scan으로 되어 있어 느린데 인덱스를 생성해서 index scan을 하니깐 빨라졌다는 이야기를 들어봤을 것이다.
인덱스가 없는 경우
SQL을 발행해서 한 건의 데이터를 취득하는 경우라도 인덱스가 없으면 디스크에서 테이블 데이터를 모두 읽어서 조사해야 한다.(full scan)
인덱스가 있는 경우
인덱스가 있으면 최소한의 필요 블록만 읽으면 된다. 인덱스가 있다고 무조건 좋은 것은 아니다. 검색이 빨라지는 대신 데이터의 추가, 갱신, 삭제 시에 테이블뿐만 아니라 인덱스 데이터도 갱신해야 한다.
인덱스의 구조 - B 트리 인덱스
DBMS의 풀 스캔은 색인을 보지 않고 책을 처음부터 읽어가는 것과 같다. 인덱스 스캔을 통한 모든 데이터 취득은 책을 처음부터 읽지만 색인을 보면서 읽어나가는 것이다.
B 트리 인덱스가 DBMS에서 자주 사용되는 것은 트리 구조 계층이 깊어지지 않도록 디스크 I/O를 최소한으로 제어하기 때문이다.
해시 테이블
해시 테이블은 등포 검색에 큰 강점을 보인다. 해시 테이블은 키와 값 조합으로 표를 구성한 데이터 구성이다. 키는 해시 함수를 통해 해시 값으로 변환된다. 해시 값은 고정 길이 데이터라 조합 표의 데이터 구조가 간단해서 검색이 빠르다는 장점이 있다. 그리고 아무리 데이터 양이 많아진다고 해도 기본적인 등호 검색의 속도는 변하지 않는다. 하지만 범위 검색이 약하다는 문제가 있다.
4.8.3 정리
등호 검색에 강한 해시 테이블을 사용한 탐색, 등호 검색과 범위 검색에도 강한 만능형 B 트리등이 있다.
full scan 처럼 100건의 데이터가 있을 때 100건 모두 보는 것을 선형 탐색이라고 한다.
또 HDD 같은 2차 기록 장치의 데이터 탐색에 적합한 B트리와 메모리의 데이터 탐색에 적합한 T트리 등이 있어 데이터 저장 장치에 따라서 데이터 구조도 달라진다.