Caching parts of file

[virzak]

I'm working on an application which processes a large binary file.
The application does not modify the file, but reads the same location multiple times.

What's the best way of caching bytes / pages?

Here is what I've considered:

• Memory mapped files, but doesn't seem like it does any caching.
• Introducing CachingFileStream that derives from FileStream and checking MemoryCache to see if requested bytes have been previously cached.

Appreciate any advice if there's any other solution that's already available.

[gfoidl]

How much is read from / around the "same location"?
Is the move to another location always the same or is it more random-access like?

So is it possible to read into a (rented) byte[] and use that as simple and fast in-memory cache for this?
Or is the use of Pipelines possible?

[virzak]

The most common scenario is that the reads are always contiguous. The size is not identical. For example the reads could be:

from	to
400	8000
6000	8155
6000	10000
7500	9500

This should be accessed concurrently, yes.

Also how is something like stored?

One idea I had was to cache blocks of identical size (eg.4096) for O(1) insertion and lookup.

from	to	cached?	cache blocks
400	8000	n	0 - 8192
6000	8155	y
6000	10000	n	8192 - 12288
7500	9500	y

[gfoidl]

Yep, I also think the way via having blocks of either identical size (like slabs) or the requested size (if known beforehand, in order have the access contiguous) should be used.
Attach to each block a "last accessed" timestamp and have a scavenger-timer that removes not used blocks from memory.

For implementation you could do something like "virtual blocks", i.e. from API point of view assume that the blocks are there and access them via offset in the file. The actual implementation either returns that block from the cache (e.g. dictionary) or loads it (and adds to dic).
Fixed sized blocks are way easier to implement, though.

[gfoidl]

Also how is something like stored?

Well, had a free minute...for the block-based approach I'd do something like the example below (not tested, etc.).

CachedReadOnlyRandomAccess demo

using System;
using System.Buffers;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using Microsoft.Win32.SafeHandles;

const string Path = "test.dat";
const int BlockSize = 64;

await CreateHugeFile(Path, size: 100);  // well...

await using CachedReadOnlyRandomAccess randomAccess = new(Path, BlockSize, timeToKeepBlockInCache: TimeSpan.FromMinutes(1d));

IFileBlock block0 = randomAccess.GetFileBlock(0);
IFileBlock block63 = randomAccess.GetFileBlock(63);
IFileBlock block64 = randomAccess.GetFileBlock(64);

Debug.Assert(block0 == block63);
Debug.Assert(block63 != block64);

block63.SetMode(inUse: true);
UseFileBlock(block63);          // Should be in try-finally?
block63.SetMode(inUse: false);

block64.SetMode(inUse: true);
UseFileBlock(block64);
block64.SetMode(inUse: false);

Console.WriteLine();
foreach (IFileBlock fileBlock in randomAccess.GetFileBlocks())
{
    fileBlock.SetMode(inUse: true);
    UseFileBlock(fileBlock);
    fileBlock.SetMode(inUse: false);
}
Console.WriteLine();

Console.WriteLine("\nWait for scavenge");
Console.ReadKey();

IFileBlock block63Again = randomAccess.GetFileBlock(63);
Debug.Assert(block63 != block63Again);

static void UseFileBlock(IFileBlock fileBlock)
{
    int sum = 0;
    foreach (byte b in fileBlock.Data) sum += b;

    Console.WriteLine($"Block at {fileBlock.Offset,2} has length {fileBlock.Length}, range [{fileBlock.Offset,2}, {fileBlock.Offset + fileBlock.Length - 1,2}], sum of data: {sum}");
}

static async ValueTask CreateHugeFile(string path, long size)
{
    using SafeFileHandle fileHandle = File.OpenHandle(path, FileMode.Create, FileAccess.Write);
    byte[] data = Enumerable.Range(0, (int)size).Select(i => (byte)i).ToArray();
    await RandomAccess.WriteAsync(fileHandle, data, 0);
}

public sealed class CachedReadOnlyRandomAccess : IAsyncDisposable
{
    private readonly SafeFileHandle _fileHandle;
    private readonly int _blockSize;
    private readonly long _blockCount;
    private readonly long _fileLength;
    private readonly ConcurrentDictionary<long, FileBlock> _cache = new();
    private readonly Timer? _scavengeTimer;
    private readonly TimeSpan _timeToKeepBlockInCache;

    public CachedReadOnlyRandomAccess(
        string fileName,
        int blockSize = 1024,
        TimeSpan? timeToKeepBlockInCache = default)
    {
        _fileHandle = File.OpenHandle(fileName, options: FileOptions.RandomAccess);
        _fileLength = RandomAccess.GetLength(_fileHandle);
        _blockSize = blockSize;
        _blockCount = GetSlabCount(_fileLength, blockSize);

        _timeToKeepBlockInCache = timeToKeepBlockInCache ?? TimeSpan.FromMinutes(1);

        if (_timeToKeepBlockInCache != Timeout.InfiniteTimeSpan)
        {
            _scavengeTimer = new Timer(this.Scavenge, null, _timeToKeepBlockInCache, _timeToKeepBlockInCache);
        }
    }

    public ValueTask DisposeAsync()
    {
        _fileHandle.Dispose();
        return _scavengeTimer?.DisposeAsync() ?? ValueTask.CompletedTask;
    }

    public long BlockCount => _blockCount;

