성능 문제에는 메모리가 줄거나, I/O가 늘어나고 처리량이 늘어난다. 하지만 어떤 원인으로 발생하고 있는지 파악하지 못하고 추측많으로 튜닝하능경우가 많다. 인과 관계를 파악하기 위한 한가지 방법으로는 아키텍처를 배우는 것으로, *구조를 알면 잘못된 판단을 줄일 수 있다. 그리고 인과 관계를 논리적으로 생각하는것이 중요하다. '즉, 어떤현상으로 인해 다른 현상이 발생하는것을 설명 할 수 있는가?' 에대해 생각해 보아야한다. 예를들어, I/O가 느려지는 현상과 애플리케이션이 느려지는 현상을 발견했을떄, 애플리케이션의 처리 횟수는 동일하다. 그렇다면 I/O가 원인으로 애플리케이션이 느려진다는것을 추론한다.
- 알고리즘: 상자 안에 원하는 물건을 찾는데 걸리는 시간이 짧거나 길다 즉 이표현이 바로 '성능' 이다. 1000개의 상자가 있는데 평균 500개를 열 경우 물건을 찾을수 있다. 다른 방법으로는 순서를 정렬해두면 찾기 쉬워진다. 700이라는 숫자를 찾을떄 500을 찾고 우측에 있는걸 안다 이떄 시간복잡도는 logn 이다 n를 2로 몇번 놔눠야 1이 되냐. 이런 전략이나 방법을 '알고리즘' 이라고 한다.
- 응답(Response)과 처리량(Throughput):
- 응답이란 요청에 얼마나 빠르게 반응할수 있는지, 처리량은 처리 할 수있는 양이 많은지 의미한다.
- 처리량은 처리 할 수 있는 양이 많은지를 의미한다.
- 응답 중심은 만능이다. 응답이 빠르면 보통은 처리량도 올라가기 때문이다. 하지만 cpu 클록(clock)이나 디스크 I/O 속도에 한계가 있으므로, 그 이상 속도를 내기란 불가능하다. 하드웨어로서 성능을 향사시키기에는 제한이 있다.
이때 등하는 것이 처리량 중심 시스템이다. 동시에 사용하는 시스템에서 이 방식을 채택한다. 인터넷상의 인기 사이트는 접속이 몰려도 응답 속도가 떨어지지 않도록 설계되어있다. 동시에 대량 처리를 하는 시스템을 '처리량 중심 시스템' 이라고 한다.
개인이 사용하는 PC와 대형 서버 장비를 비교해보면 CPU 클럭 수는 그다지 차이가 나지 않지만, 가격은 수십 배에서 수백배 차이난다. 처리를 동시에 실행 할 수 있는 규모에서 발생한다. 서버장비는 CPU를 여러 개 이용해 동시에 처리할 수 있고 메모리양도 크다. 또한 버스(BUS) 라는 데이터 통과 경로를 이용해서 다수의 처리를 동시에, 고성능으로 처리할 수 있다. I/O 성능도 빠르다.
- 인라 엔지니어는 프로그래밍 경험이 없으면 전체인 구조가 보이지않아 응용이 불가능하고 결국 다 암기해버리는 오류를 범한다. 애플리케이션 엔지이너가 알고리즘을 알고 있기에 장기적으로 봤을 떄는 성장 가능성이 높다.
- 계산량 빅O표기법 O(1), 0(n), O(logn) n개 처리시 n회 반복하면 O(n);
- 트리구조는 2단계에서는 상자 세개, 상자가 네개로 어나도 한단 밖에 늘어나지않는다. 단수가 늘어날수록 상자가 증가하는 수에 비해 단수 증가가 완만해진다. 계산량은 두개씩 나누어지기 떄문에 처리할 수 있는 데이터는 배로 증가한다. 즉 2의 x이다. 반대로 계산량 증가는 2의 x승의 역이 되며, x=log2n이다. X는 증가량 n은 처리량이다.
- 트리의 장점은 데이터를 보지 않고도 처리할수 있다. 범위를 검색해도 트리에서는 일부분만 검색하면 된다.
- 트리의 단점으로는 데이터 갱신에 약하다. 삭제하고 새로운 치에 데이터를 추가할때 삭제할떄는 새로 채우지 않고 빈 상태로 놔두게 된다. 성능에 안좋은 영향을 준다. 두번쨰 단점은 같은 데이터만 계속 들어오면 한쪽 가지만 늘어난다. 검색 성능이 악화된다. 좌우 균형이 무너진다. 이경우가 흔히 'DB인덱스가 조각나있어 재구성이 필요하다' 이다.
- 개선트리로는 2분 트리가아닌 N분트리도 있다. N분 트리에서는 높이가 더 낮아지기 떄문에 효율적이다. 16분 ㅡ라리면 높이가 5면 된다. 16의 5승은 1048576이다. 메모리상에서 처리 할 수 있다면 2분 트리도 유용하지만, 디스크에 저된 데이터를 호출하려면 호출 횟수를 줄일 수 있는 N분 트리가 유리하지만 디스크에 저장된 데이터를 호출 횟수를 줄일 수있는 N분트리가 유리하다.
- B트리는 가지의 균형을 유지하는 분기 트리다. B+트리는 B트리를 변형한 것으로 트리의 끝에 달린 리프(Leaf) 노드라는 노드에만 값을 저장하는 방식이다. B*트리는 표기를 자주 접할 텐데, 이것은 리프를 리스트구조려 엮은 것 이다. B+트리나 b*트리는 db나 파일 시스템에서 자주 접하게 된다.
- 해시 알고리즘은 해시함수 %는 나눗셈의 나머지를 계산하여 그결과를 첨자로 사용한다 이 첨자가 가리키는 위치에 데이터를 저장한다.
장점은 계산량이 O(1)다. 아무리 데이터가 늘어나도 순식간에 찾는다.
단점은 치우침을 제거한다.동일 데이터에 대해서는 무력한데, 이는 동일 해시가 되기 떄문이다. 다른 데이터지만 해시 값이 같아지는데 18, 28을 10으로 나누면 첨자가 같이 8이다. 충돌(Collision)이다. 첫번쨰 방법은 리스트 구조로 나타낸다. 즉 해시를 재계산해서 다른 위치에 저장하는 방법이다.
데이터가 치우치는 현상에 주의해야한다. 어떤 테스트에서 해시 성능이 나빠 원인을 조사해 본적이 있는데. 11 21 31 41 같이 규칙성이 있을때 였다. 두번째 단점은 해시를 계산해서 배열에 데이터를 저장하는 작업이 오래걸린다 O(n)이다. 검색하기 전에 작업만으로 시간이 꾀걸려 만능 알고리즘은 아니다.
문자열이 해시 계산은 알파벳도 숫자로 바꿀수 있다. 예를 들어 컴퓨터에서는 '문자 코드'라는 숫자를 사용해서 문자를 표시한다. 문자 코드 숫자를 더해서 나머지 계산을 할수 있다.
- 스택의 장점 (FILO) : 필요한 만큼 공간을 사용하고 공간을 사용하고 공간이 단편화(데이터가 특정 공간으로 치우쳐서 저장되는상태) 되지 않는다. 처리가 끝나면 해당 영역이 비기 떄문에 연속된 빈공간이 남는다. OS가 프로그램을 실행할 떄에도 이 구조를 사용한다. 이떄문에 메모리 영역을 낭비하지 않고 여러 함수를 호출해서 처리 할수 있다.
- 퀵소트: 데이터를 하나씩 꺼내서 해당하는 링크에 넣는(삽입소트) 처리.
1~20 까지의 데이터가 배열에 들어 있다고 하자. 그중 가운데 숫자를 선택한다. 이숫자는 10이다. 배열 왼쪽에는 10보다 작은 숫자, 오른쪽은 큰 숫자가 오도록 재배열 한다. 다음은 왼쪽에 있는 숫자들에 동일한 처리를 반복한다. 이렇게하면 숫자가 깔끔하게 정렬된다. 오른쪽도 동일하게 처리하면 정렬이 된다. 퀵소트는 트리 구조를 위에서부터 만들어가는 형태이다.
계산량은 평균적으로 O(nlogn)이다. 장점으로는 데이터 검색 속도가 향상된다. 또한 소트를 통해 데이터 중복 상태도 파악 할수 있다.
단점으로는 소트 자체에 시간이 걸린다. 소트는 1회 검과 비교해서 시간이 더 걸린다. 데이터를 여러 번 검색할 필요가 있다면 의미가 있지만, 일회성 검색이라면 소트의 이점이 크지 않다. 개선에는 소트 병합(소트된 데이터를 병합해서 더 큰 소트 데이터를 만든다.)
- 캐시(Cache) 자체는 알고리즘이 아니지만, 성능에 있어 매우 중요한 기술이다. 몰래 놓아둔다의 의미이다. 성능 목적이기에 컴퓨터에서는 위치보단 빠른 속도가 중요시된다. 메인 메모리나 디스크와 이터를 교환하면 시간이 걸리기에 자주 사용하는 데이터를 가까운 곳에 두어 효율적으로 활용하기 위해서다. Cpu가 처리할떄 디스크에 접근하는것은 10밀리초 (1/1000sec), 메모리(ram)에서 처리하는것은 나노초(10억 분의 1초)가 걸린다. 데이터 1개처리당 약 (1/백만) 정도의 속도가 차이난다.
라이트 백(write back) 이라는 캐시 방식 데이터 갱신 방법이다. 데이터를 갱신할 떄, 정식 데이터는 갱신하지 않고 캐시 데이터만 갱신했다가 나중에 정식 데이터를 갱신하는 방법이다.
장점으로는 정식 데이터의 위치는 멀리 떨어져 있어서 처리 도가 느리다. 속도는 빠르고 물론 읽기 처리 캐시를 이용하면 빠르다. 단점으로는 캐시 데이터가 망가지면 정식 데이터가 오래된 테이블을 보유하고 있을 경우, 불일치가 발생 할수 있다.정식 데이터도 항상 최신 상태로 유지하고 싶다면 라이트 스루를 사용하면 된다.
무슨일이 있더라도 데이터가 소멸지 않는 캐시가 존재한다. '비휘발'이나 '배터리 백업' 등의 용어가 사용되는 캐시는 예상치 못한 정전이나 장비 고장시에도 데이터가 소멸되지 않는다. 물론 이런 기능의 캐시는 비싸다.
- 캐시(라이트 스루): 정식 데이터도 반드시 갱신해야하는 경가 있다. 시간은 걸리지만 데이터를 확실하게 갱신할수 있는 방법이다. 사라지면 곤란한 데이터라서 디스크에 확실히 저장해 두어야 한다.
장점: 캐시에 데이터가 있으면 읽기 처리가 빠르고, 쓰기 처리도 보장된다.
단점: 정식 데이터에 기록하기까지 시간이 걸리ㅔ 응답이 늦어질수 있다.
OS상에 무언가 기록한 경우 반드시 라이트 스루 상태라 할수 없다. 캐시에 임시로 저장해 ㅜ었다 중에 정식 데이터에 반영하는 경우도 있다, 이것이 OS 정지가 필요한 이유이다. 정지 시에 기록하지 않은 데이터를 디스크에 동기화한다. DBMS 로그 데이터는 소멸되어서는 안 되므로 보통 '바로작성' 상태로 되어있다. 이것이 바로 장비가 고장나도 DBMS데이터를 복구 할수 있는 이유다.
DBMS 내부 구조를 배우면 자연스럽게 알고리즘도 마스터하는것이 가능하다. 예를 들어 트리 구조는 인덱스에서 자주 사용되며, 테이블 결합에 해시를 사용하는 DBMS도 있다. 소트는 SQL 처리 시에 사용며 인덱스를 만들 떄도 필요하다. 비효율적인 애플리케이션 처리는 데이터가 필요할때 요청을 던짐 =전체 호출 횟수가 많음. Db에서는 원하는 데이터를 핀포인트로 반환하기에 효율적인 인덱스이지만, 횟수가 많아지면 이처럼 같은 위치를 계속 통과하게해 불필요한 처리가 많아짐.
- 애플리케이션 알고리즘과 DBMS알고리즘을 함께 고려해서, 가장 빠른 방법을 생각하는것이 좋다. 이것을 배치(Batch) 처리 시에 중요하다. DBMS 전문가가 되고 싶다면 알고리즘을 배우자. 튜닝이 한결 수월해 질 것이다. 애플리케이션 단에서는 하나하나의 데이터를 프로그램에 보내서 더하는 것보다 더한 후에 데이터를 프로그램에 보내는것이 효율적. DB에서는 원하는 데이터는 여기에 다 있으므로 이것을 전부 더해 주기만 하면 된다. 그러면 인덱스를 사용하지 않고도 처리 할수 있다.
*전체적으로 생각하는 습관을 기르자.
- 락과 성능:
성능에 관한 책을 보면서 항상 족하다 느낀것 락(Lock 잠금)에 대한 설명이다. 현실에서 가장 자주 발생하는 성능 문제는 락이다. DB의 레코드 락 이나 테이블락 자바락 같이 쉽게 알수있는것 뿐 아니라 CPU커멘드 레벨 락 , OS 내부락, DB 내부 락 등 보이지 않는곳에서 발생하는 락도 있다.
락은 어디까지나 특정 처리가 진행되고 있는 상태를 보호하기 위한 구조이자, 다른 처리가 끼어들지 못하도록 하는 것이다.
기본적으로 해결책은 락이 된 처리를 빨리 끝내는 것이다. DB 테이블에 락을 건 상태에서 SQL을 발행한 경우, 해당 SQL을 빨리 끝내면 락 대기시간을 줄일 수 있다. 다음은 락을 분할하는 방법이다. DB테이블에 락을 거는 것이 아니라, 레코드에 대해 락을 걸어서 SQL을 발행하면 병렬 실행이 가능하다. 이처럼 락 단위를 작게해서 대기시간을 줄일 수 있다.
- 락 구조
락 알고리즘이란 어렵다… 락 여부를 조사해서 락이 걸려있지 않느면 락한 후에 플래그를 세우면 되지 않나? 라고 생각 할수 있는데 틀린 답이다. 예를들어 A라는 프로그램과 B라는 프로그램이 거의 동시에 락 여부를 확인한다면 어떻게 될까? CPU 클록이 조금이라도 시간차를 두고 A와 B를 실행하면, 둘다 락상태라고 착각하게 된다.
- 락 시 일순간의 차이
이처럼 시점 차이로 문제가 발생하지 않도록 하기 위해서 사실 하드웨어(CPU 등) 명령을 사용하는 것이 일반적이다. 게다가 하드웨어 명령이라면 '락 상ㅌ인지 체크'와 '락 상태가 아니면 락을 건다'라는 처리가 서로 겹치지 않게 실행할수 있다. 이것이 '아토믹(Atomic, 성공 또는 실패 둘중 하나만 있는처리) 이라 하며, cpu명령을 사용함으로써 실수 없는 락을 실현할 수 있다. 일반 프로그램은 이런 CPU 명령을 직접 사용하는 것이 아니라 OS의 뮤텍스 나 자바의 싱크로나이즈드 같은 락 함수를 사용한다. Test and Set, Compare and Swap 용어공부!
- TestAndSet(Lock)이라고 하는 하드웨어 명령어 API를 이용해 Atomic operation 으로 대표적으로 Compared_and_Swap() 이있다. 처리 속도가 빠르고 쪼개질수 없록 하는 특징이 있다.