인덱스 구조 및 탐색

SQL 튜닝에서 사용되는 인덱스

인덱스 구조는 수평적 탐색과 수직적 탐색을 이룬다. 이것을 이해하고 나면 인덱스 구조에 대해 그림이 명확해진다.

인덱스를 우리가 중심적을 공부하는 이유는 SQL 튜닝에 초점이 맞쳐져있다. SQL 튜닝을 통해 원하고자 하는 데이터를 빠르게 얻기 위해서 인덱스에 대해 공부하는데 SQL을 사용하여 데이터를 찾는 방법은 이미 많이 알려진 두 가지 방식이 있다.

  • 테이블 전체 스캔
  • 인덱스를 이용

 

그럼 Table Full Scan 방식이 아닌 인덱스를 사용하기 위해 적절 한 튜닝의 핵심요소가 무엇인지 살펴보자.

만약 몸무게가 기재되어있는 학생 연명부가 있다고 가정해보자. 학생명과 몸무게로 정렬되어 있을때 학생을 찾기 위한 과정에서 학생을 찾고 몸무게 검색하는 과정이 거친다. 이런과정을 인덱스 스캔이라고 하는데, 이런 인덱스 스캔 과정에서 비용을 줄여야 한다.

그리고 만약 몸무게로만 정렬되어 있을 때 몸무게 접근 후 정렬되어 있지 않은 학생명을 찾기위해서 랜덤 I/O가 발생하는데 이런 랜덤 액세스를 최소화하도록 인덱스를 튜닝해야한다.

인덱스 스캔과 랜덤 액세스 두 가지 중 조금더 중요한 부분을 찾으라 한다면 랜덤 액세스 비용을 줄이는게 더 효율적이다.

위의 예에서 봤을때 시력을 찾아도 해당학생을 찾기위한 과정이 더 비용이 많이 들기 때문이다. 이처럼 SQL튜닝은 랜덤 I/O와의 전쟁이다.

이미지 출처 : http://www.dbguide.net/db.db?cmd=view&boardUid=148214&boardConfigUid=9&boardIdx=137&boardStep=1

 

인덱스 구조

인덱스는 대용량 테이블에서 필요한 데이터만 빠르고 효율적으로 액세스하기 위해 사용되는 오브젝트이다.

책에 주제에 대한 페이지 번호가 기재되어 있으면 필요한 내용을 빠르게 찾을 수 있는것처럼 인덱스를 이용하면 Range Scan을 사용하여 필요한 부분을 빠르게 읽을 수있다.

일반적으로 DBMS에서는 BTree 형태의 인덱스를 사용한다. 일반적으로 루트와 브랜치 블록에 있는 데이터는 하위 블록에 대한 주소값을 가지고 있으며, 이 것을 구분하는 키는 하위 블록에 저장된 키값의 범위를 나타낸다. 만약 사용자 ‘정철’ 데이터를 기준이라면 사용자 >= ‘정철’의 데이터는 우측 블록에 위치하는 것을 의미한다.

리프 블록에 저장된 각 레코드는 키값 순으로 정렬되어 있고, ROWID를 가지고 있다. 인덱스 키값이 동일할 경우 ROWID 순으로 정렬된다. ROWID는 데이터 블록주소와 로우 번호가 있기에 인덱스를 스캔하는 이유는 이 ROWID를 찾기 위해서이다. 왜냐하면 ROWID의 데이터 블록주소는 데이터 파일번호와 블록번호(데이터파일 내에서 부여한 상대적 순번)로 구성되어 있고, 로우번호(블록 내 순번)으로 구성되어 있기 때문에 데이터를 찾을 수 있기 때문이다.

 

인덱스 수직적 탐색

정렬된 인덱스 레코드 중 조건을 만족하는 첫 번째 레코드를 찾는 과정으로 인덱스 스캔 시작지점을 찾는 과정이다.

인덱스 수직적 탐색은 루트 블록에서 부터 시작한다. 각 브랜치 블록에 저장된 인덱스 레코드는 하위 블록에 대한 주소값을 가진다. 그 주소값을 이용하여 인덱스를 스캔한다.

