Efficient comparison of long text strings stored into a Database

Question

I store application events into a database, extracted from a different text files.

Event object is as follow :

public class LogEvent
{
    public DateTime DateTime { get; set; }
    public LogLevel Level { get; set; }
    public string Message { get; set; } //can be lengthy
}

Please note that I do not own this structure and I cannot add any property like a unique Guid to the original generated object (but I can extend the class and create additional database columns from the information I have).

My problem is that I would like to ensure that I do not insert the same event twice despite it can be replicated over different files. The DateTime+Level properties are not sufficient to qualify for equality : different events can occur at the exact same time.

Therefore, whenever I insert an event / a list of events into the database, I need to compare against message properties which is highly inefficient due to the potential string length : it implies that I need to transmit one way or another the Message property of already inserted events, to compare them either locally either against a database index.

I thought about creating an additional property Hashcode which would store String.GetHashCode() of Message property. But, I read here that this is not a good practice since the Hashcode implementation is not stable across program executions (and potential collisions but this risk acceptable)

So, I am stuck with the following problem : how to build comparison value from long strings, which can be deterministic, fast to compute/compare against, and with a an acceptable rate of collision?. Strings can be up to a few thousands characters.

I am aware of Jon Skeet's answer to a similar question here, but it's quite old (almost 10 years) and I was wondering if there is a better method in 2020!

Thanks for your hints!

Answer 1

To expand on my comment: Use the Murmur3 non-cryptographic hash algorithm. You can get it from NuGet here: https://www.nuget.org/packages/murmurhash/

• Do not use the built-in GetHashCode() because, as you surmised, it isn't safe to persist outside of your process.
• You can (but you shouldn't) use cryptographically-secure hash-functions because they're computationally expensive to calculate - and generally slow (not necessarily intentionally slow, but if SHA-256 was trivial to compute then I'd be a billionaire from finding SHA-256 hashes for Bitcoin mining).
  • Whereas hashing-functions like Murmur are designed to be fast and fairly collision-resistant.

So here's what I'd do:

1. Write a function that serializes your LogEntry to a reusable MemoryStream for hashing by MurmurHash (the NuGet package I linked-to does not have the ability to automatically hash any object - and even if it did, you need a rigidly-defined hashing operation - as it is, serializing in-memory is the "best" approach for now). Provided you re-use the MemoryStream this won't be expensive.
2. Store the hash in your database and/or cache it in-memory to reduce IO ops.

In your case:

interface ILogEventHasher
{
    Int32 Compute32BitMurmurHash( LogEvent logEvent );
}

// Register this class as a singleton service in your DI container.
sealed class LogEventHasher : IDisposable
{
    private readonly MemoryStream ms = new MemoryStream();

    public Int32 Compute32BitMurmurHash( LogEvent logEvent )
    {
        if( logEvent is null ) throw new ArgumentNullException( nameof(logEvent) );

        this.ms.Position = 0;
        this.ms.Length   = 0; // This resets the length pointer, it doesn't deallocate memory.

        using( BinaryWriter wtr = new BinaryWriter( this.ms, Encoding.UTF8 ) )
        {
            wtr.Write( logEvent.DateTime );
            wtr.Write( logEvent.Level    );
            wtr.Write( logEvent.Message  );
        }

        this.ms.Position = 0; // This does NOT reset the Length pointer.

        using( Murmur32 mh = MurmurHash.Create32() )
        {
            Byte[] hash = mh.ComputeHash( this.ms );
            return BitConverter.ToInt32( hash ); // `hash` will be 4 bytes long.
        }

        // Reset stream state:
        this.ms.Position = 0;
        this.ms.Length = 0;

        // Shrink the MemoryStream if it's grown too large:
        const Int32 TWO_MEGABYTES = 2 * 1024 * 1024;
        if( this.ms.Capacity > TWO_MEGABYTES  )
        {
            this.ms.Capacity = TWO_MEGABYTES;
        }
    }

    public void Dispose()
    {
        this.ms.Dispose();
    }
}

To filter LogEvent instances in-memory, just use a HashSet<( DateTime utc, Int32 hash )>.

I don't recommend using HashSet<Int32> (storing just the Murmur hash-codes) because using a 32-bit non-cryptographically-secure hash-code doesn't give me enough confidence that a hash-code collision won't happen - but combining that with a DateTime value then gives me sufficient confidence (a DateTime value consumes 64 bits, or 8 bytes - so each memoized LogEvent will require 12 bytes. Given .NET's 2GiB array/object size limit (and assuming a HashSet load-factor of 0.75) means you can store up to 134,217,728 cached hash-codes in-memory. I hope that's enough!

Here's an example:

interface ILogEventFilterService
{
    Boolean AlreadyLoggedEvent( LogEvent e );
}

// Register as a singleton service.
class HashSetLogEventFilter : ILogEventFilterService
{
    // Somewhat amusingly, internally this HashSet will use GetHashCode() - rather than our own hashes, because it's storing a kind of user-level "weak-reference" to a LogEvent in the form of a ValueTuple.

    private readonly HashSet<( DateTime utc, Int32 hash )> hashes = new HashSet<( DateTime utc, Int32 hash )>();

    private readonly ILogEventHasher hasher;

    public HashSetLogEventFilter( ILogEventHasher hasher )
    {
        this.hasher = hasher ?? throw new ArgumentNullException( nameof(hasher) );
    }

    public Boolean AlreadyLoggedEvent( LogEvent e )
    {
        if( e is null ) throw new ArgumentNullException( nameof(e) );

        if( e.DateTime.Kind != DateTimeKind.Utc )
        {
            throw new ArgumentException( message: "DateTime value must be in UTC.", paramName: nameof(e) );
        }

        Int32 murmurHash = this.hasher.HashLogEvent( e );
        
        var t = ( utc: e.DateTime, hash: murmurHash );
        
        return this.hashes.Add( t ) == false;
    }
}

If you want to do it in the database directly, then define a custom user-defined-table-type for a table-valued-parameter for a stored-procedure that runs a MERGE statement of this form:

CREATE TABLE dbo.LogEvents (
    Utc        datetime2(7)   NOT NULL,
    MurmurHash int            NOT NULL,
    LogLevel   int            NOT NULL,
    Message    nvarchar(4000) NOT NULL
);

MERGE INTO dbo.LogEvents AS tgt WITH ( HOLDLOCK ) -- Always MERGE with HOLDLOCK!!!!!
USING @tvp AS src ON src.DateTime = tgt.DateTime AND src.MurmurHash = tgt.MurmurHash
WHEN NOT MATCHED BY TARGET THEN
    INSERT(     Utc,     MurmurHash,     LogLevel,     Message )
    VALUES( src.Utc, src.MurmurHash, src.LogLevel, src.Message )
;

Answer 2

Step 1. Compare them by length. It'll cut off the most of them. Step 2. Compare the strings with the same length by the 1st character ... etc.