Computer Science & Engineering

    이번에는 이전 글(https://shyeon.tistory.com/13)에서 만든 레코드파일을 관리하는 simple index 파일을 생성하고 생성한 simple index파일을 활용하여 이진탐색 방식을 이용해 원하는 레코드의 정보를 불러오는 기능을 구현해 보았다.

simple index파일에서의 key 값으로는 14바이트짜리 id가 사용된다 그리고 원하는 주소에 접근하기 위해서 페이지번호와 페이지에서의 레코드 번호가 주소값으로 사용된다. 그렇기 때문에 뒤에 널문자를 제외한 13바이트의 id, 페이지 번호로 4바이트, 레코드 번호로 4바이트 총 21 바이트가 simple index 파일의 하나의 레코드를 구성한다. 레코드 파일을 하나 넘겨줄 경우 record.idx라는 이름의 simple index 파일이 생성된다. 이때 생성된 레코드는 id에 대해 오름차순으로 정렬된다. 이 id는 정수형으로 정렬되기 때문에 자리수가 클 수록 큰 수로 판단된다. 레코드파일은 다음과 같은 명령어로 실행된다.

$ a.out i records.dat records.idx

이렇게 두 번째 인자로 i를 줄 경우 records.dat의 레코드파일로부터 records.idx라는 이름의 index 파일을 생성한다.

    만약 두 번째 인자로 b 옵션을 줄 경우 정렬된 index 파일로부터 원하는 키 값을 주었을 때 원하는 레코드의 정보를 출력한다. 실행할 경우 다음과 같이 나타나게 된다.

$ a.out b records.dat records.idx "9800001111111"

#reads:3

id=9800001111111

name=shyeon

age=24

addr=Seoul

phone=010-0000-0000

email=shyeon@shyeon.com

이렇게 records.idx에서 9800001111111이라는 키를 이진 탐색으로 찾는데 3번의 읽기를 했다는 의미로 #reads:3을 출력하고 records.idx에서 찾은 주소값으로 records.dat이라는 레코드파일에서 해당 레코드를 읽은 결과를 밑에 출력하게 된다. 만약 레코드가 존재하지 않는 경우 "no persons"를 출력한다.

https://github.com/Seo-sang/simple_index_record_file

이전 글에서 설명한 가변길이 레코드 방식을 실제로 구현해보았다. 레코드파일 person.c의 구조는 다음과 같다.

 - 레코드 파일

    1. 레코드 파일은 헤더 영역과 데이터 영역으로 이루어져있다.

    2. 헤더 영역에는 헤더 레코드가 존재하고 데이터 영역에는 여러 개의 데이터 페이지가 존재한다.

 - 헤더 레코드

    1. 헤더 레코드는 전체 데이터 페이지 수 4바이트, 레코드 파일에 존재하는 모든 레코드 수 4바이트, 마지막 8바이트에는 4바이트씩 삭제 레코드를 관리하기 위해 가장 최근에 삭제된 레코드의 페이지 번호와 레코드 번호를 가지고 있다.      2. 만약 삭제 레코드가 존재하지 않는다면 헤더 레코드의 마지막 8바이트의 값은 모두 -1이다.

    3. 레코드가 삭제되었을 때 헤더 레코드의 페이지 수나 모든 레코드의 수는 수정하지 않는다.

    4. 삭제 레코드는 연결리스트 방식으로 관리된다.

 - 데이터 페이지

    1. 데이터 페이지는 헤더 영역과 데이터 영역으로 나누어져있다.

    2. 헤더 영역에는 페이지에 저장된 레코드의 수, 각 레코드의 주소, 길이(offset, length)가 있으며 데이터 영역에는 실제 저장하려는 레코드가 저장된다.

    3. 레코드의 수, 주소, 길이는 각각 4바이트이며 첫 번째 레코드의 주소는 0이다.

    4. 데이터 페이지의 번호는 0부터 부여한다.

 - 레코드

    1. 레코드는 가변길이 방식으로 저장한다.

    2. 레코드의 필드는 구분자(delimiter)를 이용한다. 이때 구분자로 '#'을 사용한다. 

    3. 새로운 레코드는 파일의 마지막 페이지의 마지막 레코드 다음 위치에 저장되고 공간이 부족할 경우 데이터 페이지를 새로 할당하여 저장한다.

    4. 만약 삭제레코드에 새로운 레코드를 저장할 수 있는 경우 삭제 레코드에 저장한다. 이때 first-fit 방식을 이용한다.

    5. 삭제 레코드에 추가할 경우 연결리스트의 앞과 뒤를 연결해주어야한다.

    6. 삭제 레코드 중에 추가할 수 없는 경우 3번과 같이 추가한다.

    7. 레코드를 삭제할 경우 delete mark로 '*'를 사용하며 delete mark 뒤에 연결리스트에 사용될 다음 삭제 레코드의 페이지 번호와 레코드 번호가 4바이트씩 binary integer 형식으로 저장된다.

    8. internal fragmentation은 고려하지 않는다.

레코드는 다음과 같이 이루어져있다.

#define MAX_RECORD_SIZE	100 // including 6 delimeters
#define PAGE_SIZE		256 // 임의로 지정
#define HEADER_AREA_SIZE	(PAGE_SIZE/10)
#define DATA_AREA_SIZE	(PAGE_SIZE - HEADER_AREA_SIZE)

typedef struct _Person
{
	char id[14];		
	char name[18];		
	char age[4];		
	char addr[22];	   
	char phone[16];		
	char email[26];		
} Person;

#endif

위의 6개의 정보로 이루어진 구조체가 하나의 레코드로 저장된다.

완성된 코드는 아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/variable_length_record

개발 환경은

OS Linux Ubuntu 20.04

gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

이다.

    우선 File에 대하여 설명하자면 파일이란 secondary memory(HDD, SSD, CD, tape 등)에 저장된 같은 형식을 가진 record들의 집합이다. 그렇다면 File Structure는 무엇인가? 파일 구조란 File Structure는 데이터를 표현하는 representation과 그 데이터를 접근하는 operation의 조합이다. 여기서 representation의 예시로는 C언어의 구조체가 있고 operation은 삽입(insert), 삭제(delete), 검색(search) 등이 있다. 우리가 좋은 파일 구조를 만들기 위해서는 데이터로부터 정보를 얻을 때 가장 적은 비용이 들어야한다. 파일처리에서 가장 많이 드는 비용은 디스크 접근이다. 그렇기 때문에 좋은 File Structure를 만들기 위해서는 Disk I/O를 줄여야한다. 앞의 내용을 요약해보면 따라서 파일처리란 파일에 접근하여 직접 구현한 연산들로 데이터를 다루는 것이라고 할 수 있다.

    우리가 앞서 말한 Disk I/O를 줄이기 위해서는 어떻게 해야할까? 얘를 들어 하드디스크(HDD)에 저장된 100명의 사람들 중에 홍길동씨의 정보를 찾는다고 생각해보자. 인간이 아니라 컴퓨터가 홍길동씨를 찾기 위해서는 가장 쉬운 방법으로 첫 번째 사람부터 차례대로 비교해보는 것이다. 이런 방식을 썼을 때 만약 홍길동씨가 77번째 record에 존재한다면 컴퓨터는 77번의 비교를 해야 찾을 수 있을 것이다. 이러한 방식을 Sequential access 순차접근이라고 한다. 그렇다면 빠른 방법은 어떤 것이 있을까? 우선 Simple index 방식을 알아보자 아래 그림과 같이 HDD에 저장된 모든 record파일을 읽어오기엔 파일이 너무 클 수가 있다. 따라서 index file을 따로 만들어 그림 왼쪽과 같이 이름과 record의 주소만 정렬하여 저장한다. 이 index file은 크기가 작기 때문에 main memory인 RAM에 모두 올릴 수 있다. 그 다음 RAM에서 이진탐색과 같은 방식으로 홍길동을 찾아 HDD의 해당 위치부터 record를 읽어오면된다.

따라서 순차처리의 경우 record파일을 한 줄씩 읽어온다면 총 3번의 Disk I/O가 발생하지만 Simple index 방식의 경우 index file을 읽어오는 비용 1번과 알아낸 주소로 접근하여 홍길동의 record를 읽어오는 1번으로 총 2번의 Disk I/O가 발생한다. 위 그림의 경우는 작은 크기이기 때문에 큰 차이가 있지 않지만 만약 record의 수가 굉장히 많은 경우 그 비용의 차이가 굉장히 커질 것이다.

   이렇게 simple index 방식은 Random access가 가능하기 때문에 시간적인 비용이 줄어든다. 하지만 record가 추가될 경우 index file도 같이 수정해야하는 번거로움이 존재한다. 이 외에도 Binary Search Tree, B-Tree, B+Tree 등 많은 방식이 존재하지만 다른 글에서 설명하도록 하겠다.

Flash memory의 Software의 구성 방식은 다음과 같이 계층적 구조로 이루어져 있다.

우리가 사용하는 Application에서 발생하는 read, write와 같은 연산들은 우리에게는 보이지 않지만 아래의 layer에 의해 투명하게 처리된다.

    우선 Flash File System은 대표적으로 FAT(file allocation table) file system이 있다. 이 계층에서는 application layer에서 호출한 read, write 연산을 수행하는 일반적인 파일 시스템이다.

    FTL(Flash Translation layer)는 우리가 사용하는 NAND 플래시 메모리를 일반 하드디스크와 같은 블록장치와 같이 행동하기 위해 논리주소를 물리주소로 mapping하는 기능을 수행한다. 이때 논리주소와 물리주소를 mapping되어 있는mapping table을 사용한다. Flash memory는 덮어쓰는 overwrite 기능을 제공하지 않기 때문에 out-of-place update를 사용한다. 따라서 block mapping table에는 항상 overwrite를 할 때 사용하는 free block을 두어 out-of-place update이 이루어질 때 사용한다. 또 하나의 block에 많은 erase, write가 이루어지는 bad block이 발생하지 않도록 하는 wear-leveling 기능도 제공한다.

    Flash Device Driver는 직접 NAND 플래시 메모리에 물리적으로 접근하여 데이터를 읽고 쓰는 역할을 수행하는 계층이다. 또 bad block와 ECC(Error Correction Code)를 처리한다.

    위와 달리 Flash File system 계층과 FTL 계층을 하나의 계층인 Dedicated Flash File System도 존재한다. 그러한 구조는 플래시 메모리 전용으로 설계된 파일 시스템에서 사용된다.

    FTL에서 논리주소와 물리주소를 mapping하는 방법에는 여러가지가 있다. 대표적으로 sector mapping, block mapping, hybrid mapping이 존재한다. 글쓴이가 구현한 방식은 block mapping 기법을 사용하였다. 이 세가지 기법을 간단히 설명하자면 sector mapping은 lsn(logical sector number)와 psn(physical sector number)가 1대1로 mapping되어 있는 방법이다. 이 경우 mapping table이 굉장히 커질 수 있는 단점이 존재한다. block mapping table 기법은 lsn을 블록당 페이지의 수로 나눈 몫을 block번호로 사용하고 나머지를 page번호로 사용하는 방법이다. 예를 들어 lsn이 9이고 한 블록당 page의 수가 4개인 경우 9/4 = 2가 블록 번호(pbn), 9%4 = 1이 블록의 page번호(ppn)인 것이다. 이 경우에 한 블록에 4개의 page가 존재하므로 sector mapping 방식에 비해 mapping table이 1/4로 줄일 수 있는 이점이 있다. 마지막으로 hybrid mapping 방식은 block mapping과 굉장히 유사하지만 나머지인 offset을 ppn으로 사용하는 것이 아닌 pbn의 비어있는 곳에 순서대로 할당한 후 page의 spare영역에 메타데이터인 lsn을 저장하여 어디서 저장된 데이터인지 알 수 있게한다.

    아래 링크는 C언어를 활용해 구현한 FTL의 block mapping table이다.

https://github.com/Seo-sang/file_processing_FTL