We received a big set of files to analyze; different formats, different content. The assignment was pretty simple: search for an email address and get all corresponding records matching the address.

We tried to import data in MariaDB and Elasticsearch, but both solutions were slow. MariaDB had better/flexible search performance in the short term, but it does not scale very well. Elastic scales well, but requires more code to keep data under control and more hardware. In addition, the search engine was just a PoC, so we didn’t want go big in hardware.

Challenges

• File size: We received a lot of files with very different file sizes, ranging from 50Mb up to 89Gb. ⇒ To keep the access-time linear, we split each file into 10K lines chunks.
• File ending: Sometime, there was no clean line ending. ⇒ We fixed with sed.
• Json files: Some exports are just a single big line; some exports are multiple lines per record. ⇒ In both cases, we transformed the json file in a json file having 1 record per line, using the tool jq
• Email extraction: Extracting email addresses sounds easy but is not a trivial task: the official regular expression to validate email addresses is pretty complex and time consuming. ⇒ We made some tests to find out a balanced regexp to save time and still catch the large majority of the mails. For a discussion on the email address regular expression, check How to Find or Validate an Email Address

Solution

We recycled an old Shuttle/I5/8GB, changed the HD with a new SSD (Samsung 850Pro, 1TB) and installed Debian.

After the hardware preparation and some tests, we decided to go for a filesystem index:

• a set of files named by the first 3 chars of the email address
• containing the reference to the source file/line where the email address was found

We prepared some Python and shell scripts to deal with the data.

We pre-parsed the files with specialized tools or some sed scripts, until we get a reasonable files base, as described in the preceding chapter. Then we applied the following pattern:

1. scan the file (f)
2. grep for email (e)
3. append "e, hash(f)" >> left(e,3)__.idx

In two days, all files were scanned and indexed. After that, it was possible to make a search for records containing a specific email address in a few seconds.

Attention was placed in the choice of the hashing algorithm; it was possible to save some Gb of redundant information. It was also important to balance the regular expression searching for mails: not too easy nor too complex.

Measures

Dataset to Analyze

Results

The chart shows on the x-axis the number of chunks and on the y-axis the number of files chunked by c. It shows how the original files have been chunked to flatten the access time.

Timing

Search Time

The following chart shows on the x-axis the indices in 50K cardinality groups (cg), on the left y-axis the number of email addresses in the cg, and on the right y-axis the worst access time [seconds] for the gc.

Circa 90% of the email addresses can be found within the 10s range, but the remaining 10% has an high access time. Based on statistics, a second indexing round has reindexed the top 10 indices by 4 chars; as result, the access time has been flattened to max 10s.

Top Indices

Indexing by the leftmost 3 chars, creates indices with different sizes, depending on how many email addresses starts with the 3 chars. The top 3 indices have millions of email addresses:

We note that the majority of email addresses extracted starts with mar, at the second place www, which means that there are many “service” email addresses.

The following chart shows a treemap of the indices sizes.

Conclusion

Using dedicated tools, we were able to decrease the query time by many order of magnitude. Depending on the goals, instead of use hardware or big and complex tools, it is better to create ad-hoc solution and use the power of the OS tools.

About the Author

Rocco Gagliardi has been working in IT since the 1980s and specialized in IT security in the 1990s. His main focus lies in security frameworks, network routing, firewalling and log management.

Links

• https://stedolan.github.io/jq/
• https://www.regular-expressions.info/email.html