Low-complexity leader election with AWS

An introduction to the Leader Election problem

The Leader Election is a classic distributed systems problem in which one node within a cluster has to be solely in charge of executing certain tasks. For instance, it could be the one having certain services enabled, starting backups or have more complex things to do.

The core of the problem is finding a way for machines to agree on who the leader will be, and react to changes in the cluster topology, such as machine disappearing or auto-scaling actions.

It this article we will see how to perform an extremely simplistic leader election that fits our specific use case, using some of the EC2 facilities offered by AWS.

We wanted to do this avoiding unnecessary complexity and third-party solutions, such as Zookeeper or Consul which are able to perform a leader election in a much more robust and comprehensive way.

Specifications

Our use case has the following specifications:

  • Leader election should be easy and shouldn't require any new infrastructure or services
  • It's OK if during small windows of time the leader is unknown
  • It should work with any number of machines
  • It should require very few AWS permissions
  • It should require little to no communication between the cluster nodes

The solution

We decided to hack a leader election algorithm on top of the EC2 metadata system. Here's the breakdown of the algorithm:

  • It fetches the list of EC2 instances in a autoscaling group
  • It sorts the instances alphabeticlaly
  • It picks the first instance as the leader.
  • All the machines execute this algorithm periodically, thus having the same opinion about who the leader should be.

Since the algorithm uses EC2 for the cluster's nodes discovery, our instances only need the ec2:DescribeTags permission.

Limitations

It is important to recognize the limitations of this very simplistic approach. Particularly, it's worth noticing that this is a low frequency system. If the leader goes down, the other nodes will have outdated information during a certain time window. This means that a particular task might not be performed by the leader.

The algorithm

Let's get to what we all want to see: the algorithm. We chose to implement the algorithm using Python with the boto3 AWS library:

#!/usr/bin/env python
import sys  
import urllib2  
from os import EX_CONFIG, EX_OK

import boto3


class EC2Helper():  
    def __init__(self):
        self.region = self.get_region()
        self.instance_id = self.get_instance_id()
        self.ec2 = boto3.client('ec2', region_name=self.region)
        tags = [
            tag for tag in self.get_tags()
            if tag['ResourceId'] == self.instance_id
        ]
        tags = {t['Key']: t['Value'] for t in tags}
        self.asg = tags.get('aws:autoscaling:groupName')

    def ec2_metadata(self, metadata_resource):
        """
        Method to get a given metadata the instance's metadata
        """
        # 169.254.169.254 is the AWS metadata endpoint
        response = urllib2.urlopen('http://169.254.169.254/latest/meta-data/' +
                                   metadata_resource)
        return response.read()

    def get_tags(self):
        return self.ec2.describe_tags()['Tags']

    def get_availability_zone(self):
        return self.ec2_metadata("placement/availability-zone")

    def get_region(self):
        return self.get_availability_zone()[:-1]

    def get_instance_id(self):
        return self.ec2_metadata("instance-id")

    def get_instances_in_autoscaling_group(self):
        asg_key = 'aws:autoscaling:groupName'
        instances = [
            tag['ResourceId'] for tag in self.get_tags()
            if tag['Key'] == asg_key and tag['Value'] == self.asg
        ]
        return instances

    def elect_leader(self, instances):
        instances.sort()
        return instances[0]


if __name__ == '__main__':  
    ec2h = EC2Helper()
    instances = ec2h.get_instances_in_autoscaling_group()
    leader = ec2h.elect_leader(instances)

    exit_code = EX_OK if leader == ec2h.instance_id else EX_CONFIG
    sys.exit(exit_code)

Usage

The script will return an exit value of 0 when the instance is the leader and a value different than 0 when the instance is not the leader (in accordance with the UNIX exit status convention).

You can therefore test your configuration just by running the script in your cluster nodes:

$ is_leader.py && echo 'I am the leader!' || echo 'I am not the leader'

Conclusions

This is a very simplistic approach which might or might not fit your specific needs. In case it does, it's certainly a good way to avoid spinning up complex infrastructure pieces just to perform a simple coordination task.

Let us know what you think in the comments!