Создание контрольной суммы на графе объектов - PullRequest
14 голосов
/ 18 марта 2011

Этот вопрос относится к этому , но я думаю, что его следует задавать отдельно.

У меня сложный граф экземпляров объектов. Теперь я хотел бы создать контрольную сумму для этого графа объекта непосредственно в памяти, чтобы определить, были ли внесены в него изменения с момента последнего сохранения контрольной суммы в графе объекта. Расчет контрольной суммы должен быть быстрым и не должен занимать слишком много памяти.

Как я понимаю, сейчас наилучшим решением, вероятно, было бы создание криптографического ключа на двоичной сериализованной форме графа объектов (исправьте меня, если я ошибаюсь). Но это приходит с несколькими вопросами:

  1. Как мне сериализовать объект? Он должен быть быстрым, а не потреблять слишком много памяти. Также это всегда должен быть надежно сериализован так же. Если я использую сериализацию .NET по умолчанию, могу ли я быть действительно уверен, что созданный двоичный поток всегда одинаков, если фактические данные совпадают? Я сомневаюсь в этом.
  2. Так что же может быть альтернативным способом сериализации, который не займет много времени для реализации?

Обновление:

Что вы думаете об этом подходе:

  1. перемещаться по графику и объект foreach в графе создать стандартный int хеш-код с использованием это алгоритм (но исключая элементы ссылочного типа, представляющие узлы в графе). Добавить каждый хэш-код в список целых чисел
  2. преобразовать список целых чисел в байт массив
  3. создать хеш в байтовом массиве используя MD5, CRC или аналогичный

Упомянутый алгоритм GetHashCode должен быстро вычислить хеш-код, который достаточно безопасен для столкновения для одного объекта, который принимает во внимание только его примитивные члены. Исходя из этого, байтовый массив также должен быть довольно безопасным при столкновении представлением графа объекта и хеша MD5 / CRC для него.

Ответы [ 5 ]

9 голосов
/ 21 марта 2011

Вместо двоичной сериализации вы можете использовать http://code.google.com/p/protobuf-net/, а затем вычислить криптографический хеш.Говорят, что protobuf более компактен, чем Bin Ser (см., например, http://code.google.com/p/protobuf-net/wiki/Performance).

Я добавлю это, учитывая, что вам не нужно сериализоваться.Было бы лучше использовать Reflection и «перемещаться» по объектам, вычисляющим ваш хеш (таким же образом различные сериализаторы «пересекают» ваш объект).См., Например, Использование отражения в C # для получения свойств вложенного объекта

После долгих раздумий и услышав, что сказал @Jon, я могу сказать вам, что моя "вторичная" идея (используя Reflection) ОЧЕНЬ ОЧЕНЬ ОЧЕНЬ сложно, если вы не хотите потратить неделю на написание анализатора объектов.Да, это выполнимо ... Но какое представление вы бы дали данным до вычисления хеша?Чтобы было ясно:

two strings
"A"
"B"

ясно "A", "B"! = "AB", "".Но MD5 («A») в сочетании с MD5 («B») == MD5 («AB») в сочетании с MD5 («»).Вероятно, лучше всего предварительно добавить длину (поэтому, используя нотацию Pascal / BSTR)

И null значения?Какое «сериализованное» значение они имеют?Еще один вопрос.Ясно, что если вы сериализуете строку как длину + строку (так, чтобы решить предыдущую проблему), вы можете сериализовать ноль просто как "null" (без длины) ... А объекты?Вы бы добавили идентификатор типа объекта?Это было бы конечно лучше.В противном случае объекты переменной длины могут создать тот же беспорядок, что и строки.

Используя BinaryFormatter (или, возможно, даже protobuf-net), вам не обязательно где-то сохранять сериализованный объект, потому что они оба поддерживают потоковую передачу ...Пример

public class Hasher : Stream
{
    protected readonly HashAlgorithm HashAlgorithm;

    protected Hasher(HashAlgorithm hash)
    {
        HashAlgorithm = hash;
    }

    public static byte[] GetHash(object obj, HashAlgorithm hash)
    {
        var hasher = new Hasher(hash);

        if (obj != null)
        {
            var bf = new BinaryFormatter();
            bf.Serialize(hasher, obj);
        }
        else
        {
            hasher.Flush();
        }

        return hasher.HashAlgorithm.Hash;
    }

