Cron Job, Elastic Beanstalk, Rails Rake

I ran into some issues lately where the the cron job is not running in my Rails deployed on Amazon Elastic Beanstalk. After much debugging, I found that it was because the environment variables are not loaded when the rake tasks were run.

This caused errors like bundler not installed or XX gems not found to appear all over my logs to frustrate the hell out of my weekends.

Took a deep dive and I found the solution. Or should I say the reason, because it remains unsolved and I had to take inspiration from an ancient war tactic to side step this issue. Before we get to the pseudo-solution, let’s find out the reason. And the main reason is…

Long story short: Rake tasks on cron job with Rails on Elastic Beanstalk will not work with Amazon Linux 2.

This is something I wished someone would have told me before I decided to upgrade my stack to the new version.

According to this pretty recent issue on Github, the Beanstalk team in AWS is aware that environment variables are not retrievable on the AL2 platforms like how it was on the old AL1.

The issue mentioned the fact that environment variables in the Beanstalk environment settings did not load, but according to my experiences, the environment variables on the system’s level are not loaded either.

I’m talking about $GEM_PATH, $BUNDLE_PATH etc. These are needed for ruby and rails, in particular, and the bundler to know where the gems are to run its operations and avoid the cursed bundle: command not found or gem not found errors.

I’m not the best candidate to debug a solution to fix it on AL2 platforms. Furthermore, by the time I can miraculously figure how to load the variables, Amazon would probably have already solved it.

So it’s much wiser to switch back to AL1. Henceforth, I will cover the method to run rails rake tasks via cron jobs in elastic beanstalk.

And yes this solution is indeed the last war tactic from Sun Tzu Art Of War.

These are the files you need.

# .ebextensions/01_cron.config
    command: "rm /etc/cron.d/cron_jobs || exit 0"
    command: "cat .ebextensions/cron_tasks.txt > /etc/cron.d/cron_jobs && chmod 644 /etc/cron.d/cron_jobs"
    leader_only: true
# .ebextensions/cron_tasks.txt
* * * * * root bash -l -c "su -m webapp; cd /var/app/current && rake test"

# Take NOTE it ends with a new line!!

The commands of the 01_cron.config file will be run during deployment.

The first command, 01_remove_ctron_jobs, will remove all cron jobs. Should it fail, it will return a success status code to prevent the deployment procedure from stopping. You can also use ignoreErrors flag to achieve the same thing.

Why do we need to remove the cron jobs each time we deploy? Great question. We will get to that in a bit.

The second command 02_add_cron_jobs will copy the cron job definitions located inside the cron_tasks.txt file into another file. This other file will be located in /etc/cron.d directory, where the cron daemon will pick up files from and run the cron jobs as instructed.

The cron job basically runs the rake task as the webapp user, which has the knowledge of the necessary environment variables to execute rails command related to your application.

Now comes a very important point!

Make sure the last line of cron job end with a new line.

The definition of a cron job will be deemed invalid if it does not end with a line break. Hence, a common error occurs where the last cron job did not run due to this reason. I had this error for breakfast last Sunday.

Lastly, the leader_only flag will be set to ensure your cron job will only run on a single leader instance in your Elastic Beanstalk environment. If you intend to run the cron job on all instances, simply remove it and the option will revert to false as its default.

So back to the cliffhanger. Why do we have to remove the all the cron jobs during deployment?

This is because the leader of the cluster in the elastic beanstalk environment may not stay the same during each deployment. Maybe it was lost, physically, in an annual California wildfire event, or maybe it was scaled down and the leader was lost as a result

Doing this will ensure that at all times, there will only be 1 instance that will be executing your cron job, if so desired.


I just lied.

According to this forum thread, the leader of a cluster is determined during the elastic beanstalk environment creation. And it will remain the same throughout all subsequent deployments.

If the leader was lost during a timed scale down event, the leader is lost forever and the cluster in Elastic Beanstalk will remain leaderless until the end of time.

Which means the removal of cron jobs during each deployment is like taking off your pants to fart. It’s trivial.

Well, I’m just placing it there in case a leader reelection feature gets implemented.

The best way to solve this leaderless problem is to use a separate dedicated worker environment and period tasks. It is the official and cleaner way to do cron jobs anyway. Having your main server clusters running cron jobs eat at their computation prowess and that is something you would should architect your system to avoid.

The downside of it is that you will need to consider the cost of having another server to handle this.

Natural Sorting With Datatables

The most significant difference between natural sorting and your typical sorting is the order of a string when there are digits involved. For instance, the string “something2” will be placed before the string “something10” under normal sorting, but 10 is more than 2 for that matter.

This default sorting algorithm causes sorting problems with Datatables and we will see 2 ways to solve it, using a natural sort plugin and the data-sort or data-order attribute.

Natural Sort Plugin In Datatables

The documentation for this plugin lives here. This is how it is implemented in my Rails projects that are running on Turbolinks.

First, install the datatables plugin package via the command below:

yarn add

In the javascript file, the snippet looks like that.

// app/packs/any.js