인덱스 수직적 탐색은 찾고자 하는 값보다 크거나 같은 값을 만나면, 바로 직전 레코드가 가리키는 하위 블록으로 이동한다. 이 과정을 반복하면서 찾아가는 하위 블록에서 조건을 만족하는 첫 번째 블록을 찾아가는 과정이다.

 

인덱스 수평적 탐색

수직적 탐색을 통해 스캔 지점을 찾고나면 그 후 데이터가 더 안나타날 때까지 인덱스 리프 블록을 수평적으로 스캔한다. 즉 데이터를 찾는과정이다.

인덱스 리프 블록끼리는 서로 앞뒤 블록에 대해 주소값을 가지고 있기 때문에 수평적인 탐색이 가능하다. 이런 과정을 통해서 조건절에 만족하는 데이터를 모두 찾고 ROWID값을 얻는다.

결국 수직적 탐색은 수평적 탐색을 시작할 위치를 찾는것이고, 수평적탐색은 그렇게 찾은 위치에서 본격적으로 데이터를 찾는 작업을 시작한다.

 

결합 인덱스 구조와 탐색

두 개 이상의 컬럼을 결합해서 인덱스를 만들 수도 있다. 이런경우에도 찾고자 하는 값과 동일하거나 같은 값을 만나게 되었을 때, 하위 블록으로 이동하는 수직적 탐색을 먼저 진행한다.

만약 고객명과 성별을 하나의 인덱스로 묶어서 탐색한다고 하였을 때와 성별과 고객명으로 묶었을 때 서로 탐색하는 블록은 달라질 수 있다. 하지만 결국 블록을 탐색하는 개수는 동일하다. 서로 컬럼의 순서가 바뀔경우에 인덱스 탐색의 비용이 다를거라는 주장이 있으나 BTree의 경우 평면구조가 아니기 때문에 수직적, 수평적 탐색에서 발생하는 비용은 동일하다.

댓글()

데이터 저장 구조 및 I/O 메커니즘

데이터베이스는 디스크로 구성되어있는 데이터베이스이기 때문에 SQL 튜닝은 곧 I/O 튜닝이다. 그렇기에 기본적인 데이터의 저장 구조 및 디스크 또는 메모리를 읽는 메커니즘에 대한 정리를 먼저 해보자.


SQL 실행이 느려지는 이유

I/O가 처리되는 동안 다른 프로세스는 놀게된다. 그렇기 때문에 효율적인 프로세스 활용이 되지 못해 SQL이 느린 것이다. 왜냐하면 디스크에 접근하는 로직이 느린 경우 다른 프로세스는 계속 놀게되고 디스크 경합이 심해지기 때문이다.


데이터베이스 저장 구조

데이터베이스를 저장하려면 먼저 테이블 스페이스를 만들어야 한다. 테이블 스페이스는 테이블, 인덱스, 파티션, LOB등 여러 세그먼트를 담는 컨테이너로써 여러 개의 데이터파일로 구성된다.

각 세그먼트는 데이터 저장공간이 필요한 오브젝트이다. 그리고 그 세그먼트는 여러 익스텐트로 구성된다.익스텐트는 블록으로 구성되어 있는데, 테이블 또는 인덱스와 같은 데이터를 저장하다 공간이 부족하면 테이블 스페이스에게 요청하여 추가적으로 블록을 할당한다. 하나의 블록은 하나의 테이블이 독점한다. 즉 한 블록에 저장된 레코드는 모두 같은 테이블 레코드이다.


정리하면 이런 순서로 구성된다.

테이블 스페이스 > 세그먼트 > 익스텐트 > 블록

-> 각 블록은 한 테이블이 독점 (다중 테이블 클러스터일 경우 제외)

세그먼트 공간이 부족해졌을 때 새로운 익스텐트를 할당받는다고 했는데 그러면 그말은  익스텐트에 쓰다가 데이터 공간이 부족하면 새로운 익스텐트에 작성을 한다는 뜻으로 서로 다른 위치에 데이터가 저장된다는 뜻이다. 그렇기 때문에 이럴 경우 서로 다른 데이터 파일에 존재할 확률이 커진다. 왜냐면 테이블  스페이스는 데이터 파일로 구성되어 있는데 이는 DBMS가 파일 경합을 위해 분산시켜 놓기 때문이다.



