Получение hash-а SHA256 многопоточно

#c_sharp #многопоточность #хеширование

Есть файл, файл делится на блоки (последовательности байтов).
Как многопоточно вычислить значение hash-функции SHA256 для каждого блока файла,
используя Thread-ы? 
    

Ответы

Ответ 1

Сначала давайте напишем функцию для одного блока.

public static class Sha256Service
{
    private const long blockSize = 16384;

    public static byte[] CalculateHash(string filename, int blockIndex)
    {
        using (var stream = new FileStream(filename, FileMode.Open, FileAccess.Read))
        using (var hasher = new SHA256Managed())
        {
            stream.Seek(blockIndex * blockSize, SeekOrigin.Begin);
            var buffer = new byte[blockSize];
            var actualLength = stream.Read(buffer, 0, buffer.Length);

            return hasher.ComputeHash(buffer, 0, actualLength);
        }
    }
}


Теперь эту функцию надо вызывать параллельно для каждого блока в файле. Самостоятельно
создавать Thread трудоёмко, я бы использовал PLINQ.

Количество блоков вычисляется по хитрой формуле которую каждый программист просто
должен однажды заучить:

var blockCount = (fileSize + blockSize - 1)/blockSize;


Дописываем второй метод для параллельного вызова первого:

public static byte[][] Calculate(string filename)
{
    var blockCount = (int)((new FileInfo(filename).Length + blockSize)/blockSize);
    var result = new byte[blockCount][];

    Parallel.For(0, blockCount, (i) => result[i] = calculate(filename, i));

    return result;
}


Файл будет открыт для чтения в нескольких потоках. Это не представляет проблемы для
RAID-массивов и твердотельных дисков, но, насколько я узнал на одиночных жёстких дисках
производительность будет снижаться.

Если делать через Thread, то код начнёт выглядеть гораздо страшнее. Приблизительно так:

static byte[][] Calculate2(string filename)
{
    var blockCount = (int)((new FileInfo(filename).Length + blockSize) / blockSize);
    var result = new byte[blockCount][];
    var threads = new Thread[blockCount];

    for (int i = 0; i < blockCount; i++)
    {
        var i1 = i;
        threads[i] = new Thread(() => result[i1] = CalculateHash(filename, i1));
        threads[i].Start();
    }

    for (int i = 0; i < blockCount; i++)
        threads[i].Join();

    return result;
}


На что здесь нужно обратить внимание? Во-первых, на то, как хитро дублируется переменная
i внутри первого цикла for. Это известный паттерн для работы с переменными цикла внутри
замыканий. Страшно.

Во-вторых, у Thread нет метода WaitAll, приходится писать такой же почти вручную.

ОТВЕТ НА ДОПОЛНИТЕЛЬНЫЙ ВОПРОС В КОММЕНТАРИИ

Приведённый код мог бы обрабатывать и файлы, большие, чем ОЗУ, если бы не одно «но» —
он создает поток на каждый блок, а у потока размер стека по умолчанию составляет 1
мегабайт.

Опять-таки, теория утверждает, что такое количество потоков не будут выполняться
и в самом деле параллельно потому что потоков гораздо больше, чем ядер.

Задание тестовое, и я бы не стал заморачиваться, положив количество потоков равным
4 или 8. Тогда хеши блоков удобнее было бы считать большими кусками, состоящими из
большого количества последовательных блоков. Делать можно было бы в 4 или 8 потоков.
Метод CalculateHash стал бы сложнее:

public static void CalculateHash2(string filename, int inclusiveStartBlock, int exclusiveEndBlock,
byte[][] hashes)
{
    var buffer = new byte[bufferSize];

    using (var stream = new FileStream(filename, FileMode.Open, FileAccess.Read))
    using (var hasher = new SHA256Managed())
    {
        stream.Seek(inclusiveStartBlock * blockSize, SeekOrigin.Begin);

        for (int i = inclusiveStartBlock; i < exclusiveEndBlock; i++)
        {
            var actualLength = stream.Read(buffer, 0, buffer.Length);
            hashes[i] = hasher.ComputeHash(buffer, 0, actualLength);
        }
    }
}


Метод Calcualte для 4-х потоков стал бы выглядеть так:

public static byte[][] Calculate3(string filename)
{
    var blockCount = (int)((new FileInfo(filename).Length + blockSize) / blockSize);
    var result = new byte[blockCount][];
    var thread1 = new Thread(() => CalculateHash2(filename, 0, blockCount/4, result));
    var thread2 = new Thread(() => CalculateHash2(filename, blockCount/4, blockCount/2,
result));
    var thread3 = new Thread(() => CalculateHash2(filename, blockCount/2, 3*blockCount/4,
result));
    var thread4 = new Thread(() => CalculateHash2(filename, 3*blockCount/4, blockCount,
result));

    thread1.Start();
    thread2.Start();
    thread3.Start();
    thread4.Start();

    thread1.Join();
    thread2.Join();
    thread3.Join();
    thread4.Join();

    return result;
}


Считаем количество блоков, выделяем память под хеши, разбиваем все блоки на 4 почти
равные части, и для блоков каждой части считаем хеши в 4-х разных потоках.

Вроде всё.


Ответ 2

Если вам нужно посчитать просто хэши блоков, то нет ничего сложного: читаете по N
байт из файла, скармливаете эти N байт алгоритму и получаете ответ. Каждый поток получает
номер блока и читает байты от N * i до max(N * (i + 1), file_length), где i -- номер
блока, начинающийся с нуля.

Если же вам нужно вычислить хэш для всего файла поблочно, то используйте hash tree
(русская статья содержит описание Tiger tree hash, использующего Tiger hash, но фактически
можно использовать другой алгоритм). Идея состоит в том, что для каждого блока вы вычисляете
хэш, затем вычисляете хэши для каждой пары (или более) и так вверх по дереву, пока
не получите единственный хэш. Этот алгоритм используется в P2P сетях для проверки целостности
файлов.

Опишите подробнее, что именно вам нужно сделать и с чем возникли трудности, и я дополню
ответ.