딩코딩 : Computer Science 블로그

Sequential Access와 Random Access

메모리에서 특정 레코드를 찾기 위해 디스크에 접근할 때

레코드를 찾는 순서에 따라 디스크 접근 방식을 Sequential Access와 Random Access로 나눌 수 있다.

그림에서 알 수 있듯이 Sequential access는 데이터에 대해 저장된 순서대로 접근하는 방식을 의미하고

Random access는 데이터에 대해서 랜덤하게 접근하는 방식을 의미한다.

이러한 Access방식에 대해 실생활에서 은행을 예로 들어 생각해보자.

은행에는 많은 사람들이 방문한다.

방문하는 사람들은 계좌번호 순서대로 줄을 서서 입장하지 않는다.

무작위의 계좌번호를 가진 손님들이 Random Access 하는 방식이다.

이제 Sequential Access 방식을 생각해보자.

은행이 문을 닫고 은행원은 손님들의 계좌번호를 Sorting 한 상태에서 순서대로 볼 것이다. (아마도)

이 방식이 Sequential Access 방식이다.

즉 일상생활에서 데이터 레코드에 접근할 때 방식은

Sequential Access, Random Access 나뉘는 것이다.

이러한 Access 방식을 생가하며 화일의 구조를 만들어야 한다.

Sequential file과 Index file

화일은 크게 두가지 구조로 나뉜다.

sequential file과 Index file이다. 

순차화일과 색인 화일로 부르기도 하는데 이제

두 화일을 순차화일과 인덱스 화일로 칭한다.

화일 처리의 주된 목적은 메모리에서 디스크 Access를 줄여서 io시간을 줄이는 것이다.

https://dingcoding.tistory.com/318?category=1035429 

위에서 설명한 두가지 Access 방법에 따라 

Sequential file과 Index file의 장단점이 구분된다.

결론부터 말하면 Sequential file은 Sequential Access에 유리하고

Index file은 Random Access에 유리하다.

이제 그 이유를 살펴보자

순차화일

순차화일은 데이터가 순차적으로 저장되어 있기 때문에

Sequential Access를 많이 할 경우 유리하다.

Blocking Factor(메모리에서 디스크의 블록을 읽는 단위)에 따라 데이터를 읽는 양은 다르겠지만,

Sequential Access를 할 때

5번 21번 학생의 데이터가 필요한 상황이라 가정해보자.

그리고 쉽게 설명하기 위해서 한 번의 디스크 Access를 할때 학생 3명의 데이터를 읽을 수 있다 가정하자.

그렇다면 순차적으로 5번, 21번, 105번의 데이터가 필요한 경우에는

5번 학생의 데이터를 읽기 위해 디스크 Access를 한 이후에

5번, 21번, 105번 데이터를 읽어온다 (학생 3명의 데이터를 읽어올 수 있다고 가정했으므로)

메모리에는 5번 21번의 데이터가 존재하기 때문에 21번 학생의 데이터를 얻기 위해서

다시 디스크에 접근할 필요가 없다.

즉 데이터를 순차적으로 요청할 때 순차화일의 경우에는 Disk Access를 적게 할 수 있다는 장점이 있다.

하지만 Random Access를 할 경우 비효율적이 된다.

이번에는 5번, 700번, 105번 데이터를 읽는다 생각해보자. (이번에도 한번의 Disk Access에 3명의 데이터를 읽어온다고 가정하자)

Disk Access 1회:

5번 데이터를 읽을 때

메모리 버퍼에는 5, 21, 105번이 저장된다.

Disk Access 2회:

메모리 버퍼에 700번 데이터가 없기 때문에

다시 디스크에 접근하고 700번, x, y 데이터를 읽어오게 된다.

Disk Access 3회:

메모리 버퍼에 105번 데이터가 없기 때문에

다시 디스크에 접근하고 데이터를 읽어오게 된다.

이 때 데이터를 찾을 때마다 순차화일에서 이진탐색을 해야한다.

디스크 위에서 이진탐색을 시행하기 때문에 여러번 디스크에 접근해야 하는 것이다.

하지만 이런식으로 데이터를 처리하면 cpu의 관점에서 너무 느려진다.

한번 디스크에 접근하는데 10ms 정도 소요되기 때문이다.

그리고 더불어 다른 문제점으로 순차화일은 데이터를 갱신할 때 비용이 많이 든다.

(그 이유는 위의 다른 게시물 링크에서 설명한다)