결과적으로 그림에서 보면 알겠지만 테이블 스페이스는 크게보면 익스텐트들의 집합이다. 익스텐트들은 데이터 파일로써 분산되어 저장이된다. 그러기 때문에 익스텐트는 서로 붙어있게 만들어져있어서 세그먼트를 이루지만 데이터는 연속적인 인스텐트에 저장되는 것이 아니라는 것을 알수있다.


이런 세그먼트들에 할당되어 있는 익스텐트 목록을 조회하는 쿼리는 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
select
    segment_type,
    tablespace_name,
    extent_id,
    file_id,
    block_id,
    blocks
from
    dba_extents
where
    owner = USER
order by
    extent_id;
 
cs




실행 결과를 살펴보면 익스텐트별 데이터 파일 블록 아이디를 확인 할 수 있는데, 익스텐트가 연속되어서 저장되지는 않는다는 것을 알 수 있다. 서로 다른 블록에 저장된다.


정리하면

블록 : 데이터를 읽고 쓰는 단위

익스텐트 : 공간을 확장하는 단위, 연속된 블록 집합

세그먼트 : 데이터 저장공간이 필요한 오브젝트(테이블, 인덱스, 파티션, LOB 등)

테이블 스페이스 : 세그먼트를 담는 컨테이너

데이터파일  : 디스크 상의 물리적 OS 파일 (테이블 스페이스는 여러개의 데이터파일로 존재)




※  DBA (Data Block Address)

  • 데이터가 몇번째 블록 어디에 위치해있는지 알려주는 주소를 의미

  • 각 테이블에 레코드에 값을 읽을 때는 ROWID를 사용하는데 ROWID는 DBA + 블록내 순번을 의미

  • 테이블을 스캔할 때는 각 세그먼트 헤더에 저장된 익스텐트 맵을 통해 필요한 블록의 위치로 이동한다.



댓글()

비트코인 핵심기술 블록체인 핵심 요약

IT 지식/IT 지식|2018. 5. 27. 21:12

다들 비트코인붐이 오기 시작하면서 돈을 잃은 사람도 있고, 돈을 얻었다는 사람도 있다.
나는 그 노선에 같이 달리지는 않았지만, 새로운 기술과 트렌드에 뒤쳐지는 느낌이 들어서 늦게나마 공부를 해보고 싶었다.

그 중에서 비트코인의 핵심 기술이라고 불리는 블록체인이 무엇인지 
조사해보았다. (인터넷에 있는 자료를 바탕으로 정리한 내용이다. 출처는 문서 하단에 기재하였다.)







제 3자 인증에서 개인과 개인간의 인증 시스템(P2P)

기존의 화폐거래를 하기위해서는 은행이라는 제 3기관의 인증을 통해 진행되었다.

예를 들어 설명해보자.
만약 위들이라는 사람이 다니라는 사람에게 10만원을 전송하고자 할 때, 위들은 은행에 내 계좌에서 10만원을 다니에게 전송하라고 요청할 것이다. 그럼 은행은 다니에게 10만원을 전송할 것이다. 

우리는 여기서 은행을 제 3기관으로써 신뢰하여 중계를 담당하게 하였다.

하지만 이는 몇몇 단점이 존재한다.
먼저, 그 중계 과정에서 일정의 수수료를 납부해야하는 단점과 돈 흐름에 대한 통제 그리고 장부를 중앙에서 관리하게 됨으로써 장부가 손실이 된다거나 조작될 경우 진위여부파악과 보상을 받기가 까다롭다.

이를 해결하기 위해서 각광받고 있는 기술이 바로 블록체인이다.

블록체인은 이런 제3기관의 중계과정 없이 거래하는 사람과 사람사이에 거래를 하게 되고 그 거래에 대한 장부를 모든 사람들이 나눠가지는 시스템이다.

이런 시스템을 이용하면 모두가 거래에대한 장부를 가지고 있어 조작할 수 없으며, 제 3기관에 거래를 맡기지 않아도 되서 제 3기관에 제약없이 거래를 할 수 있다.


장부기록방식
블록체인 기술은 간단하게 먼저 설명하면 다음과 같다.

