Postgresql/Python compressing text column with a lot of redundant rows
<p>Note:</p>

<ul>
<li>We're using Amazon RDS, so we're very limited on the number of PostgreSQL extensions we can use.</li>
<li>I've said PostgreSQL on RDS , because 1) we must use AWS, 2) we want the safest solution on data integrity with lowest time spent on maintenance. (so if an other service is better suited with these requirements, we're open to suggestion)</li>
<li>we have several terabyte of said data, so space efficiency is important (but we can easily shard based on the source)</li>
</ul>

<p>We would like to store "logs" in a table with the following minimal set of fields (more maybe added for optimization purpose):</p>

<ul>
<li>source</li>
<li>time</li>
<li>level</li>
<li>message</li>
</ul>

<p>The message column has the following specificity
   * 99% of the time very short (&lt; 64 chars, but for the exceptions they can be quite long > 1024 chars)
 * some of the well identified message can take up to 10% of the number of messages
 * a lot of "nearly" duplicated messages (i.e like <code>this system hs been up and running for X seconds</code>)<br>
 * a long tail of "unique" messages
 * taking the messages of a typical day and running them through gzip easily divided the size by 15</p>

<p>Right now i'm thinking of two possible solution</p>

<h2>Compression algorithm accepting dictionary of user defined "tokens"</h2>

<p>The idea we have would be to have some kind of compression algorithm that can use a user provided "dictionnary" based on our identified list of "repeated text" and storing the result. as our "app" is the only one to write and read, we would be able to decompress "on the fly" </p>

<ul>
<li><strong>Pro</strong>: will permit certainly to have a pretty good compression ratio</li>
<li><strong>cons</strong>: I don't know where to search (LZ77 ? but i don't see how)</li>
</ul>

<h2>Dictionnary table for "exactly" matching predefined messages</h2>

<ul>
<li>LOGS_TABLE</li>
<li>source</li>
<li>time</li>
<li>level</li>
<li>dictionnary_id</li>
<li>message (nullable)</li>
</ul>

<p>_</p>

<ul>
<li>DICTIONNARY_TABLE</li>
<li>dictionnary_id</li>
<li>message</li>
</ul>

<p>_</p>

<ul>
<li><strong>Pro</strong>: I perfectly see how to implement it, and it's easy to "update"</li>
<li><strong>cons</strong>: Does not cover the "near" match </li>
</ul>

<p>Is there an already "state of the art" solution for this kind of problem ?</p>

<p>I finally went with the dictionnary table idea</p>

<p>for the dictionnary_id I actually used a <code>murmurhash 64 bits</code> (and named the id <code>hash_message</code> so that I can precompute it on the python side first, and as it is a non-crytographic, it's pretty to call, for python there's a pure C implementation of it <code>mmh3</code> module).</p>

<p>I preloaded the dictionnary table with the 500k most common (and duplicated) logs out of the 507 millions messages I got from a "typical day" of logs.
Then I loaded the data doing the following <code>INSERT</code> request:</p>

<pre><code>        INSERT INTO my_logs (
            service_id,
            creation_date,
            level,
            hash_message,
            message
        )
        SELECT
            %(hash_robot)s,
            %(creation_date)s,
            %(hash_message)s,
            NULLIF (
                %(message)s,
                min(message)
            )
        FROM dictionnary
        WHERE hash_message = %(hash_message)s;
</code></pre>

<p>by doing so, the insert automatically if the <code>message</code> is already existing, and only insert the actual text in my log table if it's not present in the dictionnary.</p>

<p>With I got an average of only 3 bytes used by the <code>message</code> column of my log table !! which mean that most of the time the message table is null, and though adding more logs in my dictionnary would not be worth it (and that switching from a <code>bigint</code> for my service_id to a <code>int</code> would actually be a better idea)</p>

python algorithm postgresql compression