    public override bool CanRead
    {
        get { throw new NotImplementedException(); }
    }

    public override bool CanSeek
    {
        get { throw new NotImplementedException(); }
    }

    public override bool CanWrite
    {
        get { return true; }
    }

    public override void Flush()
    {
        HashAlgorithm.TransformFinalBlock(new byte[0], 0, 0);
    }

    public override long Length
    {
        get { throw new NotImplementedException(); }
    }

    public override long Position
    {
        get
        {
            throw new NotImplementedException();
        }
        set
        {
            throw new NotImplementedException();
        }
    }

    public override int Read(byte[] buffer, int offset, int count)
    {
        throw new NotImplementedException();
    }

    public override long Seek(long offset, SeekOrigin origin)
    {
        throw new NotImplementedException();
    }

    public override void SetLength(long value)
    {
        throw new NotImplementedException();
    }

    public override void Write(byte[] buffer, int offset, int count)
    {
        HashAlgorithm.TransformBlock(buffer, offset, count, buffer, offset);
    }
}

static void Main(string[] args)
{
    var list = new List<int>(100000000);

    for (int i = 0; i < list.Capacity; i++)
    {
        list.Add(0);
    }

    Stopwatch sw = Stopwatch.StartNew();
    var hash = Hasher.GetHash(list, new MD5CryptoServiceProvider());
    sw.Stop();
    Console.WriteLine(sw.ElapsedMilliseconds);
}

Я определяю класс Hasher, который получает сериализацию объекта (фрагмент за раз) и вычисляет хэш в «потоковом режиме».Использование памяти O (1).Время явно O (n) (с n "размер" сериализованного объекта).

Если вы хотите использовать protobuf (но помните, что для сложных объектов необходимо, чтобы они были помечены его атрибутами (или атрибутами WCF или ...))

public static byte[] GetHash<T>(T obj, HashAlgorithm hash)
{
    var hasher = new Hasher(hash);

    if (obj != null)
    {
        ProtoBuf.Serializer.Serialize(hasher, obj);
        hasher.Flush();
    }
    else
    {
        hasher.Flush();
    }

    return hasher.HashAlgorithm.Hash;
}

единственное «большое» отличие состоит в том, что protobuf не Flush поток, поэтому мы должны это сделать, и он НАСТОЯЩИМ хочет, чтобы тип корневого объекта был напечатан, а не простой «объект».

Ох ... и на ваш вопрос:

Как мне сериализовать объект?Это должно быть быстро и не потреблять слишком много памяти.Также он всегда должен быть надежно сериализован одинаково.Если я использую сериализацию .NET по умолчанию, могу ли я быть действительно уверен, что созданный двоичный поток всегда одинаков, если точные данные совпадают?Я сомневаюсь в этом.

List<int> l1 = new List<int>();

byte[] bytes1, bytes2;

using (MemoryStream ms = new MemoryStream())
{
    new BinaryFormatter().Serialize(ms, l1);
    bytes1 = ms.ToArray();
}

l1.Add(0);
l1.RemoveAt(0);

using (MemoryStream ms = new MemoryStream())
{
    new BinaryFormatter().Serialize(ms, l1);
    bytes2 = ms.ToArray();
}

Debug.Assert(bytes1.Length == bytes2.Length);

Скажем так: Debug.Assert потерпит неудачу.Это потому, что List «сохраняет» некоторый внутренний статус (например, версию).Это очень затрудняет двоичную сериализацию и сравнение.Вам лучше использовать «программируемый» сериализатор (например, proto-buf).Вы говорите ему, какие свойства / поля нужно сериализовать, и он сериализует их.

Так что же может быть альтернативным способом сериализации, который не займет много времени для реализации?

Proto-buf ... или DataContractSerializer (но это довольно медленно).Как вы можете себе представить, в сериализации данных нет серебряной пули.

6 голосов
/ 26 марта 2011

Что вы думаете об этом подходе:

  • перемещаться по графику и foreach объект на графике создать стандартный хэш-код int с использованием этого алгоритма (но исключить элементы ссылочного типа, представляющие узлы на графике).
  • Добавить каждый хеш-код в список целых чисел
  • Преобразование целочисленного списка в байтовый массив
  • Создание хэша в байтовом массиве с использованием MD5, CRC или аналогичного

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

хеширование