거래가 진행되는 내용을 보면 거래 기록이 쌓이게 되는데 그 거래 내역을 적은 종이를 상자에 담고 봉인해야한다. 이때 필요한 봉인번호를 찾아내는 것을 마이닝 또는 비트코인을 채굴한다고 한다.

이해가 가지 않을 수도 있으니 예를들어 설명해보자.

만약 위들이라는 사용자가 다니라는 사용자에게 돈을 10만원을 입금하게 되는 경우,
위들은 모든 사람들에게 다니에게 10만원을 이체한다고 전송하고 모든사람들은 
먼저 위들이라는 사용자가 10만원이 있는지 확인하는 과정을 거친다. 이를 검증하는 절차라고 하는데 검증이 끝난 후 돈을 보냈다는 기록을 장부에 동시에 적어서 보관하는 방식으로 거래가 이루어 진다.

이렇게 기록한 장부를 상자에 보관하기 위해서는 특정한 봉인번호가 필요한대 이를 위해서는 봉인번호를 찾아내야 한다. 비트코인 체굴이라는 것은 결국 이런 봉인번호를 찾기위해서는 문제로 주어지는 특정한 해쉬값을 가지는 input 값을 찾는 과정이라고 생각하면된다.(아래에서 동작 방식 설명) 

먼저 문제를 해결하여 봉인번호를 찾으면 모든 사람들이 이를 검증하고 검증이 끝나면 그 사람은 그 종이를 봉인하게되고 이것이 결국 비트코인을 얻었다고 하는 것이며, 이런 봉인번호를 블록체인에서는 "Proof of Work"라고 한다.

즉 이런 장부를 기록하는 종이를 블록(block)라고 하고, 이런 종이들을 보관하는 종이상자들을 블록체인이라고 한다.

결국 모든 거래는 서로에게 공유되며 그 봉인번호를 찾아서 또다른 연결고리를 찾아가는 과정이 비트코인을 획득하는 과정이라고 보면된다.

출처 : 은평시민신문





거래내역을 변경하고 다시 봉인하면 조작이 가능한가?
그럼 조작이 불가능하다고 하였는데 채굴에 성공한 봉인번호를 가지고 거래내역을 조작한 뒤에 다시 봉인하면 되는거 아닌가? 하는 의구심을 가질 수도 있다.

이미 거래내용이 기재된 거래내용은 현재 발견한 봉인번호와 상관없이 모든 블록들과 연결되어 있기 때문에 하나의  block의 기록된 거래내용 자체를 변경하고자 한다면 모든 거래 내역을 다 조작해야 하기 때문에 불가능에 가깝다.

결국 현재의 block은 이전의 block과 연결되어 있고 그 블록은 또 그 이전 block에 연결되어 있기 때문에 조작하려면 모든 봉인번호를 찾아내야 하는데.. 하나의 봉인번호를 찾아서 비트코인을 채굴하는 것도 어려운 상황에서 보든 봉인번호를 다시 찾아내서 조작한다는 건 현재 기술에서 불가능에 가깝다.

하지만 악의적으로 모두가 함께 조작한다면 조작이 가능하다는 단점은 가지고 있다.



비트코인 체굴 원리
그럼 이런 비트코인의 체굴의 원리가 무엇인지 살펴보자.
비트코인을 체굴하는 것은 금을 캐네는 것과 같다고 해서 마이닝(mining)이라고 한다.

마이닝이라는 단어는 텍스트 마이닝과같이 빅데이터에서도 자주 사용되고 여러모로 현대에서 참 가치를 찾아낸다는 뜻으로써 많이 사용되는 것 같다.

아무튼 위에서 먼저 살펴보았듯이 봉인번호를 찾는 과정을 비트코인을 채굴하는 것이라고 하는데
이는 문제해결을 통해서 얻을 수 있다.

문제는 10분에 한번씩 일정량이 생성되며, 문제를 해결한 사람에게는 비트코인이 부여되는 것이다.
이런 문제를 hashcash라고 한다.

해시는 단반향성으로써 input 데이터로 생성된 out 데이터로 다시 input 데이터를 찾을 수 없다.
또한 들어오는 input 데이터가 하나가 변경되어도 완전 다른 데이터가 출력이된다. 예를들면 hello와 hello1은 완전 다른 hash 값이 출력된다.

