DEV Community: Joshua Thijssen

BitMaelum - e2e encrypted mail

Joshua Thijssen — Fri, 22 Jan 2021 13:31:37 +0000

Hi all,

We want to introduce BitMaelum (https://github.com/bitmaelum): a privacy and security focused mail system written from the ground up. Its goal is to combat many of the pain-points found in the current email landscape: spam, privacy, mail/account ownership, etc.

Some of the features:

Complete end-to-end encryption of mail, including meta-data.
Combatting spam through a proof-of-work type system.
Ownership of your bitmaelum address.
Users, not the list owners, manage mailing lists subscriptions.
Mobile friendly.
Automation is made possible through events and webhooks.

We have developed a system that we think is ready for our first developer release: our "hello world" release. The system consists of a mail-server, a mail-client, and some supporting tools. The quick start will guide you into creating an account to test the system. We like to invite developers and everyone interested to try out the system, leave feedback, or even help us implement new features and bugfixes.

For more information, please take a look at our website: https://bitmaelum.com, our GitHub account https://github.com/bitmaelum/bitmaelum-suite, or send us an email via info@bitmaelum.com or through bitmaelum: bitmaelum!

A quest to save money on Amazon

Joshua Thijssen — Tue, 28 Jan 2020 08:20:54 +0000

One day I've received an email from Amazon Web Services with the subject "AWS Free Tier limit alert". This scared me: even though we use Amazon outside the free tier limit, I had no idea why and what reached the free tier limit.
It turns out we have used 850K SQS requests at the moment while the free tier limit was 1 million. It automatically sends an e-mail at 85% of your usage limit.

Now things got really scary: we did use SQS, but we use it in no such a way that it should generate 850 thousand requests. And even though I have multiple budget alarms in place and nothing out of the ordinary was going on, I did worry about this. Are there services behaving badly and trashing things, resulting in a maxed-out credit card by the end of the month?

So I start diving into the infrastructure, trying to figure out what was going on. Not seeing anything out of the ordinary, I figured the issue might be something wrong with the code that was running. After a half-hour or so, I've identified a piece of code that was running sub-optimal, resulting in multiple SQS requests which shouldn't. I've optimized some of the SQS query parameters on Amazon and refactored parts of the code resulting in fewer calls.

I've received the email from Amazon on the 11th of the month, thus assuming that we would reach 850K times 3 is about 2.5 million SQS requests. I figured that with our new optimization we would have saved around 1 million requests per month, resulting in 1.5 million requests per month. Not good, but at least we shaved off almost half the requests.

At this point, I was feeling good. Really good. Not only was the code a bit faster and less complex, but we managed to not pay Amazon more money than we need to. And all it took was around 4 hours of work. Four hours! In this moment of victory, I wanted to know how much money we saved this, realizing we are saving this a huge amount of money EACH month.

From the pricing page of amazon:

The first 1 million monthly requests are free. After that, the pricing is as follows for all regions:
Pricing per 1 million Requests after Free tier (Monthly): $0.40 ($0.0000004 per request)

It took a while for it to land, but I was realizing that I've spent four whole developing hours to save around 40 CENTS per month and it would take me a bit over 83 YEARS to get my money back.

And this by itself is already bad enough, maybe the biggest problem was that I was wrong about my "savings" too:

The reason why we have reached this many SQS requests wasn't the code itself. It was the fact that we connected SQS to Lambda, so it would trigger once we received messages in the queue. But this isn't a push-action within Amazon, in fact, lambdas are continuously pulling the queue, resulting in requests being made. And it's not just one single lambda that pulls, there are multiple at the same time.

In the end we did manage to save some requests, but this was nothing compared to the number of pull requests from lambda itself. Not only did I spent 4 hours to save 20 cents, but I didn't even save those 20 cents in the end.

It did teach me a good lesson though.. a lesson I thought I knew, but apparently needed a good wakeup call:

Figure out how much you are actually saving in money or time before spending any time/money on your optimization. These four hours spent would be a good deal if it would save up like 100$ each month. We would get our money back quickly and save even more in the end.
When you want to optimize something, make damn sure you are optimizing the correct thing. Code can be deceiving.
I will never forget SQS pricing for the rest of my life.

Parsing complex search queries in PHP

Joshua Thijssen — Wed, 22 Jan 2020 08:46:42 +0000

An important factor in a system like Seams-CMS, is the fact we need to be able to let users search for data. Such search queries could be as simple as:

query all entries that start with "foo".

But they could also become very complex:

query all entries that start with "foo" and are tagged with either "news" or "featured" or have at least 10 comments but no more than 25, and is published at most 1 year ago.

Creating a system that can deal with such complex questions sounds like a daunting task, but is, in fact, a relatively simple problem: we treat our search queries as a custom programming language.

Lexing and parsing

Creating a custom programming language just for search queries sounds like overkill but it's not. Most querying systems, like SQL or ElasticSearch Query language or any system, deal with this the same way. The magic solution is called lexing and parsing.

To make things work, we need to do these four steps:

Step 1: Identify tokens from our search query (lexing)
Step 2: Analyze the tokens and make sure they adhere to our ruleset (parsing)
Step 3: Create an Abstract Syntax Tree (AST) from these tokens.
Step 4: Use the AST for building your search.

This, in fact, is exactly what pretty much every programming language does too: from your source code, it tries to decipher different tokens (keywords, strings, variables, etc) and makes sure these tokens follows the rules of the programming language. Next, it will convert these tokens into an Abstract Syntax Tree, which is a representation of your program that can be easily processed or executed.

Since our search queries are handled by an API written in PHP, we need to find a way to lex and parse in PHP. Fortunately, there is already a common library available for this: the Doctrine Lexer. It is mostly used for parsing and generating the DQL language (doctrine query language) but can be easily used for lexing and parsing your custom language. Sweet!

Backus normal form

Before we can start with these steps, we must create a blueprint for our query language. This is completely up to you and pretty much the sky is the limit. Do however make sure your rules are easy to follow otherwise you not only confuse yourself and must create a complex parser, but it will also confuse your users.

One way of creating such a blueprint is with the help of the Backus Normal Form (BNF). This is a standardized way of writing your rules. Some lexer/parser systems can generate parsers directly from this, but in our case, we need to create a parser manually. Again a reason to make the language as simple as possible.

(note that the following is not completely in BNF notation, but readable enough)

 query := simple_query_expression |
          query AND simple_query_expression |
          query OR simple_query_expression

 simpleQueryExpression := identifier operator operand | '(' identifier operator operand ')'

 identifier := [a-zA-Z0-9_.]+

 operator := eq|ne|gt|le|lt|in|ni|contains

 operand := scalar | array

 array := '[' array_value ']'
 array_value := scalar | scalar ',' array_value

 scalar := qstring | string | int | date
 qstring := '"' [^"]+ '"'
 string := [^\s]+
 int := [0-9]+
 date := ISO8601 datetime

Our language consists of a query which can be either a simple_query_expression OR a query followed by the keyword AND followed by another simple_query_expression, OR a query followed by the keyword OR followed by another simple_query_expression. This allows us to create complex AND/OR queries.

A simple_query_expression is nothing more than an identifier followed by an operator followed by an operand, OR the same thing but withing parenthesis. This means that ("foo" eq "bar") and "foo" eq "bar" are the same thing.

An identifier is nothing more than a word that matches the [a-zA-Z0-9_]+ regex. Some languages prefer to have identifiers starting with a letter first for instance, but in our case, it doesn't matter.

Operators are words: eq, ne, gte, gt etc.. We could have opted for operators like == !=, > etc but since we are sending these search queries mostly through URLs, it would be easier to read them as things like == would be URL-escaped.

Scalars, strings, qstrings, int, and dates are also relatively simple tokens.

Arrays are anything between brackets: [ "foo", 4 ], [ "foo", "bar", "baz" ] etc.

Lexing

Now that we have created our language, it's time to start with the lexer.

<?php

namespace SeamsCMS\Query\Filter;

use Doctrine\Common\Lexer\AbstractLexer;

class Lexer extends AbstractLexer
{
    // All tokens that are not valid identifiers must be < 100
    public const T_NONE              = 1;
    public const T_NUMBER            = 2;
    public const T_STRING            = 3;
    public const T_OPEN_PARENTHESIS  = 4;
    public const T_CLOSE_PARENTHESIS = 5;
    public const T_OPEN_BLOCK        = 6;
    public const T_CLOSE_BLOCK       = 7;
    public const T_COMMA             = 8;
    public const T_DATE              = 9;

    // All keyword tokens should be >= 200
    public const T_AND      = 200;
    public const T_OR       = 201;
    public const T_EQ       = 202;
    public const T_NE       = 203;
    public const T_LT       = 204;
    public const T_LTE      = 205;
    public const T_GT       = 206;
    public const T_GTE      = 207;
    public const T_IN       = 208;
    public const T_NI       = 209;
    public const T_CONTAINS = 210;

    /**
     * {@inheritdoc}
     */
    protected function getCatchablePatterns()
    {
        return [
            '[a-z0-9_.]*',    // Identifiers
            '(?:[0-9]+)?',    // numbers
            '(?:"[^"]+")',    // Double quoted strings
        ];
    }

    /**
     * {@inheritdoc}
     */
    protected function getType(&$value)
    {
        $type = self::T_NONE;

        switch (true) {
            // Recognize numeric values
            case (is_numeric($value)):
                return self::T_NUMBER;

            // Recognize quoted strings
            case ($value[0] === "\""):
                $value = str_replace("\"\"", "\"", substr($value, 1, strlen($value) - 2));

                if (is_numeric($value)) {
                    // Quoted numbers are still numbers 
                    return self::T_NUMBER;
                }

                // See if we are a quoted date
                try {
                    $ret = new \DateTime($value, new \DateTimeZone("UTC"));
                    if ($ret instanceof \DateTime) {
                        return self::T_DATE;
                    }
                } catch (\Exception $e) {
                    // It's ok when it's not a date.
                }

                return self::T_STRING;

            // Recognize identifiers, aliased or qualified names
            case (ctype_alpha($value[0])):
                $name = 'SeamsCMS\\Query\\Filter\\Lexer::T_' . strtoupper($value);

                if (defined($name)) {
                    $type = constant($name);

                    if ($type > 100) {
                        return $type;
                    }
                }

                return self::T_STRING;

            // Recognize symbols
            case ($value === '('):
                return self::T_OPEN_PARENTHESIS;

            case ($value === ')'):
                return self::T_CLOSE_PARENTHESIS;

            case ($value === '['):
                return self::T_OPEN_BLOCK;

            case ($value === ']'):
                return self::T_CLOSE_BLOCK;

            case ($value === ','):
                return self::T_COMMA;

            // Default
            default:
                // Do nothing
        }

        return $type;
    }
}

We define symbols (constants) for each token we want to identify. This means that whenever we detect a , in our language, the lexer will return a T_COMMA (unless the comma was inside a quoted string, in which case it would return a T_STRING.

There is a little bit of magic going on detecting the operators: when we discover the string "eq", the lexer checks if there is a constant called T_EQ, and if so, it will use that token, otherwise the string is just a string. This is here so we don't have to define each operator separately.

Another tricky thing is that we check quoted strings for dates. If the string can be parsed as a DateTime, we consider the string as a T_DATE, otherwise, it's just a T_STRING.

Parsing the tokens

Now that we can lex our language into tokens, it's time to make sense of these tokens. According to our BNF, a simple_query_expression must start with a T_IDENTIFIER followed by a T_OPERATOR. The parser is where this syntax checks will occur and where it will return errors identifying the error (for instance: it can return "operator expected" when a T_IDENTIFIER is followed by a T_DATE instead of a T_OPERATOR.

Here is a snippet of our parser:

    /**
     *  simpleQueryFactor:= identifier operator operand | '(' QueryExpression ')'
     *
     * @return Node
     * @throws ParseException
     */
    public function simpleQueryFactor(): Node
    {
        $lookaheadType = $this->lexer->lookahead['type'];
        if ($lookaheadType === Lexer::T_OPEN_PARENTHESIS) {
            $this->lexer->moveNext();

            $expr = $this->QueryExpression();
            $this->mustMatch(Lexer::T_CLOSE_PARENTHESIS);
            return $expr;
        }

        $identifier = $this->identifierExpression();
        $operator = $this->operatorExpression();

        switch ($operator->getOperator()) {
            case 'in':
            case 'ni':
                // In and NI must be arrays
                $this->mustMatch(Lexer::T_OPEN_BLOCK);
                $operand = $this->arrayExpression();
                $this->mustMatch(Lexer::T_CLOSE_BLOCK);
                break;
            case 'gt':
            case 'gte':
            case 'lt':
            case 'lte':
                // These can only be numbers or dates, not strings
                $operand = $this->numberOrDateExpression();
                break;
            case 'contains':
            case 'eq':
            case 'ne':
            default:
                $operand = $this->operandExpression();
                break;
        }

        return new SimpleQueryNode($identifier, $operator, $operand);
    }

    /**
     * identifier := [A-Z0-9_.]+
     *
     * @return IdentifierNode
     * @throws ParseException
     */
    public function identifierExpression(): IdentifierNode
    {
        $this->mustMatch(Lexer::T_STRING, 'identifier');
        $identifier = $this->lexer->token['value'];

        return new IdentifierNode($identifier);
    }

(note that the BNF is a bit different that we discussed).
Inside the simpleQueryFactor function we check the syntax for a simple_query_expression and generate an AST node. We check for parenthesis and if found, we parse the expression in between. The "mustMatch" function checks if the next token is actually a T_OPEN_PARENTHESIS or T_CLOSE_PARENTHESIS so it will throw a syntax error when we forget a closing ), or have an uneven number of open and close parenthesis.

The syntax rules for a query depends a bit depending on each operator: the in and ni operator MUST have an array as an operand, while gt, gte etc must have either a number or a date.

If everything follows our rules, we return a SimpleQueryNode which is an AST node with an identifier, an operator and operand.

the identifierExpression is a bit simpler: it will check if the value matches a string (we don't have separate tokens for identifiers), and returns an identifier AST node.

AST nodes

The AST nodes itself are simple data objects without any logic inside. They are present to represent the abstract syntax tree:

class IdentifierNode extends Node
{
    /** @var string */
    protected $value;

    /**
     * IdentifierNode constructor.
     * @param string $value
     */
    public function __construct(string $value)
    {
        $this->value = $value;
    }

    /**
     * @return string
     */
    public function getValue(): string
    {
        return $this->value;
    }
}

<?php
class SimpleQueryNode extends Node
{
    /** @var IdentifierNode */
    protected $identifier;

    /** @var OperatorNode */
    protected $operator;

    /** @var Node */
    protected $operand;

    /**
     * SimpleQuery constructor.
     *
     * @param IdentifierNode $identifier
     * @param OperatorNode $operator
     * @param Node $operand
     */
    public function __construct(IdentifierNode $identifier, OperatorNode $operator, Node $operand)
    {
        $this->identifier = $identifier;
        $this->operator = $operator;
        $this->operand = $operand;
    }

    /**
     * @return IdentifierNode
     */
    public function getIdentifier(): IdentifierNode
    {
        return $this->identifier;
    }

    /**
     * @return OperatorNode
     */
    public function getOperator(): OperatorNode
    {
        return $this->operator;
    }

    /**
     * @return Node
     */
    public function getOperand(): Node
    {
        return $this->operand;
    }
}

Walking the abstract syntax tree

So the parsing process does two steps at once: checking the syntax of our language and generating an abstract syntax tree.

A query like this

content.full_name.value ne "John Doe" and (meta.sizelte 12000 or meta.blaat eq "foobar")

would give us the following AST:

<?php return 'AST\\QueryExpressionNode(
    "terms": array(
        "0" => AST\\SimpleQueryNode(
            "identifier": AST\\IdentifierNode(
                "value": \'content.full_name.value\',
            ),
            "operator": AST\\OperatorNode(
                "operator": \'ne\',
            ),
            "operand": AST\\LiteralNode(
                "value": \'John Doe\',
            ),
        ),
        "1" => AST\\QueryTermNode(
            "factors": array(
                "0" => AST\\SimpleQueryNode(
                    "identifier": AST\\IdentifierNode(
                        "value": \'meta.size\',
                    ),
                    "operator": AST\\OperatorNode(
                        "operator": \'lte\',
                    ),
                    "operand": AST\\LiteralNode(
                        "value": 12000,
                    ),
                ),
                "1" => AST\\SimpleQueryNode(
                    "identifier": AST\\IdentifierNode(
                        "value": \'meta.blaat\',
                    ),
                    "operator": AST\\OperatorNode(
                        "operator": \'eq\',
                    ),
                    "operand": AST\\LiteralNode(
                        "value": \'foobar\',
                    ),
                ),
            ),
        ),
    ),
)';

This is now a system that can be easily traversed over. We know that a QueryExpressionNode consists of one or multiple terms that have to be 'AND'ed with each other. A simpleQueryNode consists of an identifier, operator, and operand, which could be a literal or array, etc.

At this point, we don't care about syntax and rules because that all has been taken care of by the lexer and parser.

In our case, we use this AST to generate filters for our MongoDB data cluster, but we could just as easily use the same AST to output an ElasticSearch query or even an SQL query to fetch data from another data source. The possibilities are endless!

Conclusion

Dealing with complex queries doesn't have to be that hard. It's easy to fall into the trap of creating your own parser, but more often than not you end up with all kind of edge-cases that you may or may not handle, have issues when dealing with the complexities of subqueries, or and/or queries that may or may not be in parenthesis, etc.

Instead of writing your own parser system, use a proven and well-documented system like lexing and parsing: it's for a good reason that it's used in every (query) language out there and although it may look scary at first, you'll get the hang of it quickly.

More information about Seams-CMS, or other articles about development, PHP and CMSes in general can be found at https://blog.seams-cms.com