Design Merging

Requirement

Shuffled Lists of data stored in disks (files) (in the output directory)

File name convention: unmerged.<partition #> (i.e. unmerged.3)

Config

Idea

1. Input: total n-partitions, partially sorted
2. Output: Totally sorted n-partitions (or lower)
3. Like merge sort, partition the files. Then, proceed merging

1. 위 그림의 블럭 하나하나가 파일 하나라고 생각하면 됨. partition 단계까지는 문제 없음. 파일 하나 하나 떨어지는 것으로 생각하면 됨.
2. 이 파일 하나하나를 MultiFile에 넣어줌. (우선 파일 하나씩)
3. 그 다음에 MultiFile 2개씩 모은 다음에, 다른 MultiFile에 비교하면서 레코드 하나씩 넣어줌 (merge 단계와 유사, 1번 매니저에서 레코드 하나 꺼내왔다가, 2번 매니저에서 레코드 하나 꺼내왔다가.... 비교하면서)
4. 위 단계 반복. 그러면 MultiFile가 최종적으로 하나 남게됨. 그러면 단계 끝.

Components

• MultiFile: manage multiple partitions (files) as a single file (실제로 없음)
  • 여러 partition들을 List[File]로 두고 관리
  • Read n records → automatically change file if reached EOF on each file (MultiFileRead class)
  • Write n records → automatically create / change file if reached max capacity (32MB) (MultiFileWrite class)
• MergeUtil: 실제로 merge를 수행하는 파트
  • mergeFiles(workDir: File, mfl: List[MultiFileRead]): MultiFileRead
    • recursive 구조를 위해 MultiFileRead를 리턴
    • partition → merge
    • merge는 MultiFileRead 인스턴스 2개를 받아 처리. MultiFileWrite를 하나 만들고, 각 MultiFileRead에서 레코드를 하나씩 읽어와 MultiFileWrite에 쓴다. (데이터 비교하면서 작은 순으로) 다 쓴 이후에 MultiFileRead 인스턴스에 해당되는 파일을 모두 지우고, MultiFileWrite를 MultiFileRead로 변환하여 리턴한다.
    • 여기서 file renaming을 하지 않는다. 밖에서 따로 해줘야 한다.

To Use

construct working directory (output directory) to File -> new File(directory)
construct List[MultiFileRead]: output directory listing 한 뒤에 
	fileList.map(f => MultiFileRead(List(f)))
그 다음에 MergeUtil.mergeFile(workdir, mfl)

Consequence

Final Lists of data stored in disks (files)

File name convention: partition.<partition #> (removed idx range)