Random Access 할 때도 디스크 Access 를 줄이는 방법이 필요하다.

인덱스 화일

인덱스 화일에서는 순차화일과 달리 데이터를 key값에 따라 순서대로 저장하지 않는다.

데이터가 입력되면 입력되는 그 순서대로 기록할 뿐이다.

하지만 해당 학번이 디스크 어느 위치에 존재하는지 나타내주는

인덱스 테이블을 메인 메모리에 두고 사용한다.

이럴 경우 메인 메모리에서 원하는 key(학번)을 찾아서 바로 디스크에 접근할 수 있다.

인덱스를 메인메모리에 저장할 수 있는 이유는

단순 인덱스 테이블을 메인 메모리에 저장하는 데에는 많은 용량이 필요하지 않기 때문에 가능하다.

그리고 추후 설명하겠지만 실제로 인덱스 테이블은 배열구조가 아닌

트리 구조로 이루어진다.

트리 자료구조로 인덱스 구조를 만들어 메모리에 저장하고 디스크에 접근해야 하는 일이 생기면

메모리 내의 인덱스에서 key값을 찾아 접근해야 하는 디스크의 주소를 알아내고 디스크에는 한 번 Access 하게 되는 것이다.

순차화일 처럼 키값을 찾기 위해 이진탐색을 하는 것은 동일하지만

순차화일은 디스크 상에서 이진탐색을 해야하는데

인덱스 화일은 메모리 상에서 이진탐색을 진행하기 때문에 

인덱스 화일이 Random Access를 할 때 유리하다.

하지만 인덱스화일은 Sequential Access를 할 때 불리하다.

순차화일은 데이터가 순차적으로 저장되어 있는 걸 읽어오기 때문에

순차적으로 데이터를 요청할 때 Disk Access를 적게 할 수 있는데 비해

인덱스화일은 실제 데이터가 무작위로 섞여 있기 때문에

순차적인 데이터 요청이 오더라도 계속 Disk Access를 하여 데이터를 읽어와야 할 것이다.

이처럼 순차 화일과 인덱스 화일은

Disk Access 방식에 따라 장단점이 존재한다.

하지만 이러한 두 화일의 장점을 살려 만든 B+ 트리 구조의 화일도 존재한다.

데이터를 순차적으로 정렬해서 저장해야 하는 이유

컴퓨터에서 영속적인 데이터를 보관하기 위해

물리적인 디스크에 정보를 저장한다.

cpu의 관점에서 디스크에서 데이터를 읽어오는 io시간은 굉장히 큰 시간이다.

디스크에서 특정 데이터를 찾는데는 물리적인 rotational delay와 seek time이 필요하기 때문이다.

그렇기 때문에 최대한 디스크에 적게 접근하는 게 중요한 문제이다.

데이터를 저장할 때는 메모리의 output Buffer에 있는 내용을 디스크에 쓰고,

컴퓨터에서 디스크에 있는 정보가 필요해서 불러올 때는 디스크의 블록 단위를 기준으로 메모리에 데이터를 불러온다.

이때 중요한 것중 하나가

컴퓨터에서 특정 데이터가 필요할 때

디스크에 access해서 디스크로부터 메모리로 블록을 읽어와야 한다.

이때 필요한 레코드가 block의 어디에 위치해 있는지 찾는 것이 중요하다.

만약 레코드가 10억개가 존재하는 상황에서 하나의 레코드를 찾아야 한다고 생각해보자

레코드들이 모두 무작위로 위치해 있다면 최악의 경우 레코드를 10억개를 다 찾아보아야 한다.

이 방법은 너무 오래걸린다.

특정 레코드 조회 빨리 하기 위해서 key값을 기준으로 binary search를 한다면

굉장히 빠르게 찾을 수 있다. binary search는 logN 만큼 조회하면 해당 레코드를 찾을 수 있기 때문이다.

log(10억)은 30에 가깝다.

위에서 데이터가 무작위로 위치해있을 땐 최악의 경우 10억번을 봐야했는데,

데이터가 정렬되어 있다면 30번만 보면 디스크에서 원하는 데이터를 찾을 수 있다!

즉 데이터가 일정하게 정렬되어 있는 화일을 sequential한 파일, 순차화일이라 부르는데

화일이 순차화일로 존재한다면 데이터 조회를 굉장히 빠르게 할 수 있는 것이다.

트랜잭션 화일과 마스터 화일 