document.addEventListener("turbolinks:load", () => {
  if (dataTables.length === 0 && $('.data-table').length !== 0) {
    $('.data-table').each((_, element) => {
        pageLength: 50,
        columnDefs: [
          { type: 'natural-nohtml', targets: '_all' }

document.addEventListener("turbolinks:before-cache", () => {
  while (dataTables.length !== 0) {

There is quite a bit of complexity in implementing this. The explanation can be found in this article and is largely due to the need to adapt to a turbolinks driven environment.

The key implementation takes place in line 9 and 10. The natural-nohtml type is specified to strip any html during sorting, while the _all value for the target key means to apply natural sort as the default sorting for all columns. More information and configuration options can be found in its documentation.

data-sort Or data-order Attribute

We can use the data-sort or data-order attribute of the table cell to indicate to Datatables to use these value to do the sorting instead of the values in the cell.

<td data-order="02">2</td>
<td data-order="10">10</td>

This will place the string in the correct numerical order. However, you would have to do the heavy lifting of padding the digits with the appropriate number of 0s.

It is a more useful feature if you want to sort values with a vastly different display value that its actual value that can mess up the sorting order, like date.

<td data-order="1332979200">Thu 29th Mar 12</td>
<td data-order="1354406400">Sun 2nd Dec 12</td>

Under normal sorting, the second <td> element will be placed above the first because ‘S’ comes before ‘T’. However, when we dictate the sort order to be using their epoch timestamp, the story will be different.

11 Gradual Methods On How To Scale A Database

I used to work in a web shop / app agency and now as a full stack app and web developer. My work’s focus has always been about churning out application fast and furious. There is not much investment, budget and love to shower upon optimization, security and, in particular, scaling concerns.

With some free time on my hand, I decided to look at the topic that has been bothering me since my first ever Ruby On Rails application: database scaling.

The methods to scale a database can be split into 3 categories.

  • Application and code
  • Database design and schema
  • Database infrastructure

11. Obliterate N + 1 Queries

This is a common problem that can overwork the database with unnecessary number of queries. It generally lacked the use of JOINs in the queries to prefetch data that will be used eventually in the same request.

Common problem, common solution. Use JOINs to eager load the data beforehand to spare your server multiple trips to the database.

As an application level optimization on the code base, it should be a basic practice for backend developers.

I myself, however, do not practise this all the time. As a word of justice to explain myself and probably a fair number of my fellow confrère, we don’t optimize right away because we have clients who don’t really know what they want and the project requirements were not that all that clear to start with. It just does not make financial sense to spend resources optimizing the project.

From a developer’s point of view and experience building up applications from scratch, the priority is functionality, low budget and speed. Optimization is a bonus we do not paid

10. Optimize Data Type

Data type optimization is an optimization done on the database schema.

Optimize the space needed for a column. An email should not need the full VARCHAR(255) of a typical string data type for example.

Optimizing the space that each column in each table takes will reduce the time taken for the database to get the required data as it will “traverse less bytes”.

9. Normalization

Normalization is an optimization done on the database design and schema.

Split out common but less accessed data into separate tables so that there is less computation required when reading the key tables. This is a form of enumeration at the database level. It keeps reading data efficient and thus reduces the load on the database.

However, be careful not to over normalized your tables or it will require a lot of unnecessary JOINs that can quickly bloat up computational needs. An example that I have came across is the normalization of ‘days’ into a table of permanently 7 rows and 2 columns.

8. Indexing

Indexing is an optimization done in the database design.

Indexing allows the database to look through a mapping table to find the required row of data in the corresponding table rather than the whole table of data itself.

A mapping table is much lightweight, hence it reduces the time needed to get to a data, freeing up more resources for the database to handle more incoming requests.

Think of it as the table of content in a lengthy web page, book or catalog of grocery. You would do a “control F” to look for the information you want via the table of content rather than read from start to finish until you get to your data. That is indexing essentially.

7. Database Views

Database views is an optimization done on both application and database design level.

Database views are stored queries in the database. They can store temporary results and have an index attached to them.

The advantage of using database views over only indexing your tables is that the database now only has to go through the filtered results from the SQL query in the database view, as compared to an index which consist of all results without the filtered.

For example, if a database view has a query that only looks at records for this year, then your database will only be searching the records for only this year. Using only an index, it will have to search through the records since the start of time till this year, which is a lot less efficient. This stackoverflow answer answers it better.

6. Caching

Caching is an optimization done on the database infrastructure level.

Some of the information we display on our websites and apps are derived data from our database. Derived data are raw data from the database that are computed within your application based on business logic. Some examples I can think of are tabulating the total spent by users from an online shop which involves calculating the individual prices of each item, the quantity bought, discounts and miscellaneous fees like taxes and shipping.

These data would not change, given the same raw data and same computing algorithm. So rather than running through the same requests to get the same raw data from the database, and going through the same algorithm, it may make sense to cache it. We typically use cache servers, are not part of the typical databases and are add ons to the infrastructure, to handle this.

Cache servers like Redis stores data in RAM and not on the hard disk like typical databases. The significance of this distinction is that these memory on RAM can be accessed much quickly than those on the hard disk. It is also this exact reason that RAM is much more expensive than memory in the hard disk, thus destroying any idea you might have about using purely cache as the database.

This gives you much to think about what data should be cached and what should not. The art of using cache efficiently to break up the bottlenecks in your application requires much experience and experiment.

You also have to use them wisely because most cache have a limit on how much data you can store in it. Redis, for example, as a key-value store, at the very basic level, has a limit of 512MB for each value.

On top of that, you need to be smart about when and how to auto expire and explicitly expire cached data so that they show the latest data according to your application needs. For example, when there is a change in the raw data in your database, the computation has to be done again since we are talking about new and different input values.

5. Read Replicas

The use of read replicas is an optimization done on the database infrastructure level.

Read replicas involves spinning up more database copies of the master database to handle read loads. This spreads the load up, leaving mainly the write requests to the master database.

Some read requests that required strong consistency still need to go through the master database. This is due to the latency of data propagation from the master database to these read replicas when there are new changes made to the master database.

If your application is write intensive, this may not be the best tool for the job and it will achieve little improvement in performance.

4. Vertical Scaling

Vertical scaling is an optimization done on the database infrastructure level.

This is the oldest trick in the book: throw money at the problem. Upgrade the database or opt for a more IOPS intensive storage type.

This is ultimately a mere stop gap solution as there is a limit on how far this can take us. It is also a costly upgrade for a non future proof solution.

I perceive its main advantage as simply buying us time to prepare for the next level of scaling.

3. Vertical Partitioning

Vertical partitioning is an optimization done in the database infrastructure level.

Disclaimer: I have never experienced doing this, but I believe this is what vertical partitioning is theoretically about and loved to be pointed out if I am wrong about it.

This step is slightly different from what most people perceive of sharding, which is more commonly horizontal sharding that we will cover later. Vertical partitioning is a form of sharding that is easier to implement. I deem it the appetizer for sharding.

It involves splitting columns and even tables into a separate databases or “shards”. This reduces the data in the main database and thus its computing load. It also spreads the traffic, in particular write requests that replicas are not able to solve, to other shards.

Each shard itself can have its own read replica clusters to further reduce the distribute the load.

However, this complexity will seep into the application level as now your application needs to know which database to connect to to write or read whatever data.

2. Hybrid Databases

Vertical partitioning is an optimization done on the database infrastructure level.

Disclaimer: I have never experienced doing this, but I believe this is what vertical partitioning is theoretically and loved to be pointed out if I am wrong about it.

This is a follow up on vertical partitioning. We can use new and more appropriate technologies to the new shards that can manage that part of the application better.

For example, we can use NoSQL databases to handle the historical coordinates of vehicles for a location tracking module. The requirements of this module is places itself more towards the availability and partition tolerance in the CAP theorem. There is no imperative need for ACID properties to be upheld in database transactions, and eventual consistency under the principles of BASE is sufficient for this module, on a very general level. This allow us to utilize the scaling capabilities of the NoSQL database, at the expense of consistency in the data, which is something we can deal with.

That said, not all NoSQL databases are made equal. They do not all sacrifice consistency for availability and scaling. There are many flavors of NoSQL that will fit different requirement of your module and it is all about finding the correct tool for the correct job.

Another example of using hybrid databases is when you have a highly analytical application. We can partition the tables involved in the data computation into a shard, and perform an ETL process to store the data in a more efficient structure in databases that are more appropriate for analytical functions, like Amazon Redshift and Google’s BigQuery. It takes away the computational load from your application and database.

The advantage of this partitioning allow you to scale only the bottlenecks of your application in the most cost productive manner.

An example of this vertical partitioning is done by Airbnb for their chat module. They identified it as a bottle neck in their application and acted accordingly to it. They did not use a different technology for that partition in this case.

1. Sharding

Sharding, or horizontal partitioning, is an optimization done on the database infrastructure level.

Disclaimer: I have never experienced doing this, but I believe this is what horizontal partitioning is theoretically and loved to be pointed out if I am wrong about it.

Eventually, some of your tables will have so much data that there is a need to split the rows in the tables into different shards. For example, the first 10 million rows will be, in the same table, moved to a shard located in USA, the next 10 million will be, in the same table, placed in another shard located in Germany, and so on.

Usually at this point of time, you will have a handful of clusters of vertical shards. Horizontally sharding each of these clusters will not be manageable. I believe it is a complex mess to be handling this.

This also bring about new problems like cross shard latency at a global scale and application complexity to route the data to the correct shard. Add in the requirement for data recovery it is time to update your resume, as Mr. Sugu Sougoumarane mentions below, in his talk about the Vitess tool, which will bring me to the next point on this tool as a solution to sharding.

Before you carry out sharding, even for vertical partitions, you may want to consider Vitess. It is a database clustering management system for horizontal scaling to save you the complexity of handling that yourself as you scale so that you can spend your resources on the improving the application itself, which is what ultimately matters.

If I ever get to the point of having to do sharding, at least this will be the first tool that I will research and study more about to tackle the problem.

How To Use HTML Validation On Flatpickr

My go to date picker JavaScript library is flatpickr. It has a decent UI that can be customized easily, is lightweight, and is straight forward to implement. There is one particular flaw that I seek to address in this article, that is integrating it with the basic HTML validation.


I want to be able to use basic HTML validation on my date inputs. A date input with a simple required attribute should trigger the HTML validation if it is empty upon form submission.

I also would like to prevent users from being able to enter free text in the text field which is meant for date input.

However, flatpickr comes with a flaw that would demand a hack to make it work the way I want.

The Read Only Problem

The cause of its flaw is that flatpickr disables itself by slapping the input with a readonly attribute. A readonly attribute will cause the input to elude the grasp of the basic HTML validation during form submission. This is so as HTML validation ignores readonly, disabled and hidden elements.

The Catch-22 Solution

The immediate solution is to initialize the flatpickr instance with the option allowInput set to true. However, this will allow users to be able to enter free text in the date input, which is what I would also like to guard against.

The Hack

Hence, my solution here is to implement a listener that will toggle the input’s readonly attribute when the date picker dropdown is active, and toggle it back when the user has moved on from date picking.

The Code

flatpickr("[data-behavior='flatpickr']", {
  altInput: true,
  altFormat: 'F j, Y',
  dateFormat: 'Y-m-d',
  allowInput: true,
  onOpen: function(selectedDates, dateStr, instance) {
    $(instance.altInput).prop('readonly', true);
  onClose: function(selectedDates, dateStr, instance) {
    $(instance.altInput).prop('readonly', false);

Line 1 initializes the flatpickr instance on elements specified by the selector.

Line 2 to 4 are my custom configuration options. I am placing it here to demonstrate the hack for a non default scenario.

Line 2 indicates my intention to display my date values in an alternative format.

Line 3 indicates the alternative format to display in.

Line 4 indicates the date format that will eventually submitted to the form’s action endpoint.

These configurations will tell flatpickr to create 2 inputs.

One is hidden and meant to be submitted to the backend. This input will inherit the attributes of the original input element that would matter during submission, like the name and id. Let’s call this the hidden input.

The other input is meant for display purpose. The value in it will be shown the desired alternative input format. And since it is display, it will inherit the relevant attributes from the original input element that matters for display. For example, the style, class and in particular, the readonly and required attributes. Let’s call this the display input.

Line 5 removes the default readonly attribute that flatpickr will place on its target input elements.

Line 7 defines a function that will be triggered when the dropdown is active. It will find the display input and set it to readonly. This will prevent users from being able to entering any text that will mess up the input value.

Line 10 undo the effect of line 7 in the likely scenario when the user has finished picking the date and the date dropdown closes.

Line 11 handles the behavior where the input cursor remains on the date input when the datepicker dropdown is deactivated. A possible scenario that this might happen is when the user presses the escape key when the dropdown is active. When that happens, the readonly attribute is gone and the user is able to enter any text on the input. Thus, the blur() function prevents this.

How To SSH Into Private Servers Via A Bastion Without Copying SSH Keys

This is a documentation on the the process of accessing the public EC2 instances from a bastion server that is created in the private subnet, as a follow up to the article on setting up a proper cloud infrastructure with basic security for applications on AWS.


Once in a while, we need to communicate with the production servers to do checks. The proper way is to setup a bastion server in the public instance and ssh into them. However, setting the bastion server up with the proper configurations might be time consuming to get it right.

On top of that, once we are done, there is a financial incentive to shut the bastion server down to save cost. This will translate to more time consumed to spin it up and down.

Since we might not do this often, we would tend to forget how to set up or shut down the bastion server properly. This translates to more time debugging during each process should any steps be missed along the way.

Hence, it will be nice to have these processes recorded down in code.

Terraform Setup For Bastion Server

The terraform files to setup the bastion server is as shown below. This is a complete copy of the snippet in the article on setting up a standard AWS VPC using terraform. The explanation is there so I would not be covering that here.

# bastion
resource "aws_security_group" "bastion" {
  name = "${var.project_name}${var.env}-bastion"
  description = "For bastion server ${var.env}"
  vpc_id =

  tags = {
    Name = "${var.project_name}${var.env}"

resource "aws_security_group_rule" "ssh-bastion-world" {
  type = "ingress"
  from_port = 22
  to_port = 22
  protocol = "tcp"
  # Please restrict your ingress to only necessary IPs and ports.
  # Opening to can lead to security vulnerabilities
  # You may want to set a fixed ip address if you have a static ip
  security_group_id =
  cidr_blocks = [""]

resource "aws_security_group_rule" "ssh-bastion-web_server" {
  type = "egress"
  from_port = 22
  to_port = 22
  protocol = "tcp"
  security_group_id =
  source_security_group_id =

resource "aws_instance" "bastion" {
  ami = "ami-061eb2b23f9f8839c"
  associate_public_ip_address = true
  instance_type = "t2.nano"
  subnet_id =
  vpc_security_group_ids = ["${}"]
  key_name = aws_key_pair.main.key_name

  tags = {
    Name = "bastion-${var.project_name}${var.env}"

resource "aws_key_pair" "main" {
  key_name = "${var.project_name}-${var.env}"
  public_key = "ssh-rsa something"

output "bastion_public_ip" {
  value = aws_instance.bastion.public_ip

Retrieving AWS EC2 Client

I will be using ruby to carry out the ssh process because I am really bad with shell script 🙁

These snippets here are translated from a rake task which is what I use for my projects. There may be errors here and there so do understand the process rather than just plain copy!

require 'aws-sdk'

aws_access_key_id = `aws --profile #{aws_profile} configure get aws_access_key_id`.chomp
aws_secret_access_key = `aws --profile #{aws_profile} configure get aws_secret_access_key`.chomp

ec2_client =
  region: region,
  access_key_id: aws_access_key_id,
  secret_access_key: aws_secret_access_key

First, initialize an instance of EC2 client. That will require the correct access key id and secret access key. These can be easily retrieve by running the aws configure command in the shell.

Line 3 and 4 does this, given the desired aws_profile, and stores the value in respective ruby variables for use in the rest of the script.

Note that the back ticks (`), among other shell execution commands in ruby, should be used here as it is the only one the returns the output that we need to use. The chomp method removes the line break that is returned along with the output in the shell.

Retrieving The Bastion Server Instance

results = ec2_client.describe_instances(
  filters: [
      name: '',
      values: ["#{project_name}#{env}-bastion"]

raise 'There are more than 1 reservations. Please check!' if results.reservations.count > 1

raise 'There are no reservations. Please check!') if

instances = results.reservations.first.instances

raise 'There are more than 1 bastion servers. Please check!' if instances.count > 1

bastion = instances.first

Next we retrieve the bastion instance via the describe_instances method as shown on line 1.

On line 4 and 5, we narrow down our instances to search for using the filter This filter refers to the security group that we have attached to the bastion instance (see the terraform files).

The next few lines handle the unexpected scenarios of having multiple reservations and instances. I do not know the difference between these 2 entities, but I guess that is trivial to our mission here.

Eventually, we will have the access to the bastion instance.

Retrieving The Private Web Server Instance

results = ec2_client.describe_instances(
  filters: [
      name: '',
      values: ["#{project_name}#{env}-web-servers"]

raise 'There are no reservations' if

private_ip_addresses = do |reservation|

raise 'There are no private_ip_addresses.' if

instance_ip = private_ip_addresses.first

Next, we retrieve web server instances using the same method by filtering their security group’s name. Our target here is the private ip address of any one of the instances. Adjust accordingly if there is a particular private instance you are trying to access.

SSH Into Private Web Server Via Bastion Server

Here comes the main event, the ssh operation.

sh 'ssh-add -D'
sh "ssh-add -K #{Rails.root}/#{project_name}-#{env}"
sh('ssh ' \
'-tt ' \
'-A ' \
"-i #{Rails.root}/#{project_name}-#{env} " \
"ec2-user@#{bastion.public_ip_address} " \
'-o StrictHostKeyChecking=no ' \
"-o 'UserKnownHostsFile /dev/null' " \
"\"ssh ec2-user@#{instance_ip} " \
"-o 'UserKnownHostsFile /dev/null' " \
'-o StrictHostKeyChecking=no"')
sh 'ssh-add -D'

Use the sh utility command in ruby to execute shell script. We are not going to use the output of the commands here, so using back ticks is not necessary.

In this bash session, line 1 clears all ssh identities present if any with the -D option. Note that this bash session is decoupled from the bash session of the current terminal. Hence, at this point of time, there should not be any since it is a new session. We also do not need to worry about erasing the ssh agents that we have added. I am keeping it here for hygiene sake.

Line 2 adds the RSA identity of the key pair, which is used to create the bastion instance, to the ssh agent in the current session.

This step is extremely pivotal. It allows us to forward our ssh agent along with the required RSA identity to the bastion server. The bastion server will subsequently be able to authenticate with the web server due to the forwarded identity.

And realise this. All this is done without the bastion server actually possessing the ssh keys at all! This is immensely beneficial on the security side of things because the bastion server, as a server on the public subnet that is exposed to the Internet, is a point of vulnerability for your private instances. It poses a security risk if attackers are able to access the private instances using the ssh keys in the bastion server. But since the keys are not there, we can make sure Gandalf sees to them.

The command from line 3 onwards is the actual main ssh command.

Line 4 forces a pseudo-terminal allocation for us to interact with the web server once we have established the connection. Multiple t option ensures that the interactive session will be forced even if the ssh did not have a local tty for interaction purpose.

Line 5 forwards the ssh agent through the tunneling. And since we have added the RSA identity to the our ssh agent in this session, the authentication keys are also forwarded in the process, without make a copy in the bastion server itself.

Line 6 points to the identity file required to access the bastion server from our local machine. You would not need this line if you have created your bastion server and your web instances using the same key pair. For this case, this is an extra step that is not necessary as I have set up the web and bastion servers to use the same key pair.

Line 7 states the endpoint of the bastion server and where to ssh into.

Line 8 prevents the ssh mechanism to ask for our confirmation to carry out the operation.

Line 9 prevents our bastion’s ip address to be registered a known host on our ssh known_hosts file. As these bastion servers are meant to be shut down after use, their ip addresses will be different each time we spin them up. Hence, this option will prevent the unnecessary and unmonitored bulging of our known_hosts file.

Line 10 is the command to run after we have successfully ssh into the bastion server. In this case, we are running the a subsequent ssh command to ssh into the web server instance via its private ip address that we found earlier. Note that this command is wrapped in quotes.

To reiterate a few pointers here:

  • This subsequent ssh command does not require any identity file due to the RSA identity that is forwarded
  • The bastion server can access the private instances due to the setup of the security groups
  • The shell interaction session between the bastion server and the web instance is available to use on our local machine due to the -tt option mentioned in line 4.

Line 11 and 12 serve the same purpose as line 8 and, but this time for the bastion server’s ssh operation into the web servers.

Line 13 for hygiene sake, clear the RSA identity from the ssh agent.


There you have it, an ssh session via a bastion server without copying the security keys into it to ensure minimum vulnerability and maximum security!

How To Setup And Debug Google App Script

This is a quick start guide on setting up Google App Script and using it in G Suite applications. Mainly, I will go through Google Sheets and Google Drive since they are the most widely used services.


This is meant to remove the layer of repetitive mundane house keeping tasks via automation. In my side hustle, we have shifted our files from dropbox to Google Drive recently, bestowing us the ability to automate our tasks with Google App Scripts.


Head to your Google App Scripts console. There are many functions you can explore here. I will touch on just 3. Mainly the projects, executions and triggers.

Every project holds the script to execute based on a trigger. It is up to your jurisdiction to decide if a project should uphold a Single Responsibility Principle or do multiple task as part of a bigger singular operation.

Clicking on the ‘New Project’ button near the top left of the screen will bring you to the code editor where you can code your script.

In a script, you can define any number of functions. The exact function to run can be chosen during the trigger selection process. The usual setup is to have a main function, and the other functions are helpers.


The most important thing in coding is debugging. After all, it makes up most of our time as software developers.

In App Script, there is no luxury to debug the code interactively. You will need to rely on the usual logger. To print a log, write the code as such:

function main() {
  Logger.log('Hello World!');

There are 2 ways to view the logs.

First, within the script editor, go to View -> Logs. A dialog box will popup to show you the logs. A shortcut on mac is cmd + enter.

Second, is from the “My Executions” page back in the App Script console. I personally prefer looking at the logs through there because it does not only show its output but also other details like whether it is even running in the first place.

Click on the play arrow button to execute the function for debugging purposes.


In the App Script editor, click on the clock icon to bring yourself to the function’s triggers page.

Add a trigger by clicking the bottom right button. A dialog box will popup and you can select the conditions of the trigger.

You can select the function in the script to run, as mentioned earlier, and the type of trigger. For Google Sheets, there are more options for triggering the script. More on that later.


Before you begin, it is good to know that every entity in G Suite have an id. This id is the gibberish string that you see in the URL of an opened Google Sheets, Google Docs or even a folder in Google Drive. It is highlighted in yellow in the image below.

Google Docs ID

Knowing the id of the particular file or folder allow you to carry out your operations without having to write the code to search for it. Then again, you can search them by name.

The entities that can be called and utilized in the App Script are documented here. Let’s take a look at DriveApp for example.

Example With Google Drive On Time Driven Trigger

Let’s say you want to remove editors you previously gave access to in your files. You want them to be removed when the files are moved into a particular folder.

function removeEditors() {
  var folder = DriveApp.getFolderById(ID_OF_FOLDER);


function iterateFiles(folder) {
  var files = folder.getFiles();
  while (files.hasNext()) {
    var file =;
    Logger.log(`Looking at file ${file.getName()}`);

    var editors = file.getEditors();
    editors.forEach(function(editor) {
      var email = editor.getEmail();
      var approvedEmails = [

      if (!approvedEmails.includes(email)) {
        Logger.log(`Removing editor: ${email} from ${file.getName()}`);

Given the ID_OF_FOLDER, this script will iterate through all the files in that folder, and for each file it will check if its editors’ emails are under the list of approved emails. If their email is not in the list, they are stripped of the editor role in the file.

Note the way the files variable is being looped. The loop is carried out if hasNext() returns true, and the next file in line is retrieved via next(). This is different from how the editors are looped with forEach, which is, I believe, the usual way developers loop through iterators in JavaScript.

The last step is to setup the time driven trigger to your liking.

The code, unfortunately, cannot be optimized by checking the lastUpdatedDate() of the file and sparing the need to loop through editors for files that were moved into this folder eons ago. This is because moving files into different folders does not update the file’s lastUpdatedDate().

Albeit a small inconvenience, I do expect more features and attributes in the future in App Script to be developed for us to utilize and optimize our codes. Until then, I sincerely hope that it stays free, as it already it right now, without any usage limitation or tiering. In fact, I hope it stays free forever!

Example With Google Sheet OnEdit Trigger

Let’s look at another example with Google Sheet. In a spreadsheet, we want to compile the values entered in a sheet into another sheet in the same spreadsheet in real time. Simple and straightforward. Let’s see how we can work on it.

Before that, take note of an extremely crucial step. Make sure the spreadsheet is a Google Sheet. If you uploaded a Microsoft Excel sheet and opened it using Google Spreadsheet, you will not be able to run any App Script until you convert it to a Google Sheet. If this applies to you, go to File -> Save as Google Sheet as shown below to make this necessary change.

Save as Google Sheets

The function is as shown below.

function compile(event) {
  var row = event.range.getRow();
  var column = event.range.getColumn();
  var value = event.range.getValue();
  var spreadsheet = SpreadsheetApp.getActiveSpreadsheet();
  var targetSheet = spreadsheet.getSheetByName("Target Sheet")
  targetSheet.getRange(row, column).setValue(value * 2)

We get the row and column that the user was editing on, whichever sheet that was, and multiply its value by 2 before saving it in the same row and column in the desired sheet with the name Target Sheet.

Now to add the trigger. In the script editor, click on the clock icon. It will bring you to the triggers of this project. Click on the button to add trigger on the bottom right of the page. Under Select event source, you will now see a new option From spreadsheet, and when you select it, you can select the event type to kickstart the function. We are looking for the onEdit event type for this case.

As you can see, this project is associated to only 1 spreadsheet – the spreadsheet it was created from. Additionally, each spreadsheet can have only 1 project as well.

Hence, you cannot have the same script running on different spreadsheet. At least if you did it this way. There may be another way to do so and overcome this restriction but I have yet to explore it.


The potential of App Scripts does not end here. Other than scripts, you can even code out html views to present visual dashboard based on real time changes.

On top of that, you can publish you own app scripts, as well as use the scripts other developers have made. This forms a community can supercharge automation to increase productivity.


Make use of App Script and automate away!

Customize Devise Forgot Password Token In Rails

This is a documentation on how to change the user flow of forgot password using the devise gem.


I often work on projects that are purely API based and are served only on mobile devices as apps. This poses a problem when using devise because its main audience is web application. The user flow that it has set up thus assumes the presence and usage of web pages. That is absent for this case, and setting it up is troublesome to say the least.

In the case of forgot and resetting password flow, the user will receive an email with a link to reset their password. This link leads to a webpage and they will reset their password there and then.

For a pure API environment, this translates to an immense amount of extraneous work required. We need to setup the hosting of the webpages, prepare the styling assets, tweak css codes, wire up the SSL certificate, validate the input fields, and properly redirect from the website into the app once the password has been reset.

And the frustrating thing is that this is a small but essential function in a typical application. We cannot do away with it, but it is often neglected, or should I say taken for granted. And the disproportionally large effort it takes to set it up 1 web page just for this seemingly insignificant function is often overlooked.

I see the need to implement a way devise can allow user to change passwords without the use of webpage.

Project Specifications

The UX flow in my projects will look like this.

The reset password flow will send an email with a token that the users will enter in their app upon submitting the form on forgot password.

The user will enter their new password as well as the token in their app to change their password.

How Reset Password Work In Devise?

Before we can get to work, we need to understand how reset password flow runs in devise.

By default when the user submits his/her email in the forgot password flow, this controller method in the Devise::PasswordsController is called.

# POST /resource/password
def create
  self.resource = resource_class.send_reset_password_instructions(resource_params)
  yield resource if block_given?

  if successfully_sent?(resource)
    respond_with({}, location: after_sending_reset_password_instructions_path_for(resource_name))

The send_reset_password_instructions method is called on the class of the resource. The main code snippet is as shown below, retrieved from the source code in devise github repository.

module Devise
  module Models
    module Recoverable
      extend ActiveSupport::Concern
        def set_reset_password_token
          raw, enc = Devise.token_generator.generate(self.class, :reset_password_token)

          self.reset_password_token   = enc
          self.reset_password_sent_at =
          save(validate: false)
      module ClassMethods
        def send_reset_password_instructions(attributes={})
          recoverable = find_or_initialize_with_errors(reset_password_keys, attributes, :not_found)
          recoverable.send_reset_password_instructions if recoverable.persisted?

Eventually, the function set_reset_password_token function will be called to generate the reset_password_token. This method will eventually become one of the User model’s instance methods when it includes the recoverable module.

The logic of generating the reset_password_token is wrapped in the TokenGenerator class of the Devise module as shown below.

module Devise
  class TokenGenerator
    def generate(klass, column)
      key = key_for(column)

      loop do
        raw = Devise.friendly_token
        enc = OpenSSL::HMAC.hexdigest(@digest, key, raw)
        break [raw, enc] unless klass.to_adapter.find_first({ column => enc })

As I want user to generate a token that they will need to enter together when they submit their new password after receiving it from an email, I definitely want to dictate the number of characters the token has for the sake of humane user experience. We will see how to tweak this method to generate a token of suitable length.

The function send_reset_password_instructions will also be triggered thereafter to send an email. By default, the reset password token that was generated will be appended to a url that is sent along in that email. That url meant for the users to click and go to a webpage to change their password. For my case, I will not be presenting the url to be clicked in the email, but just the the token string instead.

Generate Custom Reset Password Token

Here we will change the set_reset_password_token for the User model. This will only affect the User model and not other models, which may be crucial for you.

In my projects, I usually have another devise model, ie. the AdminUser model who needs to access to a CMS system. The CMS system is authenticated by none other than devise in the usual devise way. Hence, I do not want to do a site way change to all my models due to this sort of “hybrid”.

Hence, the new code will look like this.

def set_reset_password_token
  raw, enc = Devise.token_generator.custom_generate(self.class, :reset_password_token)

  self.reset_password_token   = enc
  self.reset_password_sent_at =
  save(validate: false)

The only line that was change is line 3. I am using the custom_generate method, which I define below.

module Devise
  class TokenGenerator
    def custom_generate(klass, column)
      key = key_for(column)

      loop do
        raw = SecureRandom.alphanumeric(Rails.configuration.confirmation_token_length)
        enc = OpenSSL::HMAC.hexdigest(@digest, key, raw)
        break [raw, enc] unless klass.to_adapter.find_first({ column => enc })

Compared to the above, the only line that is changed in this case is line 7. The default method uses Devise.friendly_token, the source code of which can be found here.

I replaced it with a custom method of mine to generate and alphanumeric string of a custom desired length.

Seeing that I change so little for each part of the code, I could have just redefined the Devise.friendly_token and save some effort in copying and pasting codes. However, due to the fact that I am still going to have an AdminUser that will make use of the default configuration of devise as it, I cannot apply it site wide. Of course, if I have only 1 Devise model to work with, that will be a plausible route to take.

Send Email With Customized Reset Password Token

So now that the reset_password_token has been generated, it is time to send it out in the email.

There’s nothing to change on the Devise::Mailerclass here. All we need to change is the email view under reset_password_instructions.html.erb. Below is the default view from devise repository.

<p>Hello <%= %>!</p>

<p>Someone has requested a link to change your password. You can do this through the link below.</p>

<p><%= link_to 'Change my password', edit_password_url(@resource, reset_password_token: @token) %></p>

<p>If you didn't request this, please ignore this email.</p>
<p>Your password won't change until you access the link above and create a new one.</p

We now have the @token that we can just display for users as a string, and we do not need edit_password_url link to be generated.


This is how we can modify the reset_password_token using devise with the least possible code changes. It involves understanding the flow of logic throughout the different components in devise, as well as the role each component play, so that you know what can and should be modified. The same can be applied to the confirmation flow as well.

This can be integrated with doorkeeper and devise on top of this guide that I wrote on integrating these 2 gems without hiccups since the amount of changes is little and not show stopping.

Class And Instance Methods in Ruby Metaprogramming

This is my own summary on the class and instance methods in relation to metaprogramming in ruby.


Many articles out there have already given a detailed write up on this topic. Here I am giving my 2 cents, partly to help me revise when I stumble on this concept again. Because this is how I understand it.

The articles written by various other experienced developers are by no means inadequate. I guess it just people having different learning styles and so here I am documenting mine intending to serve only 1 audience, ie me 🙂

Start With The Syntax

I stumbled on this topic because of the various different syntaxes I have seen in various ruby code bases. And they are nothing like ruby. Weird symbols that go against ruby’s English like syntax and blocks with deep implicit meaning that brings about confusion when reading the code are some examples.

So I thought it is best to come clear with the syntaxes first.

Instance Methods

So there are a couple of ways to define instance methods in ruby.

class Instance1
  def hello
    p "self inside hello is #{self}"

  class_eval do
    def hello
      p "self inside class_eval hello is #{self}"

class Instance2
  class_eval do
    def hello
      p "self inside class_eval hello is #{self}"

  def hello
    p "self inside hello is #{self}"

Here are 2 classes Instance1 and Instance2 with the same method names and definitions. The only difference is the order which they are defined. And if we take a look at their output:

instance1 =
instance2 =

instance1.hello # "self inside class_eval hello is #<Instance1:0x00007ff17da771c0>"
instance2.hello # "self inside hello is #<Instance2:0x00007ff17d7bbb98>"

The method that is defined later will run. The significance here is that these 2 definitions are in fact the same thing. They are both legit but different ways to define instance methods, and the methods defined later will override the one defined initially as expected.

Class Methods

There are 3 different ways based on my research.

class Class1
  def self.hello
    p "self inside self.hello is #{self}"

  instance_eval do
    def hello
      p "self inside instance_eval hello is #{self}"

  class << self
    def hello
      p "self inside class << self is #{self}"

class Class2
  instance_eval do
    def hello
      p "self inside instance_eval hello is #{self}"

  class << self
    def hello
      p "self inside class << self is #{self}"

  def self.hello
    p "self inside self.hello is #{self}"

class Class3
  class << self
    def hello
      p "self inside class << self is #{self}"

  def self.hello
    p "self inside self.hello is #{self}"

  instance_eval do
    def hello
      p "self inside instance_eval hello is #{self}"

The same thing here. 3 classes with the same 3 methods defined in different order. And yes, the output will be dictated by last one that is defined.

Class1.hello # "self inside class << self is Class1"
Class2.hello # "self inside self.hello is Class2"
Class3.hello # "self inside instance_eval hello is Class3"

No shit. They are just different ways to do the same thing.

Best Practices

So now with the confusion over different syntaxes out of the way, let’s refer to a single class for the rest of the article.

class MyClass
  class_eval do
    def hello
      p "self inside class_eval hello is #{self}"

  instance_eval do
    def hello
      p "self inside instance_eval hello is #{self}"

MyClass.hello # "self inside instance_eval hello is MyClass" # "self inside class_eval hello is #<MyClass:0x00007ff188369ad0>"

These are the best practices to define a class method and an instance method in the metaprogramming way. The instance_eval method is especially important, in my humble opinion, in replacing the class << self syntax that is so baneful in ruby linguistics.

Reading ruby code is like reading English

Why The Need For a Different Way To Define A Method?

One of the purpose of metaprogramming derives from the need to define methods during runtime. They are often used in conjunction with the method define_method to define new methods based on variables that are only available during run time.

An example would be the current_user method in the authentication related devise gem. If you have multiple models, like AdminUser and Player on top of User, you can easily access an instance of them in the context of the controller via current_admin_user and current_player respectively. This is done without you having to copy paste the content of current_user into these “new” methods.

This is made possible due to metaprogramming. devise defines these new methods at runtime, looking at all the models that require its involvement, and generate these helper methods all without writing extra code.

The robustness of metaprogramming is clearly crucial and essential.

The Essence of Instance and Class of a Class

So there is this whole confusion about a hidden class in a class in ruby. This all stems from 1 fact: everything in ruby is an object. That includes a class.

Everything is an object in ruby

So how can a class as we know it, with all its inheritance and class method and instance method properties, be an instance of a ruby object?

This is made possible with the existence of a hidden metaclass whenever a class is defined in ruby. This hidden class holds the common properties of classes as we know them and allow us to use mere ruby objects like a class. There’s a lot of confusion in this sentence due to the overlapping usage of the word class. Be sure to read it again.

Hence class methods are in fact instance methods of this metaclass. These methods of the metaclass are not inherited by the instances of the class, just like how a class method should be.

Singleton Class In Ruby

Another name for these hidden metaclasses is singleton class (‘eigenclass’ is another). I find this naming more apt in the context of ruby (And I will refer to it as singleton class from here onwards). Allow me to explain.

Classes should have a unique namespace in its codebase. Therefore when a class is defined, and so for its corresponding metaclass, it will not be defined again. Its one and only instance of itself will thus exist for the lifetime of the application with no duplicate. This gives the term ‘singleton’ so much more sense.

In fact, I perceive it as the official definition in ruby because of the method singleton_class which gives an object instance access to its “metaclass” instance. Here is an example. # "self inside instance_eval hello is #<Class:#<MyClass:0x00007faa7a3bb448>>"

Note the memory address of the singleton class. It indicates that this singleton class is in fact an instance.

instance_eval and class_eval

With a better concept of a class, a singleton class and an instance, let’s look at instance_eval and class_eval block.

Initially, it came across to me as unintuitive that a class method is defined under instance_eval, and an instance method is defined under class_eval. Why make life so difficult?

However, once we understand the concept, everything will fall into place.

Under instance_eval, we are looking at the MyClass under the context that it is an instance. We are evaluating it as an instance. And an instance of a class can only refer to the singleton class that will hold anything that should possess the properties of a typical class that we know in computing.

Under class_eval, we are evaluating MyClass as a class, where we define methods to be applied on instances of MyClass as usual.

These 2 methods determine the context in which the methods in it are defined. In particular, it dictates what the variable self refers to in each scope. This article has a much detailed explanation on that.


There’s definitely more to metaprogramming that to define methods during runtime. This idea of using code to generate code has immense potential and this may just be only the tip of the iceberg.

Integrating reCaptcha V3 With Turbolinks In Rails

Google has published the latest new version of reCaptcha V3 and I had to integrate it into my recent Rails projects. The greatest difference between the old version is its improvement in user experience. It removes the user friction where users are required to click on the notorious “I am not a robot” check box and at times take some spontaneous image verification quiz. In its place, the new reCaptcha observes the user’s actions on the website to determine if he/she is a genuine human user. It generates a score which the backend of the website will need to verify against to decide if the score is above the threshold of what is considered a real user. On the frontend, there’s no more extra step required to submit the form. Pretty neat!

In the midst of integrating it to my project, I had some problems, as usual, with turbolinks. The biggest of them is navigating between pages. Hence, this article seeks to document the process.


Due to the use of turbolinks, the initialization process is different from what was documented. In fact, there is little to no documentation on the alternative way to initialize the recaptcha library. With reference to this blog, the initialization step is as such.

Note that I am using the slim template engine to generate my HTML views.

// in the < head >
script src=''
= javascript_pack_tag 'recaptcha', 'data-turbolinks-track': 'reload'

I insert this snippet at the head of the pages that requires reCaptcha using the content_for helper.

This method of requiring the file allow us to use a custom function to initialize the grecaptcha object. This thus provide us control as to when we want to initialize the object so as to prevent reinitialization when navigating between pages in a turbolinks environment.

This method is documented in an obscure area in the recaptcha V3 docs and is also usable in V2 as documented here.

The javascript function renderCaptcha will be called when the file has loaded, and it is constructed in the recaptcha.js.erb file.

Note that this file is given the attribute data-turbolinks-track with a value of reload. This implies that when we navigate between pages where the tracked assets required are different, the site will do a full reload instead of going through turbolinks. In particular for this case when navigating from a page with recaptcha to another without recaptcha, there will be a full reload of the page as the tracked asset, recaptcha.js.erb is no longer present.

This ensures that the recaptcha library is downloaded again and the renderCaptcha function is called when the script is loaded for initialization.

Let’s take a look at the content of the renderCaptcha function.

The Javascript

// recaptcha.js.erb
window.renderCaptcha = function() {
  document.grecaptchaClientId = grecaptcha.render('recaptcha_badge', {
    sitekey: "<%= Rails.application.credentials.dig(Rails.env.to_sym, :recaptcha, :site_key) %>",
    badge: 'inline', // must be inline
    size: 'invisible' // must be invisible
window.pollCaptchaToken = function() {
  setTimeout(window.pollCaptchaToken, 90000);
window.getCaptchaToken = function() {
  grecaptcha.execute(document.grecaptchaClientId).then(function(token) {
    document.getElementById('recaptcha_token').value = token;
document.addEventListener("turbolinks:load", () => {
  $('#contact-form').on('ajax:success', event => {

Firstly, note that this is an erb file. This allows us to render ruby variables into javascript and compiled by Webpacker during build time. Refer to this documentation on installing erb with Webpacker or my article on setting up bootstrap with Rails 6 and Webpacker on how to set this up. In this case, I am storing my recaptcha site key using the new Rails way since 5.2 and parsing it in the javascript file during build time for consumption.

The renderCaptcha() initializes the recaptcha script and renders the recaptcha badge on an HTML element with the id recaptcha_badge. Once initialized, the getCaptchaToken() will then retrieve the recaptcha token and utilize it in its callback function. I will be setting the value of the an input element with the id recaptcha_token. This input will be sent along to the backend for the backend to use for verification. More on the views in a bit.

My logic is to poll the new token every 1.5 minutes as the token expires every 2 minutes. The 30 seconds buffer should be sufficient for my backend, which will receive the recaptcha token, to verify with the recaptcha server before the token expires. I have split up pollCaptchaToken() with the actual function getCaptchaToken() to get the token because I will be using getCaptchaToken() explicitly after I submit the form to refresh the token.

Note the use of window and document here. These objects persist in between page navigations in a turbolinks environment. Hence, they provide us a way to keep track of data so we do not initialize the function multiple times while navigating back and forth. And the key data to track here is the grecaptchaClientId on the document object. It tracks whether we have initialized the recaptcha script already or not.

That said, remember the data-turbolinks-track attribute with the value reload added to the script? Once again, it ensures the page fully reloads should the tracked assets be any different in between page navigations. This ensures 2 things:

  1. Prevents multiple initilizations occurring while navigating between pages because grecaptchaClientId is not null
  2. Ensures initialization will occur when traversing from a page without the recaptcha script due to a full reload. Otherwise, we will have to wait for the polling function to happened before we can get our token, and that will be disastrous should the user submit the form with a blank token before that.

Lastly, I add an ajax:success event listener on the form to handle a successful remote javascript call to my Rails backend. Note that I cannot add the listener on the document object as such:

$(document).on('#contact-form', 'ajax:success', function() { ... })

As the document object persist between navigation, it will result in the event listener being added each time a page navigation occurs, hence causing undesirable effects.

The View

#recaptcha_badge.d-none data-turbolinks-permanent=''
= hidden_field_tag :recaptcha_token, '', data: { turbolinks_permanent:'' }

The #recaptcha_badge object will hold the badge of the reCaptcha. You can add styling in whatever way you want, but I am using the bootstrap d-none css class to hide it totally as I do not need it.

The hidden_field_tag renders a hidden input field where I will store the recaptcha token.

These elements are given the data-turbolinks-permanent attribute. This is a crucial step. It ensures that the elements with the same id are not re-rendered in between page navigations in a turbolinks environment. Persisting the form element across page loads prevents the input from losing the recaptcha token. Without it, we will need to wait for the polling function to occur again after navigation before we are able to get a new recaptcha token for submission.

That said, the data-turbolinks-permanent on the #recaptcha_badge may not be necessary. But I am just persisting it across pages as well for trivial reasons.

Of course, make sure the input is within the form element so that it gets passed to the backend upon submission.


This new recaptcha user experience is a definitely a good step towards improving conversion. But integrating with turbolinks is troublesome as always. I hope this article helped to address it, and provide enough explanation on why each step are required adequately.

Sort Algorithms Cheatsheet

This is a summary of the key features that make up an algorithm.


While it is easy to understand the concept of each sort algorithm, I find it difficult for me to remember the key steps that define an algorithm or is characteristic of that algorithm. That key step may prove to be pivotal in solving the algorithm but may come in as insignificant from the macro view of its concept.

Hence, I decided that it will be better for me to jot the key pointers down.


Key Steps

  • Gist: Using a pivot value, recursively split the array (or segments of array) and its resultant halves, where all the elements in left half is smaller than the pivot and all the elements in the right half is larger
  • 3 steps: stop condition, partition, recursion
    • Stop condition
      • Check if the given left index is strictly smaller than the given right index
      • If they are equal, it means we are dealing with 1 element and there’s nothing to sort
      • Left index should not and will not be more than the right index
    • Partition
      • The key here is to return a partition index
      • Randomly select element and use element value as pivot (pivot index is ignored)
      • Left and right index will traverse towards center
      • Stop incrementing left index when its value is greater than or equal pivot value
      • Stop decrementing right index when its value is smaller than or equal pivot value
      • Swap the values and continue traversing
      • Ensure left <= right (this logic should be hoisted to the top)
      • Return the left index as the partition index
      • This partition index will be the eventual midpoint of this subarray
    • Recursion
      • Call itself twice
      • One will use the given left index and partition index – 1
      • The other will the given right index the partition index + 1


  • Each iteration frees up 1 element
  • For each element freed, quicksort is executed lg n times on average
  • Average time complexity is n lg n
  • Worst case is n^2, if the pivot is always the smallest/largest value, so need to be careful when choosing pivot
  • Randomize selection of pivot to effectively reduce probability of hitting worst case
  • In place sorting algorithm where no extra memory is needed and the operation can be carried out on the array itself


Key Steps

  • Gist: first recursively halve array until we are dealing with 1 element, then recursively merge the elements back in a sorted order until we get back the array of the same size, and now it will be sorted
  • A recursive function that consist of 3 parts in order: split, recursion, merge
  • We will mutate the array, but it will not be an in place sorting. This is because it is difficult to do so.
  • So first create an empty arrayCopy of same size to temporarily hold the values of  sections of the original array that are already sorted to be overwritten into the corresponding section in the original array.
  • Split
    • Given a subarray array, the arrayCopy, the leftStart and rightEnd of the subarray to be split
    • Continue splitting and duplicate a copy of the left half and the right half
    • Stop condition: Stop the current iteration if the given array is only 1 element and just return
  • Recursion
    • Call itself on the left half
    • Then call itself on the right half
    • So the splitting will continue until we are dealing with 1 element to kick start the merge
  • Merge
    • Dealing with the same subarray from the split step, provided with the leftStart and rightEnd of the subarray
    • The leftEnd and the rightStart are at the midpoint of this subarray
    • These 4 key indices mirror the indices in the original array
    • Traverse from leftStart to leftEnd together from rightStart to rightEnd
    • Fill up the arrayCopy in ascending order
    • Ensure the indices do not overshoot its respective end
    • Eventually, one half will have all its elements filled up in the arrayCopy, while the other half can simply append the remaining elements to the arrayCopy from where it left off
    • The arrayCopy is sorted for that exact portion  of the original array, so we will overwrite that portion of the original array with the same portion of the arrayCopy
    • That portion of the original array may not be sorted in contemplation of its whole, but that will be addressed and its values overwritten in the subsequent merge steps.


  •  Time complexity of n lg neven in worst case
  • Need extra n space for the array copy

Insertion sort

Key Steps

  • Gist: insert elements one by one from unsorted part of array into sorted part of array
  • Divide the array into sorted portion and unsorted portion
  • Sorted partition always starts from the first element, as array of 1 element is always sorted
  • First element of unsorted array will shift forward until the start of the sorted portion of the array OR until it meets an element bigger than itself
  • Order of the sorted portion is maintained
  • The last element of the sorted array takes its place
  • The next iteration start on the next element of the unsorted portion, which is now the first element of the current unsorted portion
  • The loop mutates the array


  • Best case is an already sorted array, so no shifting of elements from the unsorted to the sorted portion of the array, resulting in a time complexity of n
  • The worst case is a reverse sorted array, which results in the whole sorted array having to shift for each iteration. The first element of the unsorted portion of array is always at the the smallest and need to go to the front of the sorted portion. Time complexity is n^2

Selection sort

Key Steps

  • Gist: scan array to find the smallest element and eliminate it for the next iterations
  • Swap smallest element with the front most element
  • Scan the array in the next iteration excluding the smallest element(s)
  • Last remaining single element will be of the largest value, so iterations take place until n - 2


  • Time complexity is n^2

Bubble sort

Key Steps

  • Gist: keep swapping adjacent elements if left is larger than right down the array, and repeat this iteration for as many time as there are elements in the array
  • End before the 2nd last index so that we do not go out of bound when comparing the current element with the next for swapping
  • The largest elements starts forming at the end of the array
  • Subsequent iterations can end before the already sorted section of the array at the end as optimization
  • A flag reseted at each iteration can be used to end the function early if no swap is detected for the current iteration, which would mean the array is already sorted


  • Time complexity is n^2