Учитывая, что вы предпочли бы скорость, а не точность, и что хэш-код размером int для каждого элемента оставляет достаточно места для предотвращения коллизий, выбор алгоритма хэш-кода кажется правильным. Исключение ссылочных типов, которые участвуют в графике, означает, что мы отбрасываем некоторую информацию; подробнее об этом см. ниже.

Улучшение хэша узла

Идея не учитывать другие узлы, подключенные к узлу, который мы хэшируем, верна, но, может быть, мы можем сделать лучше, чем просто выбросить всю эту информацию? Мы не хотим принимать во внимание хеш-коды других узлов (они также будут хэшироваться сами по себе), но мы отбрасываем информацию, представленную здесь графом dge : хеш-код для узла с внутренние данные X, связанные с N другими узлами, не должны быть одинаковыми для узла с данными X, связанными с M другими узлами.

Если у вас есть дешевый способ использования части данных о границах, используйте их. Например, если график направлен, то вы можете добавить к хеш-коду, вычисленному для каждого узла, число ребер, выходящих из него в другие узлы.

Агрегирование хэш-кодов

Создание списка хеш-кодов было бы средним подходом между суммированием хеш-кодов в один long (очень быстро и сохраняет некоторую дополнительную информацию по суммированию в int) и созданием списка хеш-кодов в зависимости от общего порядка элементов в графе. Если вы ожидаете много элементов на графике, то суммирование может быть более подходящим (сначала я попробую и посмотрим, достаточно ли оно без столкновений); если в графе не так много элементов (скажем, <1000), я сначала попробую использовать метод полного порядка. <em>Не забудьте выделить достаточно памяти для списка (или просто использовать массив) при его создании; Вы уже знаете его окончательную длину, так что это бесплатное увеличение скорости .

Создание хеша фиксированного размера

Если вы суммировали хеш-коды в примитиве, этот шаг вообще не требуется. В противном случае, хэширование списка как byte[] - это то, что я считаю лучшим. Поскольку хеширование байтов займет очень мало времени по сравнению с созданием списка, вы можете использовать хэш-функцию большего размера, чем md5 или crc32, для уменьшения коллизий без практического снижения производительности.

Улучшение окончательного качества хеша

После получения этого "окончательного" хеша я добавляю или добавляю к нему количество элементов в хешированном графе в виде строки в шестнадцатеричном формате фиксированного размера, потому что:

  • Это может помочь уменьшить коллизии (насколько это зависит от характера графиков)
  • Мы уже знаем количество элементов на графике (мы только что хэшировали каждый из них), поэтому это операция O (1)

Определение итогового заказа

Если порядок, в котором обрабатываются элементы на графике, не является строго определенным, то дверь открыта для ложных отрицаний: два графика, которые должны хешировать одно и то же значение, не делают этого, потому что, хотя они логически эквивалентны, реализация из хэш-функции, выбранной для обработки хэшей для каждого элемента в другом порядке. Эта проблема появится, только если вы используете список, так как сложение транзитивно, поэтому «добавить в long подход» неуязвимо для него.

Чтобы бороться с этим, вам нужно обработать узлы на графике в четко определенном порядке. Это может быть порядок, который легко получить из структуры данных узлов (например, как обход предварительного порядка в дереве) и / или другой информации (например, имена классов или типы узлов для каждого узла, идентификаторы узлов, если таковые существуют и т. Д.).

Поскольку предварительная обработка графика для получения общего заказа займет некоторое время, вы можете взвесить это с затратами, вызванными ложным отрицательным результатом, как я упоминал выше. Кроме того, если графики достаточно велики, обсуждение может быть спорным, поскольку подход суммирования хеш-кода узла более соответствует вашим потребностям.

2 голосов
/ 26 сентября 2014

Вот подход, который я использую:

1. Сериализация с использованием ServiceStack's TypeSerializer

Это сериализует объекты в JSV, который я смутно описал бы как «JSON с меньшим количеством кавычек», поэтому он меньше и подразумевается (автором) примерно в 5 раз быстрее, чем сериализация JSON. Основное преимущество перед BinaryFormatter и Protobuff (которое в противном случае было бы моим первым выбором) заключается в том, что вам не нужно аннотировать или описывать все типы, которые вы хотите сериализовать. Я так ленив, и это просто работает с любым poco.

2. Вычислить MD5 хеш

