大文件外排序

一道固定内存下进行文件外排序的算法题解，虽然说是外排，但是根据题目要求，还是使用内排序的方式实现

题目

假设您拥有⼀台电脑

1. 内存为 4GB
2. 磁盘⽆限空间
3. 磁盘上 data ⽬录下有⼀万份大小为 8GB 的⽂件
4. ⽂件内容每⾏开头前三个字⺟都为最基础的 ASCII 码值
5. ⽂件内容是⽆序的
6. 该电脑能打开的⽂件描述符⽆限多

现要求将 data ⽬录下的所有⽂件合并为⼀个超⼤⽂件且合并后的⽂件中的内容使⽤每⾏前三个字⺟做升序排列，如果前三个字⺟相同则随机即可，要求考虑最快速度下最⼩资源占⽤。

输入样例

⽂件 A 内容：
aaaAAA
aabAAA

⽂件 B 内容：
aaaBBB
aaaCCC
aacBBB

输出结果

aaaAAA
aaaBBB
aaaCCC
aabAAA
aacBBB
 或 
aaaCCC
aaaBBB
aaaAAA
aabAAA
aacBBB

思路

粗略一看像是外排序的问题，但根据要求有几个特点

1. 排序依据：每行开头的 ASCII 码
2. 文件描述符无上限

如果使用外排序，将会产生一些保留中间阶段排序的临时文件，反而增加了磁盘和 I/O 开销

• 首先考虑排序依据，ASCII 码一共 128 个，排除控制字符后可显示的有 95 个，根据题目描述每行开头固定三位，也就是共有 $95^3$ 个，每个 ASCII 占用一个字节，最大占用量为 $95^3\times3=2572125\approx2.45MB$，这样去重后排序的内存消耗可以忽略了
• 其次是文件描述符，对应的数据结构为 fd -> 文件指针 -> 文件，内存中不读取内容时占用很小，也可以使用内存进行处理，同时为减少数据量的拷贝，使用 syscall 直接进行文件操作，记录每一行位置的起始和长度，在排序后进行写入即可
• 因为以上没有提到 CPU 核数的问题，所以不考虑并发，仅使用单线程处理

代码

package main

import (
	"os"
	"sort"
	"syscall"
)

const bufferSize = 1024 * 1024 * 1024 // 缓冲区暂定为 1GB

type File struct {
	fd     int   // 文件描述符 
	offset int64 // 行偏移量 
	size   int   // 行长度 
}

func main() {
	storage := make(map[string][]*File)

	// 读取文件内容并构建 ASCII 码映射 
	if err := readFiles(storage); err != nil {
		panic(err)
	}

	// 获取所有 key 并排序 
	keys := make([]string, 0, len(storage))
	for key := range storage {
		keys = append(keys, key)
	}
	sort.Strings(keys)

	resultFd, err := syscall.Open("result", syscall.O_WRONLY|syscall.O_CREAT, 0644)
	if err != nil {
		panic(err)
	}
	defer syscall.Close(resultFd)

	// 将文件内容写入结果文件 
	for _, key := range keys {
		files := storage[key]
		for _, file := range files {
			if _, err := syscall.Seek(file.fd, file.offset, 0); err != nil {
				panic(err)
			}
			buffer := make([]byte, file.size)
			if _, err := syscall.Read(file.fd, buffer); err != nil {
				panic(err)
			}
			if _, err := syscall.Write(resultFd, buffer[:file.size]); err != nil {
				panic(err)
			}
		}
	}

	// 关闭所有打开的文件 
	for _, files := range storage {
		for _, file := range files {
			syscall.Close(file.fd)
		}
	}
}

func readFiles(storage map[string][]*File) error {
	files, err := os.ReadDir("data")
	if err != nil {
		return err
	}

	for _, entry := range files {
		fd, err := syscall.Open("data/"+entry.Name(), syscall.O_RDONLY, 0)
		if err != nil {
			return err
		}

		buffer := make([]byte, bufferSize)
		var lineBuffer []byte
		var offset int64

		for {
			n, err := syscall.Read(fd, buffer)
			if err != nil {
				return err
			}
			if n == 0 {
				break // EOF
			}

			for i := 0; i < n; i++ {
				if buffer[i] == '\n' {
					key := string(lineBuffer)[:3]
					storage[key] = append(storage[key], &File{fd: fd, offset: offset - int64(len(lineBuffer)), size: len(lineBuffer) + 1})
					lineBuffer = nil
				} else {
					lineBuffer = append(lineBuffer, buffer[i])
				}
				offset += 1
			}
		}
	}
	return nil
}