위에서 처럼 화일에서 데이터를 순차적으로 저장해야 조회를 빠르게 할 수 있다.

그런데 단순히 화일을 순차적으로 저장하면 문제가 발생한다.

데이터에 특정 레코드가 삽입된다면

모든 데이터를 다시 써야하는 문제가 발생하기 때문이다.

예를 들어서

데이터 레코드가 총 10억개 정도 있다고 생각하자.

10억개 데이터는 모두 정렬되어 있다.

이때 화일에 데이터를 하나 삽입해야한다.

그런데 5억개 데이터와 5억개 데이터 사이에 새로운 데이터가 하나 추가되어야 된다고 생각해보자.

그렇다면 새로운 화일을 만들어

기존 5억개 데이터를 그대로 쓰고, 새로운 데이터를 하나 추가하고

다시 또 5억개 데이터를 써야한다.

즉, 순차적인 화일 구조를 유지하기 위해서 데이터가 갱신될 때마다 엄청난 양의 데이터를 다시 써야한다.

이런 구조는 실제로 사용할 수 없다. 데이터 조회는 빨리 할 수 있지만 조회를 빨리 하기 위해서 화일을 다시 쓰는 시간이 너무 오래걸린다.

이러한 문제를 개선하려면

순차 화일 구조를 유지하되, 데이터 갱신하는 횟수를 줄여야한다.

이를 해결하기 위한 방법이 마스터 순차화일을 하나 유지하고,

데이터 갱신 요청을 기록해주는 트랜잭션 화일을 하나 더 만들어서,

일정 간격마다 트랜잭션 화일에서 마스터화일로 데이터를 merge해주면 된다.

이전에는 데이터 갱신이 될때마다 화일을 다시 써야 했다면,

이제는 데이터 갱신 기록을 트랜잭션 화일에 쭉 저장해두었다가, 정해둔 간격마다 마스터 화일에 저장하면 된다.

이렇게 하면 마스터 화일에서 데이터를 빠르게 조회할 수 있고,

순차화일에서 데이터를 갱신하는 문제도 해결할 수 있다.

다만 이도 완벽할 수 없는게 데이터 갱신을 일정 주기마다 하기 때문에

트랜잭션 파일에 저장되었지만 마스터 파일에 저장되지 않았다면 데이터 조회를 할 수 없다.

그래서 비즈니스 로직에 따라 일정한 간격을 정하는 것이 굉장히 중요하다.

디스크와 메인 메모리(사이 버퍼)

프로그램이 하나의 Logical Record를 요청할 때

디스크에 있는 Physical Record인 한 block이 

메인 메모리의 버퍼에 저장되고, 

프로세스는 버퍼에 저장된 데이터를 Work Area로 불러와 해당 데이터를 이용해서 프로세스를 실행한다.

이때 버퍼의 자료구조는 Circular Linked List를 이용하여

다중 버퍼로 구현될 수 있다. 

프로그램 코드에서 open으로 파일을 불러올 때 

디스크에서 해당하는 파일의 첫번째 블록을 메인 메모리의 input 버퍼에 저장한다.

이때 첫번째 블록을 버퍼로 로드하는 이유는 미리 블록을 로드해두면

이후에 만약 첫번째 블록에 해당하는 데이터를 이용해야하는 일이 있으면

디스크에 Access할 필요 없이 바로 다음 명령을 진행할 수 있어서 효율적이다. 

물론 첫번째 블록에 해당하는 데이터를 이용하지 않는 경우도 있다.

버퍼

만약 A라는 프로세스가 x,y,z라는 파일을 open으로 읽는다면

IO Buffer역할을 하는 메모리가 메인 메모리에 할당된다.

그리고 후에 close를 하면 할당했던 메모리를 반환하여 다른 프로그램이 메모리를 활용할 수 있도록 한다.

그리고 프로그램을 종료할 때 꼭 close를 해야 메인 메모리에 있는 Output Buffer에 있는 데이터가

디스크에 올바르게 저장된 후 프로세스가 종료된다.

버퍼안의 여러개의 블록을 저장할수록

디스크 Access가 줄어들어 Io의 속도가 빨라지지만 메인메모리의 용량은 한정되어있어

만약 버퍼가 과도하게 메모리를 차지하게 되면 다른 프로세스가 사용할 수 있는 메모리의 양이 줄어들어

전체적인 프로세스 스케줄링이 비효율적으로 된다.