Это «достаточно хороший» подход для меня с точки зрения производительности и характеристик столкновения. Если бы я был слишком силен в этом, я бы, вероятно, пошел с MurmurHash3 , который имеет характеристики столкновения, аналогичные MD5, но на намного быстрее. Он не подходит для криптографических целей, но, похоже, это не является обязательным требованием. Единственная причина, по которой я пошел с MD5, это то, что он запекается в BCL и достаточно быстр для моих целей.

Вот и все, как метод расширения:

using System.Text;
using System.Security.Cryptography;
using ServiceStack.Text;

public static byte[] GenerateHash(this object obj) {
    var s = TypeSerializer.SerializeToString(obj);
    return MD5.Create().ComputeHash(Encoding.UTF8.GetBytes(s));
}

Объекты, которые я использую с этим, являются относительно небольшими (обычно сериализовано не более пары сотен символов), и я никогда не сталкивался с проблемами столкновения. YMMV.

2 голосов
/ 24 марта 2011

Я думаю, что вам нужно создать канонический порядок для объектов, отсортировать объекты в этом порядке, а затем вычислить хэш для объектов в этом отсортированном порядке.

Один из способов сделать этоопределить отношение между объектами, которое всегда равно «<» или «>», если объекты не содержат идентичный контент (в этом случае объекты имеют «==» в соответствии с отношением) [примечание: это не учитываетфакт, что дуги из идентичных объектов содержимого могут позволить вам отличить их как «<» или «>»;если это важно для вас, определите канонический порядок и для дуг]. Теперь перечислим все объекты в графе и отсортируем по этому соотношению.Обрабатывайте объекты в отсортированном порядке и составляйте их хэши.

Я ожидаю, что это будет работать очень быстро, безусловно, намного быстрее, чем любое решение, включающее сериализацию, поскольку оно не генерирует гигантский текст (или даже двоичный текст) строки из значений.

0 голосов
/ 27 марта 2011

Как заметила Ира Бакстер, вы хотите переставить (отсортировать) объекты на графике в определенном каноническом порядке.Затем вы можете перейти к вычислению хэшей и сведению их (как в «map-Reduce») к одному хешу.

В качестве трюка с производительностью иногда полезно попробовать сохранить график таким образомвсе время - иногда проще сохранить коллекцию отсортированной, чем отсортировать все после транзакции обновления.

Здесь вы можете использовать хитрость, чтобы минимизировать использование памяти и процессора.Вам необходимо проанализировать, как часто меняются объекты и график и как часто вы хотите знать, изменился ли график объектов.

Как я уже упоминал в комментарии к вашему вопросу, MD5 и подобные алгоритмы хеширования не используют много памяти - менее килобайта на экземпляр.Вам нужно только сохранить блок (512 байт) данных для хеширования за один раз.

Если вам повезет, ваши объекты и график сильно изменятся (т.е. многие объекты меняют состояние один за другим).другое), но вы хотите знать об этом только время от времени (т.е. только после того, как закончится вся транзакция обновления графа).В этом случае вы просто хотите вычислить хэши только после завершения транзакции.Или, может быть, только по требованию (т.е. когда вы отправляете событие обновления или опрашиваете его на предмет изменений из отдельного потока).В этом случае, чтобы сэкономить память, вы хотите передать объект вычисления хеша MD5 / SHAxxx потоком данных, сохраняя как можно меньше промежуточных значений.Таким образом, использование вашей памяти будет постоянным, независимым (как в O (1)) от размера графика.

Теперь, если вам еще повезет, ваши объекты не сильно изменятся, если вообщено вы хотите знать, изменились ли они сразу, например, вызывая событие для каждого изменения.В этом случае вы хотите изменить, т.е. обернуть или иным образом расширить объекты, чтобы вычислить хеш или просто проверить их на наличие реальных изменений.Нажмите «измененное» событие в каждом установщике свойства объекта.То же самое с изменением графика.Это полностью избавит вас от вычисления хешей (в некоторых случаях - значительный прирост производительности).

Если ваши объекты меняются редко, и вам также нужно проверять их на наличие изменений редко (включая случаи с де / сериализацией, используемой где-топроцесс), тогда первый подход все еще работает лучше.

Обычно контрпродуктивно пытаться вычислять хэши для сложных объектов в графе, который часто меняется, чтобы знать о каждом изменении, происходящем внутри немедленно (воздействовать на каждый изих).В этом случае вы хотите использовать какой-либо подход к сигнализации о событиях (лучше всего для .NET) или обратных вызовов.

...