    public IFileBlock GetFileBlock(long offset)
    {
        if (offset > _fileLength)
        {
            throw new ArgumentOutOfRangeException(nameof(offset));
        }

        long slabIndex = GetSlabIndex(offset);
        return _cache.GetOrAdd(slabIndex, static (idx, randomAccess) => new FileBlock(randomAccess, idx), this);
    }

    private void Scavenge(object? _)
    {
        DateTimeOffset now = DateTimeOffset.UtcNow;
        DateTimeOffset maxAge = now - _timeToKeepBlockInCache;
        int count = 0;

        // Just a best effort solution.
        foreach (KeyValuePair<long, FileBlock> kvp in _cache)
        {
            if (kvp.Value.CanBeScavenged(maxAge))
            {
                _cache.TryRemove(kvp);
                kvp.Value.Dispose();
                count++;
            }
        }

#if DEBUG
        Console.WriteLine($"Scavenge: removed {count} items from cache");
#endif
    }

    private static long GetSlabCount(long length, int blockSize) => (length + blockSize + 1) / blockSize;
    private long GetSlabIndex(long offset) => offset / _blockSize;

    public IEnumerable<IFileBlock> GetFileBlocks()
    {
        for (long i = 0; i < _blockCount; ++i)
        {
            long offset = i * _blockSize;
            yield return this.GetFileBlock(offset);
        }
    }

    private class FileBlock : IFileBlock, IDisposable
    {
        private readonly CachedReadOnlyRandomAccess _randomAccess;
        private readonly byte[] _block;
        private readonly long _offset;
        private readonly int _bytesRead;

        private DateTimeOffset _lastAccessed;
        private bool _inUse;

        public long Index { get; }

        public FileBlock(CachedReadOnlyRandomAccess randomAccess, long index)
        {
            this.Index = index;
            _randomAccess = randomAccess;
            _block = ArrayPool<byte>.Shared.Rent(randomAccess._blockSize);

            _offset = index * randomAccess._blockSize;
            _bytesRead = RandomAccess.Read(randomAccess._fileHandle, _block.AsSpan(0, randomAccess._blockSize), _offset);
        }

        public void Dispose()
        {
            Volatile.Write(ref _inUse, false);
            ArrayPool<byte>.Shared.Return(_block);
        }

        public long Offset => _offset;
        public int Length => _bytesRead;

        private ReadOnlySpan<byte> Span => _block.AsSpan(0, _randomAccess._blockSize);

        public ReadOnlySpan<byte> Data
        {
            get
            {
                if (!Volatile.Read(ref _inUse))
                {
                    throw new InvalidOperationException("Block must be marked as InUse first");
                }

                _lastAccessed = DateTimeOffset.UtcNow;
                return _block.AsSpan(0, _bytesRead);
            }
        }

        public void SetMode(bool inUse) => Volatile.Write(ref _inUse, inUse);

        public bool CanBeScavenged(DateTimeOffset maxAge) => !Volatile.Read(ref _inUse) && _lastAccessed <= maxAge;
    }
}

public interface IFileBlock
{
    long Offset { get; }
    int Length { get; }
    ReadOnlySpan<byte> Data { get; }

    void SetMode(bool inUse);
}

The case with contiguous reads that cross a block-boundary isn't covered. That's a harder problem, which could be solved by

• create a separate instance with different blocksize, so that no crossing of the boundary will occur
• read from the current and the next block, then combine into one array -- thus for usage it would be good to layer some kind of manager on top of this type so that is "just works"
• ...

For the forward scans you could go crazy and do some sort of prefetching, i.e. populate the cache with the next block before it is requested, so that the item is already in the cache, and so on.

Quite an interesting use case 😄.

[virzak]

@gfoidl wow, you're fast! Thanks. Will use part of this in a CachingFileStream unless you had an intention to create a OSS library out of this.

@adamsitnik, since you are one of leading devs on everything FileStream, can you confirm that something like this isn't currently available and we're not reinventing the wheel here?

Update: after visiting your Wikipedia page, no wonder you're so fast :)

[gfoidl]

you had an intention to create a OSS library out of this.

I don't have that intention. Use it as it fit your needs. But if your solution evolves into an OSS lib, I'm happy to help out.

Update: after visiting your Wikipedia page, no wonder you're so fast :)

😀

[adamsitnik]

since you are one of leading devs on everything FileStream, can you confirm that something like this isn't currently available and we're not reinventing the wheel here?

We don't have anything for caching random reads, but contiguous reads should work well with default FileStream buffering.

What you need to do:

• create a FileStream with large bufferSize (64k? I am not sure how big your reads are).
• use Seek, not Position (Unify BufferedFileStreamStrategy seeking #78457) to change the file offset
• if my understanding is correct the next read will reuse buffered data:

runtime/src/libraries/System.Private.CoreLib/src/System/IO/Strategies/BufferedFileStreamStrategy.cs

Lines 936 to 942 in 031a16a

	// If the offset of the updated seek pointer in the buffer is still legal, then we can keep using the buffer:
	if (0 <= readPos && readPos < _readLen)
	{
	_readPos = (int)readPos;
	// Adjust the seek pointer of the underlying stream to reflect the amount of useful bytes in the read buffer:
	_strategy.Seek(_readLen - _readPos, SeekOrigin.Current);
	}

[virzak]

And in context of the video editor example the other requirement seems to be:

• Keeping a handle to FileStream at the application level. In a multi-tab application it would be FileStream per tab.

Is that correct?