Java 文件高级技术(二):随机读写文件

  1. RandomAccessFile 的概念?
    答:

    • RandomAccessFile 可以随机读写,是更为接近操作系统API,在实现一些系统程序时,它比流更为方便高效
    • 可以利用 RandomAccessFile 设计实现一个类似 Map 的简单的键值数据库。
  2. RandomAccessFile 的构造方法 public RandomAccessFile(String name, String mode) throws FileNotFoundExceptionpublic RandomAccessFile(File file, String mode) throws FileNotFoundException 中参数 mode 的含义是?
    答:mode 表示打开模式,可以有 4 个取值。

    • r:只用于读。
    • rw:用于读和写。
    • rws:和 rw 一样,用于读和写。另外,它要求文件内容和元数据的任何更新都同步到设备上。
    • rwd:和 rw 一样,用于读和写。另外,它要求文件内容的任何更新都同步到设备上,和 rws 的区别是,元数据的更新不要求同步。
  3. 概述一下 RandomAccessFile 的内部原理?
    答:

    • RandomAccessFile 虽然不是 InputStreamOutputStream 的子类,但它也有类似于读写字节流的方法。另外,它还实现了 DataInput/DataOutput 接口。
    • RandomAccessFile 内部有一个文件指针,指向当前读写的位置,各种 read/write 操作都会自动更新该指针。与流不同的是,RandomAccessFile 有相关方法可以获取该指针,也可以更改该指针。
    • RandomAccessFile 是通过本地方法,最终调用操作系统的 API 来实现文件指针调整的。
  4. 使用 RandomAccessFile 设计一个键值数据库 BasicDB?
    答:

    • 将键值对分为两部分,值保存在单独的 .data 文件中,值在 .data 文件中的位置和键称为索引,索引保存在 .meta 文件中。
    • .data 文件中,每个值占用的空间固定,固定长度为 1024,前 4 个字节表示实际长度,然后是实际内容,实际长度不够 1020 的,后面是补白字节 0
    • 索引信息既保存在 .meta 中,也保存在内存中,在初始化时,全部读入内存,对索引的更新不会立即更新文件,调用 flush() 方法才会更新。
    • 删除键值对不修改 .data 文件,但会从索引中删除并记录空白空间,下次添加键值对的时候会重用空白空间,所有的空白空间也记录到 .meta 文件中。
    • 简单起见,暂不考虑由于并发访问、异常关闭等引起的一致性问题。
  5. 【笔试题】使用 RandomAccessFile 实现一个键值数据库 BasicDB?
    答:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    // BasicDB 定义了如下静态变量
    private static final int MAX_DATA_LENGTH = 1020; // 保存键值对,键为 String 类型,值为 byte[] 类型。为便于实现,假定值即 byte[] 的长度不超过 1020
    private static final byte[] ZERO_BYTES = new byte[MAX_DATA_LENGTH]; // 补白字节
    private static final String DATA_SUFFIX = ".data"; // 数据文件扩展名
    private static final String META_SUFFIX = ".meta"; // 元数据文件扩展名,包括索引和空白空间数据

    // 内存中表示索引和空白空间的数据结构
    Map<String, Long> indexMap; // 索引信息,键->值在 .data 文件中的位置
    Queue<Long> gaps; // 空白空间,值为在 .data 文件中的位置


    // 表示文件的数据结构
    RandomAccessFile db; // 值数据文件
    File metaFile; // 元数据文件

    // 构造方法
    public BasicDB(String path, String name) throws IOException {
    File dataFile = new File(path + name + DATA_SUFFIX);
    db = new RandomAccessFile(dataFile, "rw");
    if(metaFile.exist()) {
    loadMeta(); // 元数据文件存在时,调用 loadMeta() 方法将元数据加载到内存
    } else {
    indexMap = new HashMap<> ();
    gaps = new ArrayDeque();
    }
    }

    // 保存键值对的方法
    // 设计的值是 byte 数组,这看上去是一个限制,不便使用,这里主要是为了优化,因为任何数据都可以转化为 byte 数组保存。对于字符串,可以使用 getBytes() 方法,对于对象,可以使用之前介绍的流转换成 byte 数组
    public void put(String key, byte[] value) throws IOException {
    Long index = indexMap.get(key);
    if(index == null) {
    index = nextAvailablePos();
    indexMap.put(key, index);
    }
    writeData(index, value);
    }

    // nextAvailable() 方法
    private long nextAvailablePos() throws IOException {
    if(!gaps.isEmpty()) {
    return gaps.poll();
    } else {
    return db.length;
    }
    }

    // 写值数据
    private void writeData(long pos, byte[] data) throws IOException {
    if(data.length > MAX_DATA_LENGTH) {
    throw new IllgalArgumentException("maximum allowed length is " + MAX_DATA_LENGTH + ", data length is " + data.length);
    }
    db.seek(pos);
    db.writeInt(data.length);
    db.write(data);
    db.write(ZERO_BYTES, 0, MAX_DATA_LENGTH - data.length);
    }

    // 根据键获取值
    public byte[] get(String key) throws IOException {
    Long index = indexMap.get(key);
    if(index != null) {
    return getData(index);
    }
    return null;
    }

    // 获取数据
    private byte[] getData(long pos) throws IOException {
    db.seek(pos);
    int length = db.readInt();
    byte[] data = new byte[length];
    db.readFully(data); // 读够内容
    return data;
    }

    // 删除键值对
    public void remove(String key) {
    Long index = indexMap.remove(key); // 从索引结构中删除
    if(index != null) {
    gaps.offer(index); // 添加到空白空间队列中
    }
    }

    // 同步元数据
    public void flush() throws IOException {
    saveMeta();
    db.getFD().sync(); // getFD() 方法会返回文件描述符,sync() 方法会确保文件内容保存到设备上
    }

    // 保存元数据
    private void saveMeta() throws IOException {
    DataOutputStream out = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(metaFile)));
    try {
    saveIndex(out);
    saveGaps(out);
    } finally {
    out.close();
    }
    }

    // 保存索引信息
    private void saveIndex(DataOutputStream out) throws IOException {
    out.writeInt(indexMap.size());
    for(Map.Entry<String, Long> entry : indexMap.entrySet()) {
    out.writeUTF(entry.getKey());
    out.writeLong(entry.getValue());
    }
    }

    // 保存空白空间信息
    private void saveGaps(DataoutputStream out) throws IOException {
    out.writeInt(gaps.size());
    for(Long pos : gaps) {
    out.writeLong(pos);
    }
    }

    // saveMeta() 的逆操作
    private void loadMeta() throws IOException {
    DataInputStream in = new DataInputStream(new BufferedInputStream(new FileInputStream(metaFile));
    try {
    loadIndex(in);
    loadGaps(in);
    } finally {
    in.close();
    }
    }

    // 加载索引
    private void loadIndex() throws IOException {
    int size = in.readInt();
    indexMap = new HashMap<String, Long> ((int) (size / 0.75f) + 1, 0.75f);
    for(int i=0; i<size; i++) {
    String key = in.readUTF();
    long index = in.readLong();
    indexMap.put(key, index);
    }
    }

    // 加载空白空间
    private void loadGaps(DataInputStream in) throws IOException {
    int size = in.readInt();
    gaps = new ArrayDeque<> (size);
    for(int i = 0; i<size; i++) {
    long index = in.readLong();
    gaps.add(index);
    }
    }

    // 关闭数据库
    public void close() throws IOException {
    flush();
    db.close();
    }