[파일처리] Organizing Files for Performance

데이터 압축 (Data Compression)

※ 데이터 압축의 장점

- 파일 크기를 작게 만들어 저장 공간을 절약함
- 전송 속도를 빠르게 함
- 순차 탐색 속도를 빠르게 함

※ 데이터 압축의 단점
- 압축된 파일은 읽을 수 없음
- 인코딩, 디코딩 비용이 필요

※ 데이터 압축 방식

• 다른 표기법의 사용(Using a Different Notation) - redundancy reduction : 간결한 표기법으로
  - ex) 미국의 50개 state : 2byte(16bit) -> 6bit로 표현 가능
  각 state를 0 ~ 49로 맵핑하면 49(110001)를 표현하기 위해 6bit만 필요함
  
  
• 반복되는 열의 삭제 (Suppressing Repeating Sequences) - Run-length encoding
  - 2번 이상 연속되는 데이터에 대해서 다음과 같이 표현
  - run-length 코드 지시자, 반복되는 pixel 값, 반복 횟수로 표현

• 가변 길이 코드의 대입 (Assigning Variable-length Codes) - 허프만 부호화
  - 파일 내에서 출현 빈도가 문자마다 다르다는 사실에 착안한 방식
  - 출현 빈도가 높은 문자에 적은 비트의 코드를 부여
  - ex) "abde"(4 byte) -> "101000000001(12 bit)

---

데이터 회수 (Reclaiming Space in Files)

파일을 이용하다 보면 특정 레코드를 삭제하거나 수정하는 경우가 많다. 이러한 과정을 반복하다 보면 원래 있었던 레코드의 공간에 단편화가 발생하여 파일 구조가 악화될 수 있다. 따라서 사용하지 않는 레코드 공간을 다시 회수할 수 있는 방법이 필요하다.

 

※ 데이터 회수 방식

• Storage compaction
  - 정상적인 레코드들만 새로 다른 파일에 복사
  - 비용이 크기 때문에 실시간이 아닌 주기적으로 실행
  - 삭제된 레코드들의 맨 앞부분에 특수문자로 마킹해두고 주기적으로 삭제

※ 공간 재사용을 위한 삭제된 데이터 관리 방식

• Deleting Fixed-Length Records
  - 삭제된 레코드를 빠르게 찾는 것이 중요함
  - 따라서 삭제된 위치를 미리 알고 바로 접근이 가능하도록 해야 함
  - 삭제된 레코드를 linked list로 관리

1. 삭제된 레코드의 값 : 특수문자 + 바로 앞에 삭제된 레코드의 RNN (없다면 -1)
2. 가장 최근에 삭제된 레코드의 RNN을 header에 저장
3. header가 가리키는 레코드를 선택하여 새로운 데이터를 저장
4. header의 값을 갱신

 

• Deleting Variable-Length Records
  - 가변 길이 레코드 방식에서는 RNN을 사용할 수 없음
  - 따라서 레코드의 byte offset을 통해 접근해야 함
  

1. 삭제된 레코드 값 : offset + 특수문자 + 구분자 + 바로 앞에 삭제된 레코드의 offset (없다면 -1)
2. 가장 최근에 삭제된 레코드의 offset을 header에 저장
3. 링크드리스트를 따라가며 새로운 데이터를 저장할 수 있는 크기의 삭제된 레코드를 발견하면 삽입
4. 만약 충분한 크기의 삭제된 레코드가 없다면 파일의 맨 끝에 append

---

 

※ 저장공간 단편화(Storage Fragmentation)

낭비되는 공간을 internal fragmentation이라고 부른다. 고정 길이 레코드 방식을 사용하는 경우는 당연하게도 internal fragmentation이 존재할 수밖에 없다.

 

그렇다면 가변 길이 레코드 방식을 사용하면 internal fragmentation이 생성되지 않을까? 그렇지 않다. 가변 길이 레코드 방식은 삭제된 공간을 재활용하는 과정에서 더 작은 크기의 레코드를 삽입하는 경우 internal fragmentation이 발생한다. 다만 이를 다시 가용 리스트로 사용하는 방식을 사용하여 문제를 해결할 수 있다.

 

하지만 더 이상 가용리스트로 사용할 수 없는 크기의 internal fragmentation이 될 경우 이는 external fragmentation가 되어 공간을 낭비하게 된다. external fragmentation을 해결하는 방법은 다음과 같다.

 

※ external fragmentation 해결 방법

• Storage compaction
  
  
• coalescing
  : 가용 리스트가 서로 인접해 있는 경우, 이들을 합쳐서 하나의 공간으로 사용
  
  
• place strategy
  : 새로운 데이터를 삽입할 때 낭비되는 공간을 최소화하기 위해 배치 전략을 사용
  
  ※ place strategy 종류
  - First-fit (가장 먼저 나오는 right size 공간에 삽입하는 방법)
  - Best-fit (가장 낭비되는 크기가 작은 right size 공간에 삽입하는 방법)
  - Worst-fit (가장 낭비되는 크기가 큰 right size 공간에 삽입하는 방법) - 재사용 위함

 

First-fit 전략인 경우 : 72 자리에 삽입
Best-fit 전략인 경우 : 57 자리에 삽입
Worst-fit 전략인 경우 : 72 자리에 삽입

 

---