그렇기 때문에 대표적인 hash 알고리즘인 sha-256는 경우의수가  2256개이다.
그렇기 때문에 사실 모든 데이터를 다 조회해보는 것은 너무 어렵다.

그래서 비트코인 체굴을 위해서 제공되는 데이터는 문자열과 결과 hash값이다. 
그래서 체굴하고자 하는 사람은 임의의 nonce만을 찾아내면 되도록 문제를 제공한다.



사용자 인증방법 및 거래 방법
중앙에서 이것이 내 비트코인이라는 것을 증명해주는 기관이 없다면 이 비트코인이 내 것이라는 것을 어떻게 증명해야할까?

이는 공개키 암호화 방식으로서 문제를 해결하고 있다.
※ 공개키 암호화 방식


출처 : https://brunch.co.kr/@artiveloper/24



공개키 암호화 방식을 사용하면 누구나 공개키를 통해서 개인키로 서명한 서명을 검증할 수 있다.
=> 특정메시지를 자신의 개인키로 서명하면 다른 사람은 이미 공개된 공개키로 그 서명이 그사람 개인키로 서명한 것인지 확인할 수 있다.

그래서 위들이라는 사용자가 다니라는 사람과 거래를 할 때 다니가 올린 공개키로 다니가 보낸 데이터가 다니의 개인키로 암호화 된건지 인증할 수 있다.

거래과정은 다음과 같다.

돈을 보내는 사람이 공개키와 개인키를 생성해서 돈을 받는 사람에게 전달하고 수표를 작성해서 P2P  네트워크에 전송한다. 이 수표를 사용하기위해서는 돈을 보내는 사람의 개인키가 있어야 한다. 이 수표가 돈을 보내는 사람의 수표가 맞는지 확인은 돈을 보낸 사람의 공개키로 검증해볼 수 있다.

비트코인이란 시스템에서 가장 중요한 부분은 바로 이렇게 돈을 주고받는 거래이다.

돈을 보내는 수표를 발행하기 위해서는 발행하는 사람의 과거으 ㅣ수표 이력을 조회하여 돈이 그만큼 존재하는지 확인한다.





출처 : 네이버 D2



위의 예를 살펴보면 Transaction C는 D에게 보내기 위해 A와 B를 통해 전달 받았던 수표를 가리키고 있다. 

Transaction D는 C에게 비트코인을 전송받았기 때문에 Transaction C가 발부한 수표를 가리키게 된다. 그리고 Transaction C는 D에게 101 비트코인을 전송하고 잔액 49 비트콘인 남게된다.

수표의 뿌리는 마이닝을 통해서 채굴한 비트코인부터 시작이다.
위의 그림에서 Transaction B가 비트코인을 통해서 채굴을 한 뿌리 수표이다.

그럼 위에서 설명했던 내용 중에 위변조에 대한 내용을 다시 한번 확인해보자.
비트코인에서 수표(위에서는 거래장부)를 블록체인에 저장하기 위해서는 여러 개의 수표를 모아서 하나의 블록을 생성하고, 그 블록을 연결리스트로 만들어 저장한다. 

이 블록을 생성하기 위해서는 앞에서  설명했던 hashcash문제를 또 풀어야 한다. 
이 블록자체를 위조할 수 있다고 생각하지만 위에서 설명했던 것 처럼 블록은 연결리스트로 구성될 때 이전 블록의 해시값을 다음 블록에 포함시켜서 중간에 블록의 위조를 막는다.




출처 : D2




Block2는 Block1의 해시값 hash1을 담고 있다. 그렇기 때문에 Block1의 내용이 수정되면 Hash1의 값이 변경되기 때문에 block2도 수정되어야하고 이런과정을 통해 모든 hash 값이 변경되어야 한다.

사실 전세계에 P2P로 연결된 블록체인 기술에서 hash값을 변경해가면서 위변조 하는 것 자체가 불가능에 가깝기 때문에 그정도로 신뢰도가 있다고 판단해도 좋을 것 같다.



만약 비슷한 시점에 봉인문자열을 찾게 된다면?

