RoomBookingResolver 0.0.1

RoomBookingResolver - External Merge Sorter

A high-performance .NET library for sorting large CSV files that exceed available memory using an external merge sort algorithm.

Overview

The ExternalMergeSorter is designed to handle sorting of extremely large CSV files (multiple gigabytes) without loading the entire file into memory. It uses a two-phase approach:

1. Split & Sort Phase: Divides the input file into manageable chunks, loads each chunk into memory, and sorts it
2. Merge Phase: Merges the sorted chunks back together while maintaining overall sort order

This approach allows you to sort arbitrarily large files limited only by disk space.

Features

• ✅ Sorts large CSV files exceeding available RAM
• ✅ Efficient memory usage with configurable chunk sizes
• ✅ Parallel processing support via cancellation tokens
• ✅ Conflict detection during merge operations
• ✅ Configurable output handling
• ✅ Automatic temporary file cleanup

Configuration

The sorter is configured via InputOptions in your appsettings.json:

{
  "InputOptions": {
    "InputFilePath": "/path/to/large-file.csv",
    "TempFileSize": 100000,
    "MergeChunkSize": 2,
    "CreateOutputFile": true,
    "OutputFileName": "sorted-output.csv",
    "OutputFilePath": "/path/to/output/"
  }
}

Configuration Parameters

Tuning Tips

• TempFileSize: Higher values reduce the number of temporary files but use more RAM. Set based on available memory:

  • 50,000 rows = ~minimal memory overhead
  • 500,000 rows = ~moderate memory use
  • 1,000,000+ rows = ~higher memory pressure

• MergeChunkSize: Controls how many files are merged per round:

  • 2 = binary merge (slowest but most memory-efficient)
  • 4-8 = balanced approach (recommended)
  • Higher = fewer merge rounds but higher memory/handle usage

Usage

Basic Example (Programmatic)

using Microsoft.Extensions.DependencyInjection;
using BookingResolverApp;
using BookingResolverApp.Interfaces;
using BookingResolverApp.Options;
using Microsoft.Extensions.Options;

// Set up dependency injection
var services = new ServiceCollection();

// Configure InputOptions
var inputOptions = new InputOptions
{
    InputFilePath = "/data/bookings.csv",
    TempFileSize = 100_000,
    MergeChunkSize = 2,
    CreateOutputFile = true,
    OutputFileName = "sorted-bookings.csv",
    OutputFilePath = "/data/output/"
};

services.AddSingleton(Options.Create(inputOptions));

// Register the sorter and its dependencies
services.AddSingleton<IExternalMergeSorter, ExternalMergeSorter>();
services.AddSingleton<IPathResolver, PathResolver>();
services.AddSingleton<IHelper, Helper>();
services.AddSingleton<IConflictDetector, ConflictDetector>();

var serviceProvider = services.BuildServiceProvider();
var sorter = serviceProvider.GetRequiredService<IExternalMergeSorter>();

// Execute the sort
using var cts = new CancellationTokenSource();
cts.CancelAfter(TimeSpan.FromHours(1)); // Optional timeout

var tempFiles = await sorter.SplitAndSortFiles(cts.Token);
Console.WriteLine($"Created {tempFiles.Count} sorted chunks");

// Merge all chunks
await sorter.MergeFiles(tempFiles, isFinalChunk: true, cts.Token);

// Clean up temporary files
await sorter.CleanupFiles();

Console.WriteLine("Sort complete!");

Using BookingResolver (Recommended)

The BookingResolver class wraps the sorter with additional features like conflict detection:

var result = await bookingResolver.RunAsync(cancellationToken);

if (result.Success)
{
    Console.WriteLine($"✓ Sort completed in {result.ElapsedMilliseconds}ms");
    Console.WriteLine($"✓ Conflicts detected: {result.Conflicts.Count}");
}
else
{
    Console.WriteLine($"✗ Error: {result.Message}");
}

How It Works

Phase 1: Split & Sort

Input File (5GB)
    ↓
Read in 100K-line chunks
    ↓
Sort each chunk in memory
    ↓
Write sorted chunks as temporary files
    ↓
bookings_1_sorted.tmp (500MB)
bookings_2_sorted.tmp (500MB)
bookings_3_sorted.tmp (500MB)
... (up to bookings_N_sorted.tmp)

Phase 2: Merge (with multiple rounds if needed)

Merge Round 1:
  bookings_1,2_merged.tmp + bookings_3,4_merged.tmp + ...
  
Merge Round 2:
  merged files from round 1 → fewer, larger merged files
  
Final Merge:
  All remaining sorted files → sorted-output.csv

Input File Format

The sorter expects CSV files with at least the following columns in order:

Room,StartDate,StartTime,EndDate,EndTime,GuestName,...
R101,2024-01-15,09:00,2024-01-15,11:00,John Doe,...
R102,2024-01-15,10:00,2024-01-15,12:00,Jane Smith,...
...

Sorting Criteria (in order):

1. Room ID (ascending)
2. Start Date & Time (ascending)

Error Handling

The sorter handles errors gracefully:

• Invalid CSV format: Parsing errors are caught and reported
• Disk space: Monitor disk usage; ensure enough space for temporary files
• Cancellation: Respects CancellationToken; gracefully exits mid-sort
• Cleanup: Always attempts to delete temporary .tmp files, even on error

Performance Characteristics

Times are approximate and depend on disk speed, CPU, and data distribution.

Conflict Detection

When MergeFiles is called with isFinalChunk = true, the sorter checks for booking conflicts (overlapping time slots in the same room) and reports them via IConflictDetector.

Thread Safety

The sorter is not thread-safe. Create a separate instance per thread or use proper synchronization.

Dependencies

• Microsoft.Extensions.Options - Configuration management
• IPathResolver - Path resolution for input/output/temp files
• IHelper - CSV parsing and sorting comparers
• IConflictDetector - Conflict detection during merge

License

See LICENSE file in the repository.