내가 블록체인을 알아보면서 가장 궁금했던 것은 바로 이 이슈이다.
만약 비슷한 시점에 해답을 찾게 된다면 누가 먼저 찾았는지 알 수 있을까?라는 문제이다.

비트코인은 기본적으로 길이가 긴 블록체인을 원본으로 생각하고, 둘이 길이가 같다면 이중 아무거나 선택해도 문제가 없다는 원칙을 가진다.

블록체인 A를 보유한 사용자는 새로 생성된 블록을 블록체인 A에 추가해 나갈 것이고, 블록체인 B를 보유한 사용자는 새로 생성된 블록을 블록체인 B에 추가해 나갈 것이다. 블록체인 A에 새로 추가된 블록을 블록체인 B의 사용자는 받아들이지 않는다. 블록체인이 다르다는 건 새로 생성된 블록이 가리키는 이전 블록의 해시값이 다르다는 의미이기 때문에 블록체인을 형성할 수 없기 때문이다. 따라서 양쪽 블록체인의 사용자는 완전히 갈라져서 별개의 네트워크처럼 나누어진다.

시간이 지나면 양쪽 사용자 중 컴퓨터 성능이 더 좋은 쪽이 더 빨리 블록을 생성해 더 긴 블록체인을 만들게 된다. 더 긴 블록체인이 아마도 더 많은 사용자가 참여한 블록체인일 것이다. 그리고 둘 중 하나가 블록을 위조하려는 세력이라면 아마도 짧은 블록체인을 가진 쪽이 불순한 세력일 가능성이 높을 것이다. 이제 블록체인 A와 블록체인 B의 길이가 달라지는 시점에 사용자가 짧은 블록체인이 잘못된 블록체인이라고 판단하고 긴 블록체인을 받아들이는 것으로 전략을 바꾼다면 전체 사용자가 가진 블록체인은 곧 하나로 통일된다.

다음 그림은 이 과정을 도식으로 표현한 것이다.




사진 출처 D2




밑에 있는 초록색 블록부터 시작해서 위로 블록체인을 만들어 간다. 특정 시점에 2개의 블록이 동시에 생성되어 블록체인이 나눠질 수 있지만(그림에선 2개로만 나뉘지만 더 많이 나뉘는 것도 가능하다), 곧 어느 한 블록체인이 더 길어질 것이고 짧은 블록체인은 버려진다. 사용자가 정확히 반으로 나뉜다면 양쪽 블록체인이 동일한 길이를 유지하며 길어질 수도 있지만 이렇게 될 확률은 매우 낮기 때문에 곧 어느 한쪽으로 수렴한다. 가장 긴 블록체인(그림에서 진한 검은색으로 표시된 체인)이 블록체인의 원본이 되고 네트워크의 모든 피어가 동일한 블록체인을 유지할 수 있게 된다.



참고 사이트


비트코인 개발 문서

https://bitcoin.org/en/developer-documentation


비트코인 프로그램
https://bitcoin.org/en/bitcoin-core/features/user-interface


출처 : 
http://d2.naver.com/helloworld/8237898 


http://slownews.kr/67899



댓글()
  1. ㅇㄴㅁ 2018.08.09 16:45 댓글주소  수정/삭제  댓글쓰기

    TREBIT

    코인거래소
    Trebit 이 원화마켓을 오픈합니다 :)
    8월 8일 18시 기준 원화마켓이 오픈이 되었습니다 !

    원화(KRW)마켓 오픈과 함께
    옵저버(OBSR)와 아이온(ION) 8월10일 상장!!!

    특히 옵저버(OBSR)는 전 세계 최초로 트래빗 거래소에 상장되는 코인으로,

    일반 암호화폐와 다르게
    ICO를 진행하지 않고 상장되는 종목입니다.

    원화(KRW)마켓 오픈 기념으로
    거래수수료 0% 이벤트를 진행 중이니
    수수료 부담 없이 거래하시고,
    무려 3억원 상당의
    에어드랍 이벤트의 주인공에 도전해 보세요.

    트래빗고객센터 : 1600-5433
    운영시간 : 평일 09:00 ~ 18:00
    이용문의 : cs@trebit.com

    *옵저버 더 알아보기: http://www.obsr.org/index
    *아이온 더 알아보기: https://ionomy.com/games