April 2017 – Hexadix

Hard Sudoku Solver Algorithm – Part 2

By Tan Nguyen | April 25, 2017 | Comments 0 Comment

Introduction

In part 1, we have solved some hard sudoku puzzles using the backtracking approach. While the algorithm did the job, it couln’t beat the time limit in the more advanced challenge: Hard Sudoku Solver 1.

This time, we are going to find a better solution so that we can pass the tests in the new challenge within the 10-second time limit.

It is recommended that you try to practice on your own first before going on to read the solution.

Problem description

From Codewars’ Hard Sudoku Solver 1:

There are several difficulty of sudoku games, we can estimate the difficulty of a sudoku game based on how many cells are given of the 81 cells of the game.

Easy sudoku generally have over 32 givens

Medium sudoku have around 30–32 givens

Hard sudoku have around 28–30 givens

Very Hard sudoku have less than 28 givens

Note: The minimum of givens required to create a unique (with no multiple solutions) sudoku game is 17.

A hard sudoku game means that at start no cell will have a single candidates and thus require guessing and trial and error. A very hard will have several layers of multiple candidates for any empty cell.

Your Task

Write a function that solves sudoku puzzles of any difficulty. The function will take a sudoku grid and it should return a 9×9 array with the proper answer for the puzzle.

Or it should raise an error in cases of: invalid grid (not 9×9, cell with values not in the range 1~9); multiple solutions for the same puzzle or the puzzle is unsolvable.

Analysis

Compared to the problem in part 1, this problem requires us to raise an error if there are more than one solution to the sudoku. Therefore, instead of return the first solution we found, we have to keep testing other possibilities to make sure that there are no other solution to the sudoku. The good news is, we can return an error early immediately when we found the second solution.

The hardest test that we are going to solve is the puzzle below, which has only 17 given numbers:

#### Should solve very hard puzzle
puzzle = \
    [[8, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 3, 6, 0, 0, 0, 0, 0],
     [0, 7, 0, 0, 9, 0, 2, 0, 0],
     [0, 5, 0, 0, 0, 7, 0, 0, 0],
     [0, 0, 0, 0, 4, 5, 7, 0, 0],
     [0, 0, 0, 1, 0, 0, 0, 3, 0],
     [0, 0, 1, 0, 0, 0, 0, 6, 8],
     [0, 0, 8, 5, 0, 0, 0, 1, 0],
     [0, 9, 0, 0, 0, 0, 4, 0, 0]]
solution = \
    [[8, 1, 2, 7, 5, 3, 6, 4, 9],
     [9, 4, 3, 6, 8, 2, 1, 7, 5],
     [6, 7, 5, 4, 9, 1, 2, 8, 3],
     [1, 5, 4, 2, 3, 7, 8, 9, 6],
     [3, 6, 9, 8, 4, 5, 7, 2, 1],
     [2, 8, 7, 1, 6, 9, 5, 3, 4],
     [5, 2, 1, 9, 7, 4, 3, 6, 8],
     [4, 3, 8, 5, 2, 6, 9, 1, 7],
     [7, 9, 6, 3, 1, 8, 4, 5, 2]]
assert(sudoku_solver(puzzle) == solution)

The backtracking approach

The first thing that we want to try is of course reusing the solution from the last challenge, with some modifications to fit the new additional requirements.

The sample code goes as below:

import copy

def sudoku_solver(puzzle):
    sudoku = Sudoku(puzzle)
    if not sudoku.valid:
        raise ValueError

    sudoku.solve()

    if len(sudoku.solutions) != 1:
        raise ValueError

    return sudoku.solutions[0]

class Sudoku:

    def __init__(self, board):
        # the 9x9 sudoku board
        self.board = []
        # list of solutions to this sudoku
        self.solutions = []
        # is the board valid
        self.valid = True


        # init a blank board with all cells filled with zero
        for i in range(9):
            r = [0] * 9
            self.board.append(r)

        # check the input board dimensions
        if not self.validate(board):
            self.valid = False

        # copy the input board to self.board
        for r in range(len(board)):
            for c in range(len(board[r])):
                if board[r][c]:
                    if not self.set(r, c, board[r][c]):
                        self.valid = False


    # validate board dimensions
    def validate(self, board):
        if len(board) != 9:
            return False
        for r in range(len(board)):
            if len(board[r]) != 9:
                return False
        return True

    # the main function to solve the sudoku
    def solve(self):
        # recursively solve the sudoku, starting from cell 0
        self.solve_helper(0)
        return self.solutions

    # given the sudoku has been filled up to cell k-1, try to solve the sudoku from cell k
    # k is the cell index, counting from left to right and top to bottom.
    #     k is 0, 1, 2, ..., 8     for cell (0,0), (0,1), (0,2), ..., (0,8)
    #     k is 9, 10, 11, ...,     for cell (1,0), (1,1), (1,2), ...
    #     k is 80                  for cell (8,8) (last cell)
    def solve_helper(self, k):
        # if we get pass the last cell, it means we have filled every cells with valid values.
        # return True to notify that we have found a solution
        if (k > 80):
            self.solutions.append(copy.deepcopy(self.board))
            return

        r = int(k / 9)
        c = k % 9

        # if this cell has been filled, go on to solve the next cell
        if self.board[r][c] != 0:
            return self.solve_helper(k+1)

        # try to fill each value from 1 to 9 in this cell
        for x in range(1, 10):
            # fill the cell with value x only if x has not appeared on the same row or col or 3x3 box
            if self.check(r, c, x):
                # start backtracking:
                # try x in this cell,
                self.board[r][c] = x
                # then try to solve from the next cell k+1,
                self.solve_helper(k+1)
                if len(self.solutions) >= 2:
                    # the problem requires us raise error if there are more than one solution,
                    # so we can skip further processing if 2 solutions have been found
                    return
                # then clear cell to return the board to the status before x was filled
                self.board[r][c] = 0

        # if we are here, it means we have tried all values in this cell without finding a solution
        # return False to notify upper recursive solve_helper that
        # we didn't find any solution given the current board status
        return False

    # check if value x can be put at cell[row][col]
    # return False   if value x has already been used in other cells on current row, or column, or 3x3 box
    # return True    otherwise
    def check(self, row, col, x):
        if not isinstance(x, int):
            return False
        if x < 1 or x > 9:
            return False
        for i in range(9):
            if self.board[row][i] == x:
                return False
            if self.board[i][col] == x:
                return False
        box_start_row = row - row % 3
        box_start_col = col - col % 3
        for r in range(box_start_row, box_start_row + 3):
            for c in range(box_start_col, box_start_col + 3):
                if self.board[r][c] == x:
                    return False

        return True

    # check if x can be put in cell [r][c]
    # if yes, put x in cell [r][c] and return True
    # if no, return False
    def set(self, r, c, x):
        if not self.check(r, c, x):
            return False

        self.board[r][c] = x
        return True

Test results

This code takes 45 seconds on my computer to solve the very hard puzzle above. Obviously, it didn’t make it through the Codewars’ hidden tests within the time limit.

Algorithm Optimizations

In the backtracking approach, we pick the first vacant cell and try every value at it. For each value, we then recursively pick the next vacant cell and try every value at the new cell. Although we do skip the values that will violates the existing values within the same row, column, and box, the number of branches that the program must try are still overwhelming.

The whole idea to optimize this algorithm is about reducing the branches that we have to test as much as possible.

Algorithm Optimization #1: Try to infer the values for the vacant cells from the existing values

The values can be inferred in two ways:

Rule 1: If cell [r][c] can only be filled with one value d (because other values already exists in the same row, column, or box), we can fill d in [r][c].
Rule 2: Because a value d must be filled exactly once in each unit (a unit means a row, a column, or a box), if all cells in a unit cannot be filled with d except for one cell, we can fill d in that cell.

Algorithm Optimization #2: Try to fail as early as possible

If we can detect that the current board status cannot be completed in any way, stop further processing on that case and return immediately.

We can detect this condition with the following checks:

Rule 3: If cell [r][c] cannot be filled with any value (because all values already exists in the same row, column, or box), the board is unsolvable.
Rule 4: If value d cannot be filled in any cell within a unit, the board is unsolvable.

Algorithm Optimization #3: Try to branch starting from the cell with fewest possible values

When no more cells can be inferred from the board, we have to go back to testing values at a vacant cell and recursively solve the board with the newly filled test value, similar to what we have been doing in the backtracking approach.

However, we can significantly reduce the number of cases to test by picking the cell with the minimum number of possible values, instead of picking the first vacant cell as usual. It’s like reducing the cases from 9*9*9*9*... to 2*3*2*2*....

Not only that this reduces the number of cases on each recursion, it also significantly reduces the depth of recursion, thanks to the inference process in Algorithm Optimization #1. In practice, this approach can reduces the number of recursive calls from hundreds of thousands calls to only several hundred calls.

Effectiveness

Believe it or not, using the above optimizations, most puzzles on Codewars’ tests, including hard ones, can be solved using only one or two recursive calls. By one recursive call, I mean we can inferred the whole board and don’t even need to test any value at any cell. In fact, except for the “very hard puzzle” mention at the beginning of this topic, all other puzzles can be solved with 6 recursive calls at most.

Implementation Optimizations

Although the algorithm optmizations seem promising, a bad implementation can ruin everything. Next, we are going to look at some implementation optimizations.

Implementation Optimization #1: Use a bit mask to mark allowed values at a cell

To efficiently check the possibilities at a cell, we can use a bit mask for each cell. The bit mask will be initialized as 0x1ff in hex or 111111111 in binary.

If value d is still allowed to be filled in a cell without conflicting with any other cells in the same row, column, or box, the dth bit of the cell’s mask is turned on.
If value d cannot be filled in a cell, the dth bit of the cell’s mask is turned off

More facts can be inferred from the above mask rule:

The initial value of the cell’s mask contains 9 set bits, indicating that all 9 values are still allowed in that cell.
If a mask has only 1 set bit at dth position, we can consider that d is filled in that cell (Rule 1).
If a mask is 0, we can consider the puzzle status is unsolvable (Rule 3).
Everytime a value d is set at cell [r][c], we also clear the dth bit in every cells in the same row, column, or box.

Some useful functions:
Check if a mask has only one bit (which means that cell has been set with a value):

def is_single_bit(m):
    return (m & (m - 1)) == 0

where m is the mask.

Check if a value d is allowed in cell [r][c]:

def is_allowed(m, d):
    return m & (1<<(d-1))

where m is the mask, d is the value we want to check.

Get the corresponding value from the mask, given we already know that the mask has only one set bit:

def get_value(m):
    return int(math.log2(m)) + 1

where m is the mask.

Count number of set bits in a mask:

def count_bits(m):
    count = 0
    while m:
        m &= (m - 1)
        count += 1
    return count

where m is the mask.

I have also tried using a precalculated bits_set table for fast lookup when counting number of set bits in a mask, however I cannot notice a performance increase in term of running time. The function goes as follow:

# precalculate the bits_set index table
bits_set = [0] * 256
for i in range(256):
    for d in range(1,10):
        if i & (1 << d-1):
            bits_set[i] += 1
def count_bits(m):
    return bits_set[m & 255] + bits_set[(m >> 8) & 255] \
        + bits_set[(m >> 16) & 255] + bits_set[(m >> 24) & 255]

Implementation Optimization #2: Use single dimension array instead of two-dimension array

At least, in Python. In my case, use single dimension array to store the mask instead of a two-dimension array speed the code up by two times.

Implementation Optimization #3: Set a value d to a cell by clearing all other bits instead of directly setting the dth bit

By doing this, everytime we clear an eth bit, we have a chance to count the number of remaining cells that still allow e in the related units (row, column, or box). If that number is 1, we can infer the place to fill e (Rule 2). If the number is 0, we can fail early (Rule 4).

Solution

Sample code

The following sample code is written in Python.

import copy
import math

def sudoku_solver(puzzle):
    # init a blank sudoku
    sudoku = Sudoku()
    
    # set the input board to our sudoku
    sudoku.setboard(puzzle)
    
    # if the input is invalid, raise an error
    if not sudoku.valid:
        raise ValueError

    # solve the sudoku, the results (if any) will be stored in sudoku.result_boards
    sudoku.solve()

    # if there are no solution, or there are more than 1 solution
    if len(sudoku.result_boards) != 1:
        raise ValueError

    # return the only solution
    return sudoku.result_boards[0]


class Sudoku:
    ### Notes:
    # cells will be indexed from 0 to 80


    ### init static constants:

    # list of the digits that will be filled in the sudoku
    digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    # List of block/units that each cell stays in.
    # For example, cell[9] (row 1, col 0) has 3 units:
    # units[9][0] == [9, 10, 11, 12, 13, 14, 15, 16, 17] (all cells in the same row)
    # units[9][1] == [0,  9, 18, 27, 36, 45, 54, 63, 72] (all cells in the same column)
    # units[9][2] == [0,  1,  2,  9, 10, 11, 18, 19, 20] (all cells in the same box)
    units = []

    # list of all peers of each cell, which are all the unique cells in the same row, column and box.
    # For example, cell[9] (row 1, col 0) has the following peers:
    # peers[9] == [9, 10, 11, 12, 13, 14, 15, 16, 17, 0, 18, 27, 36, 45, 54, 63, 72, 0, 1, 2, 19, 20]
    peers = []

    # init units and peers table
    for i in range(81):
        units.append([])
        # add cells in same row
        units[i].append([])
        r = int(i / 9)
        for c in range(9):
            units[i][0].append(r * 9 + c)
        # add cells in same col
        units[i].append([])
        c = int(i % 9)
        for r in range(9):
            units[i][1].append(r * 9 + c)
        # add cells in same box
        units[i].append([])
        br = int(int(i / 9) / 3)
        cr = int(int(i % 9) / 3)
        for r in range(br * 3, br * 3 + 3):
            for c in range(cr * 3, cr * 3 + 3):
                units[i][2].append(r * 9 + c)
        # collect all neighbor cells of each cell
        peers.append([])
        for unit in units[i]:
            for cell in unit:
                if cell not in peers[i]:
                    peers[i].append(cell)
        peers[i].remove(i)

    # init a blank sudoku
    def __init__(self):
        self.mask = []
        self.valid = True
        self.solutions = []
        self.result_boards = []

    # set the input board to our sudoku
    def setboard(self, board):
        # the mask array of the 80 cells
        self.mask = []

        # whether the sudoku is valid
        self.valid = True

        # the list of solutions (if any) in mask format
        self.solutions = []

        # the list of solutions (if any) in human readable array format
        self.result_boards = []

        # check the input board dimensions
        if not self.validate(board):
            self.valid = False

        # init mask matrix with all cells set to 0x1ff, indicating that all 9 digits are still allowed in that cell
        self.mask = [0x1ff] * 81

        # set the input board to this sudoku matrix, and also update the peers' masks for each cell along the way
        for r in range(len(board)):
            for c in range(len(board[r])):
                if board[r][c]:
                    # if the digit cannot be set at a cell, we mark that the input board is invalid (unsolvable)
                    if not self.set(r*9+c, board[r][c]):
                        self.valid = False
                        return


    # validate board dimensions
    def validate(self, board):
        if len(board) != 9:
            return False
        for r in range(len(board)):
            if len(board[r]) != 9:
                return False
        return True

    # convert mask to human readable two-dimensional array
    def mask_to_board(self, mask):
        board = []
        for r in range(9):
            board.append([0] * 9)
        for r in range(9):
            for c in range(9):
                if self.is_single_bit(mask[r*9+c]):
                    for d in self.digits:
                        if mask[r*9+c] & (1 << (d-1)):
                            board[r][c] = d
        return board

    # clone the current status of the sudoku
    def clone(self):
        sudoku = Sudoku()
        sudoku.mask = copy.copy(self.mask)
        sudoku.valid = self.valid
        return sudoku

    # the main function to solve the sudoku
    def solve(self):
        # call the recursive function solve_helper to solve
        self.solve_helper()

        # convert the solution masks into human readable two-dimensional array and stored in result_boards
        for result in self.solutions:
            self.result_boards.append(self.mask_to_board(result))

    # recursive function to solve the board
    def solve_helper(self):
        # choose the vacant cell with the fewest possibilities
        cell = self.find_vacant_with_min_possibilities()

        # if all cells have been filled (no vacant cell), we have found a solution!
        if cell is None:
            self.add_solution(self.mask)
            return

        # try the remaining possible value in this cell
        for d in self.digits:
            # skip if d is not allowed in this cell
            if not (self.mask[cell] & (1<<(d-1))):
                continue

            # clone the sudoku status...
            sudoku = self.clone()

            # ... and try digit d in the cloned one to start searching for a solution
            # if setting d in this cell leads to an unsolvable sudoku: stop further processing
            if not sudoku.set(cell, d):
                continue

            # solve the cloned sudoku with the newly filled value
            sudoku.solve_helper()

            # if we found any solutions for the cloned sudoku:
            if len(sudoku.solutions) > 0:
                # collect those solutions for our current sudoku
                for solution in sudoku.solutions:
                    self.add_solution(solution)

            # the problem requires us raise error if there are more than one solution,
            # so we can skip further processing if 2 solutions have been found
            if len(self.solutions) >= 2:
                return


    # a mask is considered as set if there's only one bit turned on.
    # m has exactly one bit turned on if (m & (m - 1)) == 0
    def is_single_bit(self, m):
        return (m & (m - 1)) == 0

    # count number of turned on bits in a mask
    def count_bits(self, m):
        count = 0
        while m:
            m &= (m - 1)
            count += 1
        return count

    # add a solution to our collection, skip if that solution already exists
    def add_solution(self, mask):
        for result in self.solutions:
            if result == mask:
                return
        self.solutions.append(copy.deepcopy(mask))


    # find the vacant cell with fewest allowed value
    def find_vacant_with_min_possibilities(self):
        vacant_cnt = 0
        best_vacant_possibilities = 10
        best_vacant_i = 0
        for i in range(81):
            if best_vacant_possibilities == 2:
                break;
            if not self.is_single_bit(self.mask[i]):
                vacant_cnt += 1
                choices = self.count_bits(self.mask[i])

                if choices < best_vacant_possibilities:
                    best_vacant_possibilities = choices
                    best_vacant_i = i

        if (vacant_cnt == 0):
            # no more vacant cell:
            return None

        return best_vacant_i

    # set digit d at cell by clearing all the other bits (except for dth bit) in mask[cell]
    # return False if a contradiction is detected.
    # return True otherwise
    def set(self, cell, d):
        other_values = [ d2 for d2 in self.digits if d2 != d and self.mask[cell] & (1<<(d2-1)) ]
        for d2 in other_values:
            if not self.clear(cell, d2):
                return False
        return True

    # removing a digit d from being allowed at cell by clearing the dth bit
    def clear(self, cell, d):
        # if already cleared
        if not (self.mask[cell] & (1<<(d-1))):
            return True

        # turn off bit at d to mark d is no longer allowed at this cell
        self.mask[cell] &= ~(1<<(d-1))

        # Rule 1: If this cell has only one allowed value d2,
        # then make d2 the value at cell and eliminate d2 from the peers.
        if self.mask[cell] == 0:
            return False  # error: no value is allowed at this cell (Rule 3)
        elif self.is_single_bit(self.mask[cell]):
            val = int(math.log2(self.mask[cell])) + 1
            for cell2 in self.peers[cell]:
                if not self.clear(cell2, val):
                    return False

        ## Rule 2: If all cells in the unit cannot be filled with d except for one cell2,
        # we can fill d in that cell2.
        for u in self.units[cell]:
            dplaces = [cell2 for cell2 in u if self.mask[cell2] & (1<<(d-1))]
            if len(dplaces) == 0:
                return False  # error: no place for this value (Rule 4)
            elif len(dplaces) == 1:
                # d can only be in one place in unit; assign it there
                if not self.set(dplaces[0], d):
                    return False
        return True

Test the code

puzzle = \
    [[8, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 3, 6, 0, 0, 0, 0, 0],
     [0, 7, 0, 0, 9, 0, 2, 0, 0],
     [0, 5, 0, 0, 0, 7, 0, 0, 0],
     [0, 0, 0, 0, 4, 5, 7, 0, 0],
     [0, 0, 0, 1, 0, 0, 0, 3, 0],
     [0, 0, 1, 0, 0, 0, 0, 6, 8],
     [0, 0, 8, 5, 0, 0, 0, 1, 0],
     [0, 9, 0, 0, 0, 0, 4, 0, 0]]
solution = \
    [[8, 1, 2, 7, 5, 3, 6, 4, 9],
     [9, 4, 3, 6, 8, 2, 1, 7, 5],
     [6, 7, 5, 4, 9, 1, 2, 8, 3],
     [1, 5, 4, 2, 3, 7, 8, 9, 6],
     [3, 6, 9, 8, 4, 5, 7, 2, 1],
     [2, 8, 7, 1, 6, 9, 5, 3, 4],
     [5, 2, 1, 9, 7, 4, 3, 6, 8],
     [4, 3, 8, 5, 2, 6, 9, 1, 7],
     [7, 9, 6, 3, 1, 8, 4, 5, 2]]
assert(sudoku_solver(puzzle) == solution)

Result

The new code solve the "very hard puzzle" above in about 0.1s. Compared to 40s in the backtracking approach, this is a 400 times increase in performance.

Try to submit the code on Codewars, and we pass all the tests in less then 300ms. Yay!

Conclusion

By applying some optimizations on both the algorithm and the implementation, we can see a significant increase in performance of our sudoku solver program.

Notice that the rules added to the algorithm are copied from the way that "human" uses to solve sudokus. Does that mean human brains have always been implemented with the most advanced algorithms?

There are still places for improvements, to solve even harder puzzles like the one below:

# 17 cells with thousands of solution
puzzle = \
    [[0, 0, 0, 0, 0, 6, 0, 0, 0],
     [0, 5, 9, 0, 0, 0, 0, 0, 8],
     [2, 0, 0, 0, 0, 8, 0, 0, 0],
     [0, 4, 5, 0, 0, 0, 0, 0, 0],
     [0, 0, 3, 0, 0, 0, 0, 0, 0],
     [0, 0, 6, 0, 0, 3, 0, 5, 4],
     [0, 0, 0, 3, 2, 5, 0, 0, 6],
     [0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0]]

or this one:

# 16 cells with no solution
puzzle = \
    [[0, 0, 0, 0, 0, 5, 0, 8, 0],
     [0, 0, 0, 6, 0, 1, 0, 4, 3],
     [0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 1, 0, 5, 0, 0, 0, 0, 0],
     [0, 0, 0, 1, 0, 6, 0, 0, 0],
     [3, 0, 0, 0, 0, 0, 0, 0, 5],
     [5, 3, 0, 0, 0, 0, 0, 6, 1],
     [0, 0, 0, 0, 0, 0, 0, 0, 4],
     [0, 0, 0, 0, 0, 0, 0, 0, 0]]

For these two puzzles, the algorithm in this topic still takes too long to complete. Hope we can find better algorithms to solve these puzzle faster in the future. On the other hand, solving sudoku in parallel (e.g. multithread or MapReduce) is also an interesting topic to discuss.

Hard Sudoku Solver Algorithm – Part 1

By Tan Nguyen | April 22, 2017 | Comments 0 Comment

Introduction

How fast is your sudoku solver algorithm? Can it beat the time limit on this Codewars challenge? If you get a timeout, welcome to my world! 😀

In this two-part blog series, I’m going to share my experience while solving the sudoku challenges on Codewars. Part 1 will try to solve easier puzzles while Part 2 will try to solve harder ones.

The challenges that I will try to solve are listed below:

Challenge 1 and challenge 2 only require us to find one solution, so the running time is not that critical. However, Challenge 3 requires us to find all solutions, so it’s more challenging to beat the running time limit.

This blog will focus on solving challenge 2 Hard Sudoku Solver, leaving challenge 3 Hard Sudoku Solver 1 for the next blog.

Note that the solution in this blog can be used to pass both challenge 1 and 2, without any modification or optimization.

It is recommended that you try to practice on your own first before going on to read the solution.

Problem description

From Codewars’ Hard Sudoku Solver:

This kata is a harder version of Sudoku Solver made by @pineappleclock

Write a function that will solve a 9×9 Sudoku puzzle. The function will take one argument consisting of the 2D puzzle array, with the value 0 representing an unknown square.

The Sudokus tested against your function will be “insane” and can have multiple solutions. The solution only need to give one valid solution in the case of the multiple solution sodoku.

It might require some sort of brute force.

Consider applying algorithm with

Hidden Candidates

Naked-pairs/triples/quads

Intersection removal

Backtracking

Brute Force

For Sudoku rules, see the Wikipedia article.

Used puzzle from Extreme Sudoku.

We have to write a function like this:
def solve(puzzle):
    """return the solved puzzle as a 2d array of 9 x 9"""
    return puzzle
Our function should solve puzzles like this:
puzzle = \
    [[5,3,0,0,7,0,0,0,0],
     [6,0,0,1,9,5,0,0,0],
     [0,9,8,0,0,0,0,6,0],
     [8,0,0,0,6,0,0,0,3],
     [4,0,0,8,0,3,0,0,1],
     [7,0,0,0,2,0,0,0,6],
     [0,6,0,0,0,0,2,8,0],
     [0,0,0,4,1,9,0,0,5],
     [0,0,0,0,8,0,0,7,9]]

solve(puzzle)
The function should return solution like this:
    [[5,3,4,6,7,8,9,1,2],
     [6,7,2,1,9,5,3,4,8],
     [1,9,8,3,4,2,5,6,7],
     [8,5,9,7,6,1,4,2,3],
     [4,2,6,8,5,3,7,9,1],
     [7,1,3,9,2,4,8,5,6],
     [9,6,1,5,3,7,2,8,4],
     [2,8,7,4,1,9,6,3,5],
     [3,4,5,2,8,6,1,7,9]]

Solution

Although the testing puzzles to are going to be “hard”, the challenge only require us to return one solution. Therefore, we can use the simplest algorithms to beat it within the allowed time frame. I’m going to use backtracking to solve the problem.

The algorithm

For the sake of applying backtracking, we will count the cells like this.

Small tip from Professor Robert Sedgewick:
Use r and c for iteration variables instead from i and j will make the code less confusing and more readable.

The algorithm goes like this:

Recursively solve the board, starting from cell k=0
For each cell k, try to fill every possible value in cell k.
- With each value filled in cell k, try to solve the board from cell k+1 with the current board status
- If solving from cell k+1 return a solution: return True
- Otherwise, try another value in cell k
- If all values have been tried without finding a solution: return False

Note that in the above algorithm, every time we try to solve the board at cell k, we know that all cells from 0 to k-1 has already been filled with either the initial given puzzle value, or with a “test value” at a previous step.

Sample code

The following sample code is written in Python.

def solve(board):
    sudoku = Sudoku(board)
    result = sudoku.solve()

    return result

class Sudoku:
    result = []
    board = []

    def __init__(self, board):
        self.board = board

    # check if value x can be put at cell[row][col]
    # return False   if value x has already been used in other cells on current row, or column, or 3x3 box
    # return True    otherwise
    def check(self, row, col, x):
        for i in range(9):
            if self.board[row][i] == x:
                return False
            if self.board[i][col] == x:
                return False
        box_start_row = row - row % 3
        box_start_col = col - col % 3
        for r in range(box_start_row, box_start_row + 3):
            for c in range(box_start_col, box_start_col + 3):
                if self.board[r][c] == x:
                    return False

        return True

    # solve the sudoku and return one result
    def solve(self):
        # init the solve_helper at cell (0, 0)
        if self.solve_helper(0):
            return self.board
        else:
            return None

    # given the sudoku has been filled up to cell k-1, try to solve the sudoku from cell k
    # k is the cell index, counting from left to right and top to bottom.
    #     k is 0, 1, 2, ..., 8     for cell (0,0), (0,1), (0,2), ..., (0,8)
    #     k is 9, 10, 11, ...,     for cell (1,0), (1,1), (1,2), ...
    #     k is 80                  for cell (8,8) (last cell)
    def solve_helper(self, k):
        # if we get pass the last cell, it means we have filled every cells with valid values.
        # return True to notify that we have found a solution
        if (k > 80):
            return True

        r = int(k / 9)
        c = k % 9

        # if this cell has been filled, go on to solve the next cell
        if self.board[r][c] != 0:
            return self.solve_helper(k+1)

        # try to fill each value from 1 to 9 in this cell
        for x in range(1, 10):
            # fill the cell with value x only if x has not appeared on the same row or col or 3x3 box
            if self.check(r, c, x):
                # start backtracking:
                # try x in this cell,
                self.board[r][c] = x
                # then try to solve from the next cell k+1,
                if self.solve_helper(k+1):
                    # solving from k+1 did find one solution (because solve_helper(k+1) returned True)
                    # since we only need 1 solution, we can stop further processing and return here
                    # return True to notify upper recursive solve_helper that we found a solution.
                    return True
                # then clear cell to return the board to the status before x was filled
                self.board[r][c] = 0

        # if we are here, it means we have tried all values in this cell without finding a solution
        # return False to notify upper recursive solve_helper that
        # we didn't find any solution given the current board status
        return False

Test the code

problem = \
    [[9, 0, 0, 0, 8, 0, 0, 0, 1],
     [0, 0, 0, 4, 0, 6, 0, 0, 0],
     [0, 0, 5, 0, 7, 0, 3, 0, 0],
     [0, 6, 0, 0, 0, 0, 0, 4, 0],
     [4, 0, 1, 0, 6, 0, 5, 0, 8],
     [0, 9, 0, 0, 0, 0, 0, 2, 0],
     [0, 0, 7, 0, 3, 0, 2, 0, 0],
     [0, 0, 0, 7, 0, 5, 0, 0, 0],
     [1, 0, 0, 0, 4, 0, 0, 0, 7]]

solution = \
    [[9, 2, 6, 5, 8, 3, 4, 7, 1],
     [7, 1, 3, 4, 2, 6, 9, 8, 5],
     [8, 4, 5, 9, 7, 1, 3, 6, 2],
     [3, 6, 2, 8, 5, 7, 1, 4, 9],
     [4, 7, 1, 2, 6, 9, 5, 3, 8],
     [5, 9, 8, 3, 1, 4, 7, 2, 6],
     [6, 5, 7, 1, 3, 8, 2, 9, 4],
     [2, 8, 4, 7, 9, 5, 6, 1, 3],
     [1, 3, 9, 6, 4, 2, 8, 5, 7]]

assert(solve(problem) == solution)

Result

Try to submit this code on Codewars, we can pass all tests. Yay!

Conclusion

In this blog, we have solved the hard sudoku problem using the backtracking approach. However this algorithm cannot beat the time limit on this harder challenge.

In the next part, we are going to discuss how to optimize the algorithm to pass all the tests of the harder challenge within the time limit.

Nginx security vulnerabilities and hardening best practices – part II: SSL

By Tan Nguyen | April 17, 2017 | Comments 0 Comment

Have you read part I? Nginx security vulnerabilities and hardening best practices – part I

Introduction

HTTP is a plain text protocol and it is open to man-in-the-middle attacks and passive monitoring. If our website allow users to authenticate, we should use SSL to encrypt the content sent and received between users and our web server.

Google has already considered HTTPS one of their ranking factors:

Security is a top priority for Google. We invest a lot in making sure that our services use industry-leading security, like strong HTTPS encryption by default. That means that people using Search, Gmail and Google Drive, for example, automatically have a secure connection to Google.

Beyond our own stuff, we’re also working to make the Internet safer more broadly. A big part of that is making sure that websites people access from Google are secure. For instance, we have created resources to help webmasters prevent and fix security breaches on their sites.

We want to go even further. At Google I/O a few months ago, we called for “HTTPS everywhere” on the web.

HTTPS are becoming a standard in HTTP environment. To help securing the HTTP environment, there are organizations that are issuing free SSL certificates that we can use on our website, such as Let’s Encrypt. So there’s no excuses for not applying HTTPS on our website.

The default SSL configuration on nginx are vulnerable to some common attacks. SSL Labs provides us with a free scan to check if our SSL configuration is secure enough. If our website gets anything below A, we should review our configurations.

In this tutorial, we are going to look at some common SSL vulnerabilites and how to harden nginx’s SSL configuration against them. At the end of this tutorial, hopefully we can get an A+ in SSL Labs’s test.

Prerequisites

In this tutorial, let’s assume that we already have a website hosted on an nginx server. We have also bought an SSL certificate for our domain from a Certificate Authority or got a free one from Let’s Encrypt.

If you need more information on SSL vulnerabilities, you can try following the links below:

We are going to edit the nginx settings in the file /etc/nginx/sited-enabled/yoursite.com (On Ubuntu/Debian) or in /etc/nginx/conf.d/nginx.conf (On RHEL/CentOS).

For the entire tutorial, you need to edit the parts between the server block for the server config for port 443 (ssl config). At the end of the tutorial you can find the complete config example.

Make sure you back up the files before editing them!

The BEAST attack and RC4

In short, by tampering with an encryption algorithm’s CBC – cipher block chaining – mode’s, portions of the encrypted traffic can be secretly decrypted. More info on the above link.

Recent browser versions have enabled client side mitigation for the beast attack. The recommendation was to disable all TLS 1.0 ciphers and only offer RC4. However, RC4 has a growing list of attacks against it, many of which have crossed the line from theoretical to practical. Moreover, there is reason to believe that the NSA has broken RC4, their so-called “big breakthrough.”

Disabling RC4 has several ramifications. One, users with shitty browsers such as Internet Explorer on Windows XP will use 3DES in lieu. Triple-DES is more secure than RC4, but it is significantly more expensive. Your server will pay the cost for these users. Two, RC4 mitigates BEAST. Thus, disabling RC4 makes TLS 1.0 users susceptible to that attack, by moving them to AES-CBC (the usual server-side BEAST “fix” is to prioritize RC4 above all else). I am confident that the flaws in RC4 significantly outweigh the risks from BEAST. Indeed, with client-side mitigation (which Chrome and Firefox both provide), BEAST is a nonissue. But the risk from RC4 only grows: More cryptanalysis will surface over time.

Factoring RSA-EXPORT Keys (FREAK)

FREAK is a man-in-the-middle (MITM) vulnerability discovered by a group of cryptographers at INRIA, Microsoft Research and IMDEA. FREAK stands for “Factoring RSA-EXPORT Keys.”

The vulnerability dates back to the 1990s, when the US government banned selling crypto software overseas, unless it used export cipher suites which involved encryption keys no longer than 512-bits.

It turns out that some modern TLS clients – including Apple’s SecureTransport and OpenSSL – have a bug in them. This bug causes them to accept RSA export-grade keys even when the client didn’t ask for export-grade RSA. The impact of this bug can be quite nasty: it admits a ‘man in the middle’ attack whereby an active attacker can force down the quality of a connection, provided that the client is vulnerable and the server supports export RSA.

There are two parts of the attack as the server must also accept “export grade RSA.”

The MITM attack works as follows:

In the client’s Hello message, it asks for a standard ‘RSA’ ciphersuite.
The MITM attacker changes this message to ask for ‘export RSA’.
The server responds with a 512-bit export RSA key, signed with its long-term key.
The client accepts this weak key due to the OpenSSL/SecureTransport bug.
The attacker factors the RSA modulus to recover the corresponding RSA decryption key.
When the client encrypts the ‘pre-master secret’ to the server, the attacker can now decrypt it to recover the TLS ‘master secret’.
From here on out, the attacker sees plaintext and can inject anything it wants.

Logjam (DH EXPORT)

Researchers from several universities and institutions conducted a study that found an issue in the TLS protocol. In a report the researchers report two attack methods.

Diffie-Hellman key exchange allows that depend on TLS to agree on a shared key and negotiate a secure session over a plain text connection.

With the first attack, a man-in-the-middle can downgrade a vulnerable TLS connection to 512-bit export-grade cryptography which would allow the attacker to read and change the data. The second threat is that many servers and use the same prime numbers for Diffie-Hellman key exchange instead of generating their own unique DH parameters.

The team estimates that an academic team can break 768-bit primes and that a nation-state could break a 1024-bit prime. By breaking one 1024-bit prime, one could eavesdrop on 18 percent of the top one million HTTPS domains. Breaking a second prime would open up 66 percent of VPNs and 26 percent of SSH servers.

Later on in this guide we generate our own unique DH parameters and we use a ciphersuite that does not enable EXPORT grade ciphers. Make sure your OpenSSL is updated to the latest available version and urge your clients to also use upgraded software. Updated browsers refuse DH parameters lower than 768/1024 bit as a fix to this.

Cloudflare has a detailed guide on logjam.

Heartbleed

Heartbleed is a security bug disclosed in April 2014 in the OpenSSL cryptography library, which is a widely used implementation of the Transport Layer Security (TLS) protocol. Heartbleed may be exploited regardless of whether the party using a vulnerable OpenSSL instance for TLS is a server or a client. It results from improper input validation (due to a missing bounds check) in the implementation of the DTLS heartbeat extension (RFC6520), thus the bug’s name derives from “heartbeat”. The vulnerability is classified as a buffer over-read, a situation where more data can be read than should be allowed.

What versions of the OpenSSL are affected by Heartbleed?

Status of different versions:

OpenSSL 1.0.1 through 1.0.1f (inclusive) are vulnerable
OpenSSL 1.0.1g is NOT vulnerable
OpenSSL 1.0.0 branch is NOT vulnerable
OpenSSL 0.9.8 branch is NOT vulnerable

The bug was introduced to OpenSSL in December 2011 and has been out in the wild since OpenSSL release 1.0.1 on 14th of March 2012. OpenSSL 1.0.1g released on 7th of April 2014 fixes the bug.

By updating OpenSSL you are not vulnerable to this bug.

SSL Compression (CRIME attack)

The CRIME attack uses SSL Compression to do its magic. SSL compression is turned off by default in nginx 1.1.6+/1.0.9+ (if OpenSSL 1.0.0+ used) and nginx 1.3.2+/1.2.2+ (if older versions of OpenSSL are used).

If you are using al earlier version of nginx or OpenSSL and your distro has not backported this option then you need to recompile OpenSSL without ZLIB support. This will disable the use of OpenSSL using the DEFLATE compression method. If you do this then you can still use regular HTML DEFLATE compression.

SSLv2 and SSLv3

SSL v2 is insecure, so we need to disable it. We also disable SSLv3, as TLS 1.0 suffers a downgrade attack, allowing an attacker to force a connection to use SSLv3 and therefore disable forward secrecy.

Again edit the config file:

ssl_protocols TLSv1 TLSv1.1 TLSv1.2;

Poodle and TLS-FALLBACK-SCSV

SSLv3 allows exploiting of the POODLE bug. This is one more major reason to disable this.

Google have proposed an extension to SSL/TLS named TLSFALLBACKSCSV that seeks to prevent forced SSL downgrades. This is automatically enabled if you upgrade OpenSSL to the following versions:

OpenSSL 1.0.1 has TLSFALLBACKSCSV in 1.0.1j and higher.
OpenSSL 1.0.0 has TLSFALLBACKSCSV in 1.0.0o and higher.
OpenSSL 0.9.8 has TLSFALLBACKSCSV in 0.9.8zc and higher.

The Cipher Suite

Forward Secrecy ensures the integrity of a session key in the event that a long-term key is compromised. PFS accomplishes this by enforcing the derivation of a new key for each and every session.

This means that when the private key gets compromised it cannot be used to decrypt recorded SSL traffic.

The cipher suites that provide Perfect Forward Secrecy are those that use an ephemeral form of the Diffie-Hellman key exchange. Their disadvantage is their overhead, which can be improved by using the elliptic curve variants.

The following two ciphersuites are recommended by me, and the latter by the Mozilla Foundation.

The recommended cipher suite:

ssl_ciphers 'EECDH+AESGCM:EDH+AESGCM:AES256+EECDH:AES256+EDH';

The recommended cipher suite for backwards compatibility (IE6/WinXP):

ssl_ciphers "EECDH+AESGCM:EDH+AESGCM:ECDHE-RSA-AES128-GCM-SHA256:AES256+EECDH:DHE-RSA-AES128-GCM-SHA256:AES256+EDH:ECDHE-RSA-AES256-GCM-SHA384:DHE-RSA-AES256-GCM-SHA384:ECDHE-RSA-AES256-SHA384:ECDHE-RSA-AES128-SHA256:ECDHE-RSA-AES256-SHA:ECDHE-RSA-AES128-SHA:DHE-RSA-AES256-SHA256:DHE-RSA-AES128-SHA256:DHE-RSA-AES256-SHA:DHE-RSA-AES128-SHA:ECDHE-RSA-DES-CBC3-SHA:EDH-RSA-DES-CBC3-SHA:AES256-GCM-SHA384:AES128-GCM-SHA256:AES256-SHA256:AES128-SHA256:AES256-SHA:AES128-SHA:DES-CBC3-SHA:HIGH:!aNULL:!eNULL:!EXPORT:!DES:!MD5:!PSK:!RC4";

If your version of OpenSSL is old, unavailable ciphers will be discarded automatically. Always use the full ciphersuite above and let OpenSSL pick the ones it supports.

The ordering of a ciphersuite is very important because it decides which algorithms are going to be selected in priority. The recommendation above prioritizes algorithms that provide perfect forward secrecy.

Older versions of OpenSSL may not return the full list of algorithms. AES-GCM and some ECDHE are fairly recent, and not present on most versions of OpenSSL shipped with Ubuntu or RHEL.

Prioritization logic

ECDHE+AESGCM ciphers are selected first. These are TLS 1.2 ciphers. No known attack currently target these ciphers.
PFS ciphersuites are preferred, with ECDHE first, then DHE.
AES 128 is preferred to AES 256. There has been discussions on whether AES256 extra security was worth the cost, and the result is far from obvious. At the moment, AES128 is preferred, because it provides good security, is really fast, and seems to be more resistant to timing attacks.
In the backward compatible ciphersuite, AES is preferred to 3DES. BEAST attacks on AES are mitigated in TLS 1.1 and above, and difficult to achieve in TLS 1.0. In the non-backward compatible ciphersuite, 3DES is not present.
RC4 is removed entirely. 3DES is used for backward compatibility. See discussion in #RC4_weaknesses

Mandatory discards

aNULL contains non-authenticated Diffie-Hellman key exchanges, that are subject to Man-In-The-Middle (MITM) attacks
eNULL contains null-encryption ciphers (cleartext)
EXPORT are legacy weak ciphers that were marked as exportable by US law
RC4 contains ciphers that use the deprecated ARCFOUR algorithm
DES contains ciphers that use the deprecated Data Encryption Standard
SSLv2 contains all ciphers that were defined in the old version of the SSL standard, now deprecated
MD5 contains all the ciphers that use the deprecated message digest 5 as the hashing algorithm

Extra settings

Make sure you also add these lines:

ssl_prefer_server_ciphers on;
ssl_session_cache shared:SSL:10m;

When choosing a cipher during an SSLv3 or TLSv1 handshake, normally the client’s preference is used. If this directive is enabled, the server’s preference will be used instead.

More info on sslpreferserver_ciphers.

More info on ssl_ciphers.

Forward Secrecy & Diffie Hellman Ephemeral Parameters

The concept of forward secrecy is simple: client and server negotiate a key that never hits the wire, and is destroyed at the end of the session. The RSA private from the server is used to sign a Diffie-Hellman key exchange between the client and the server. The pre-master key obtained from the Diffie-Hellman handshake is then used for encryption. Since the pre-master key is specific to a connection between a client and a server, and used only for a limited amount of time, it is called Ephemeral.

With Forward Secrecy, if an attacker gets a hold of the server’s private key, it will not be able to decrypt past communications. The private key is only used to sign the DH handshake, which does not reveal the pre-master key. Diffie-Hellman ensures that the pre-master keys never leave the client and the server, and cannot be intercepted by a MITM.

All versions of nginx as of 1.4.4 rely on OpenSSL for input parameters to Diffie-Hellman (DH). Unfortunately, this means that Ephemeral Diffie-Hellman (DHE) will use OpenSSL’s defaults, which include a 1024-bit key for the key-exchange. Since we’re using a 2048-bit certificate, DHE clients will use a weaker key-exchange than non-ephemeral DH clients.

We need generate a stronger DHE parameter:

cd /etc/ssl/certs
openssl dhparam -out dhparam.pem 4096

And then tell nginx to use it for DHE key-exchange:

ssl_dhparam /etc/ssl/certs/dhparam.pem;

Note that generating a 4096-bit key will take a long time to finish (from 30 minutes to several hours). Although it is recommended to generate a 4096-bit one, you can use a 2048-bit at the moment. However, 1024-bit key is NOT acceptable.

OCSP Stapling

When connecting to a server, clients should verify the validity of the server certificate using either a Certificate Revocation List (CRL), or an Online Certificate Status Protocol (OCSP) record. The problem with CRL is that the lists have grown huge and takes forever to download.

OCSP is much more lightweight, as only one record is retrieved at a time. But the side effect is that OCSP requests must be made to a 3rd party OCSP responder when connecting to a server, which adds latency and potential failures. In fact, the OCSP responders operated by CAs are often so unreliable that browser will fail silently if no response is received in a timely manner. This reduces security, by allowing an attacker to DoS an OCSP responder to disable the validation.

The solution is to allow the server to send its cached OCSP record during the TLS handshake, therefore bypassing the OCSP responder. This mechanism saves a roundtrip between the client and the OCSP responder, and is called OCSP Stapling.

The server will send a cached OCSP response only if the client requests it, by announcing support for the status_request TLS extension in its CLIENT HELLO.

Most servers will cache OCSP response for up to 48 hours. At regular intervals, the server will connect to the OCSP responder of the CA to retrieve a fresh OCSP record. The location of the OCSP responder is taken from the Authority Information Access field of the signed certificate.

See tutorial on enabling OCSP stapling on NGINX.

HTTP Strict Transport Security

When possible, you should enable HTTP Strict Transport Security (HSTS), which instructs browsers to communicate with your site only over HTTPS.

Add this to nginx.conf:

add_header Strict-Transport-Security "max-age=63072000; includeSubdomains; ";

HTTP Public Key Pinning Extension

You should also enable the HTTP Public Key Pinning Extension.

Public Key Pinning means that a certificate chain must include a whitelisted public key. It ensures only whitelisted Certificate Authorities (CA) can sign certificates for *.example.com, and not any CA in your browser store.

Read how to set it up here.

Conclusion

The final SSL config may look something like this:

# HTTP will be redirected to HTTPS
server {
  listen 80;
  server_name hexadix.com www.hexadix.com;
  rewrite ^ https://$server_name$request_uri permanent;
}

# HTTPS server configuration
server {
  listen       443 ssl;
  server_name hexadix.com;

  add_header Strict-Transport-Security "max-age=31536000; includeSubDomains; preload" always;

  ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
  ssl_prefer_server_ciphers On;
  ssl_session_cache shared:SSL:10m;
  ssl_ciphers 'EECDH+AESGCM:EDH+AESGCM:AES256+EECDH:AES256+EDH';
  # ssl_ciphers ECDH+AESGCM:DH+AESGCM:ECDH+AES256:DH+AES256:ECDH+AES128:DH+AES:ECDH+3DES:DH+3DES:RSA+AESGCM:RSA+AES:RSA+3DES:!aNULL:!MD5:!DSS;
  ssl_certificate /etc/letsencrypt/live/hexadix.com/fullchain.pem;
  ssl_certificate_key /etc/letsencrypt/live/hexadix.com/privkey.pem;
  ssl_dhparam /etc/ssl/certs/dhparam.pem;
}

After applying the above config lines you need to restart nginx:

# Check the config first:
/etc/init.d/nginx configtest
# Then restart:
/etc/init.d/nginx restart

Now use the SSL Labs test to see if you get a nice A. And, of course, have a safe, strong and future proof SSL configuration!

Also read the Mozilla page on the subject.

References

http://www.acunetix.com/blog/articles/nginx-server-security-hardening-configuration-1/
https://geekflare.com/nginx-webserver-security-hardening-guide/
https://nealpoole.com/blog/2011/04/setting-up-php-fastcgi-and-nginx-dont-trust-the-tutorials-check-your-configuration/
http://www.softwareprojects.com/resources/programming/t-optimizing-nginx-and-php-fpm-for-high-traffic-sites-2081.html
https://raymii.org/s/tutorials/Strong_SSL_Security_On_nginx.html
https://weakdh.org/sysadmin.html
https://www.cyberciti.biz/tips/linux-unix-bsd-nginx-webserver-security.html

Designing scalable systems – Part 1: The Basics

By Tan Nguyen | April 15, 2017 | Comments 0 Comment

1. Introduction

Nowadays, web applications are becoming more and more popular. Large websites are serving billions of users everyday, with minimal to zero percent down-time. Since you are reading this article, there’s a high chance you are already running a large system or are going to build one.

In this blog series, I’m going to share my experience on how to design web applications for scalability. This first article is not intended to go into too much detail, but instead to give you a rough idea of what should be considered when designing a scalable web application. I’m going to share the way I think when designing a scalable system, and not the solution to any specific system.

This ideas mentioned in this blog series not only apply to building websites, but also to building applications and software systems in general.

Let the fun begin! 😀

2. The Basics

What is scalability anyway?

From Wikipedia:

Scalability is the capability of a system, network, or process to handle a growing amount of work, or its potential to be enlarged to accommodate that growth.

Let’s look at an example. Our application may currently be running on a 2 CPUs with 8 GB memory instance, serving two million page views per day. What if that number of page views gets doubled by tomorrow, then ten times larger by next week, and then, a thousand times larger by the end of next month? Is our application prepared for that? What are the plans to handle the extra workloads? Are we going to upgrade our server to a larger one? Or are we going to buy more servers? Or is there anything else we are going to do?

If our application is prepared for the growth of users or page views or transactions, our application is scalable.
The plans that we prepare for our application to grow, or in other words, scale, with the growth of users or transactions, are called the scaling strategies.
Designing such a plan so that our application can scale, is designing for scalability.

Scalability, simply, is about doing what you do in a bigger way. Scaling a web application is all about allowing more people to use your application. If you can’t figure out how to improve performance while scaling out, it’s okay. And as long as you can scale to handle larger number of users it’s ok to have multiple single points of failures as well. — Royans K Tharakan

Vertical Scalability vs. Horizontal Scalability

We have two choices when it comes to scaling: Vertical and Horizontal.

Vertical Scalability – Vertical scaling means that scales by adding more power (CPU, RAM) in your existing machine. It basically means promoting an upgrade on the server. An example of this would be to add CPUs to an existing server, or expanding storage by adding hard drive on an existing RAID/SAN storage.
Horizontal Scalability – Horizontal scaling means that scales by adding more machines in your resource pool. It is the ability to increase the ability to connect multiple instances so that they function as a single logical unit. Basically, it means increasing the number of servers. Most clustering solutions, distributed file systems, load-balancers help you with horizontal scalability.

Royans Tharakan wrote about this on his blog:

If you need scalability, urgently, going vertical is probably going to be the easiest (provided you have the bank balance to go with it). In most cases, without a line of code change, you might be able to drop in your application on a super-expensive 64 CPU server from Sun or HP and storage from EMC, Hitachi or Netapp and everything will be fine. For a while at least. Unfortunately Vertical scaling, gets more and more expensive as you grow.

Horizontal scalability, on the other hand doesn’t require you to buy more and more expensive servers. It’s meant to be scaled using commodity storage and server solutions. But Horizontal scalability isn’t cheap either. The application has to be built ground up to run on multiple servers as a single application. Two interesting problems which most application in a horizontally scalable world have to worry about are “Split brain” and “hardware failure“.

While infinite horizontal linear scalability is difficult to achieve, infinite vertical scalability is impossible. If you are building capacity for a pre-determined number of users, it might be wise to investigate vertical scalability. But if you are building a web application which could be used by millions, going vertical could be an expensive mistake.

But scalability is not just about CPU (processing power). For a successful scalable web application, all layers have to scale in equally. Which includes the storage layer (Clustered file systems, s3, etc.), the database layer (partitioning, federation), application layer (memcached, scaleout, terracota, tomcat clustering, etc.), the web layer, loadbalancer, firewall, etc. For example if you don’t have a way to implement multiple load balancers to handle your future web traffic load, it doesn’t really matter how much money and effort you put into horizontal scalability of the web layer. Your traffic will be limited to only what your load balancer can push.

Choosing the right kind of scalability depends on how much you want to scale and spend. In fact if someone says there is a “one size fits all” solution, don’t believe them. And if someone starts a “scalability” discussion in the next party you attend, please do ask them what they mean by scalability first.

What do we want to achieve in a scalable system?

Scalability (duh!)

A scalable system should be prepared for a lot more workloads in the future. We can upgrade the servers to larger ones, with more CPUs and memory. We can design the system so that it can be extended by adding more servers to the existing application cluster. There should always be a scaling strategy so that the system can adapt to the upcoming extra workloads.

Robustness

A scalable system should always be responsive and function correctly, even when the number of requests grows by a factor of thousands. After all, there’s no point adding more hardware resources if the system cannot function correctly.

High availability

The system is going to server millions or billions of users, all around the world. Lots of businesses may depend on our system. Our system, therefore, cannot afford a down-time. The system should always be available, even during system upgrades. When our application goes global, there’s no place for “night deploys”.

3. Methodologies

Although there are a lot of specific ways to scale a system, they can be generalized into some methodologies below.

Methodology #1: Splitting the system

If you can’t split it, you can’t scale it. — Randy Shoup

Splitting is one of the most common practices in designing a scalable system. The idea is that, since vertical scaling the whole system is limited by hardware capability, we need to split the system into components and scale each component separately.

For example, let’s say we are designing an e-commerce system. At first, we have our web application and our database on the same server. When the traffic grows, we plans to buy a larger server. If we put our system on the most powerful server at the moment, it can handle up to one million concurrent users. And that’s it. We cannot scale to another million users because there’s no more powerful server that we can buy.

The first thing we can do is to split the system so that the web application is put on one server and the database on another.
Then, we can clone the web application to put on multiple servers, all accessing the same database server.
Then, we can split the database into multiple databases, each containing several tables from the original database. The sub-databases can now be put on separate servers. In an e-commerce system, the database can be split in to product database, order database, fulfillment process database, user and authentication database, etc.

Of course, we cannot split things that easily if we didn’t design our system for that from the beginning. For example, if our application joins data from two tables, these two tables cannot be split into different servers. This little example can show us the importance of designing a system for scalability from the early days.

HDFS, MapReduce, Kafka, ElasticSearch, and many more applications are designed to be able to split and scale by adding more servers to the application cluster.
Facebook split their databases not only by tables, but also by rows. Data of users in each region are saved on different “region databases”, and are synced periodically to other “region databases”.
Lots of large systems nowadays are split into microservices, each of which takes care of one function in the system, so that the services can be scaled separately.

As you can see, designing ways that our system can be split plays an important role in making our system scalable.

Methodology #2: Detecting and Optimizing Bottlenecks

The limit of a system is the limit of its weakest link.

To make the system handle more workloads, we need to find the system’s weakest point and make that point handle more workloads.

Let’s think of an example. In our e-commerce system, we have 5 web servers and 1 database server, each hosted on a separate physical server instance. The web servers are running at about 5% of CPU on average, while the database server is always running at 95% of CPU. The bottleneck of the system in this case is the database server.

In the above example, there’s no point adding more web servers to the system. If the current setup can handle one million concurrent users at most, it is not likely that adding more web servers can help the system to handle more users. Instead, optimizing the database server may help.

As discussed in the previous part, to optimize bottleneck at the database server, we can buy a more powerful server and relocate the database into it. If that is not an option, we can try to split the tables on the database into serveral sub-databases on different server instances, but that would include some code modifying, and may not be an option either.

Taking a closer look at the resouce usage on the database server, we find out that most of the time, the CPUs are not doing the computation, but are instead waiting for the I/O requests to complete. We monitor the disk I/O, just to find out that the disk-write is always at 100 MB/s. Now we know that the real bottleneck is the disk I/O.

To optimize the disk I/O bottleneck, we can upgrade our HDDs into SSDs, or we can add more disks to the RAID system, or try to use a SAN. As long as we can provide a better I/O bandwidth, the whole system may benefit.

On the other hand, we can reduce the I/O request by optimizing database queries and indexes. If after creating some database indexes, the disk I/O rate reduces to 10 MB/s, we may not need to upgrade the database server anymore. There were also many times in my past projects, the reason was that the database doesn’t have enough memory to cache the queries, and strange it may sound, but adding more memory could solve the disk I/O problems.

After optimizing the database, our system can handle another million users, but looking at the resources usage, we now see that the web servers are using 99% of CPU all the time, while the database only uses less than 10% of CPU. This time, the web servers become the bottleneck. We can repeat the optimizing process with the web servers. We can add more server instances, or detect and optimize the bad code block that is causing the rise in CPU usage. The point is that if the weakest link in the system can handle more requests, the whole system can handle more.

Methodology #3: Detecting and Eliminating Single Point of Failure (SPOF)

Since we mentioned bottlenecks in the previous part, I thought it’s worth discussing Single Point of Failure too. This part is more on keeping our system high available than enabling it to handle more requests. In fact, most large systems serve a lot of people and lots of businesses may depend on them, so high availability is one of the most wanted requirements.

From Wikipedia:

A single point of failure (SPOF) is a part of a system that, if it fails, will stop the entire system from working. SPOFs are undesirable in any system with a goal of high availability or reliability, be it a business practice, software application, or other industrial system.

In a traditional web application, we often have a web server reading and writing to a database. When a user open a browser and navigate to the website:

the browser sends a request to the web server,
the web server receives the request and gets data from the database or writes to it,
the web server responses to the browser with the result,
the browser renders the response to the screen.

In the above setup, if the web server breaks down (maybe due to hardware issues), the website is down. The user cannot connect to the website anymore. This web server is a Single Point of Failure, which means if it fails, the whole system fails.
The database server in this case is also a Single Point of Failure.

To make our system high available, which means the system can still function if some part of it goes down, we have to eliminate its Single Point of Failure.
The word “eliminate” doesn’t mean taking that part down, but instead, means trying to make that part no long the Single Point of Failure.

Back to our example, to eliminate the Single Point of Failure at the database, we can user the mirroring function of the database. We setup the database on 2 separate server instances, one as the master server and the other as the mirror server. If the master goes down, the mirror server will stand up to replace the master to make sure the web servers can still accessing the database.
For the web server, we setup another web server that function exactly the same as the first one. We setup a reverse proxy to load balance requests between the two web server. If a web server breaks down, the reverse proxy will detect and route all traffic to the remaining one.

We have eliminated two single point of failure in the system. However, we are introducing a new one: the reverse proxy.
In the new setup, the browser connects to the reverse proxy, the reverse proxy will then forwarding the request to the internal web server, wait for the response, then forward it back to the browser. If the reverse proxy goes down, the user still cannot access the website.

To eliminate this new single point of failure, we can setup a backup server for the reverse proxy and use a Virtual IP Address. The two reverse proxy server will continously check if the other is alive, and make sure that one of them is taking the Virtual IP Address. When the master reverse proxy goes down, the backup server will take the Virtual IP Address and take the job from the master.

Detecting and eliminating Single Point of Failure is no easy task in systems design. The example above is just a simple one to demonstrate the idea. We’ll have a whole blog on this later.

Methodology #4: Caching

I believe you’ve heard about caching and use it a lot in your projects. Let’s again look it up on Wikipedia:

In computing, a cache /ˈkæʃ/ kash, is a hardware or software component that stores data so future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation, or the duplicate of data stored elsewhere.

A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot. Cache hits are served by reading data from the cache, which is faster than recomputing a result or reading from a slower data store; thus, the more requests can be served from the cache, the faster the system performs.

If your system has a lot of data that doesn’t changes for short period of time, or if the change isn’t critical and it doesn’t hurt to serve the user with an old version of the data, caching is a good candidate that can optimize your system by ten or even a hundred times.
For example, a news website doesn’t need to change its news every second. People can read a 5-minute-ago version of the news without any critical problems.

There are many types of caching, all serve the same purpose: to make future requests for that data can be served faster. A caching solution can be a mix among the following caching strategies:

Caching in disk
After being computed for the first time, a web page’s content may be cached into a file in the server’s storage. Next time the web page is requested, the server does not have to recompute the content, but read it directly from the cached file and response to the user. Most modern web servers (Apache, Nginx, IIS) and web frameworks (Django, PHP, .NET MVC) support this type of caching.

Caching in memory
After the data is read from the disk or computed from the database, it is cached in memory so that the data can be read a lot faster in the next requests. This type of caching is often used to cache data objects, and also used by image or video hosting servers.

Caching objects
Instead of caching the whole web page content, the system can cache objects that were read from the database into memory, so that next time, it doesn’t have to query it again from the database. This type of caching is often used in large systems that data are read a lot more often than written.

Caching in database
Computations can also be cached in a database. If the application does a lot of aggregations on raw data, and the aggregations does not need to be 100% updated everytime it is requested, we can ease the stress for the database by precomputing the aggregations and cache it in a separate database table, instead of scanning the whole raw data table to do the aggregations everytime receiving a request.

Distributed caching
If we need to share cached data among web servers, we may need to apply a distributed caching service of some kind to store the cached data. For example if we cache users’ session data on web servers’ memory, and use a load balancer to round robin requests among these web servers, we may face the situation where a user login with web server 1, the session cookie is stored on web server 1’s memory. Later when that user refreshes the page, she gets routed to web server 2, which has no session data of her. The result is that the user appears to be logged out, although she just logged in 5 seconds ago. To overcome this type of situation, we need a distributed caching solution. It can be a network shared folder to keep the session file, or it can be a distributed memory caching solution like memcached or Redis.

Caching can be powerful but should be used with care. Improper use of caching may cause serious problems. Here are some examples:

Caching account balance in a credit system is not the smartest thing to do, because it can lead to the situation where the accounts are overcharged.
Another common mistake is caching web page responses on a reverse proxy, including the response header information. It may happen like this:
- For example, Alice goes to myshop.com, logs in, then browses the detail page of product A.
- Web server renders the web content for product A, and caches it as a html file on the server’s disk storage, including the response header that set Alice’s authentication cookie
- Meanwhile, Bob also wants to browse product A.
- Web server serves Bob with the web content from the cached file, including Alice’s authentication cookie in response header
- Bob is now seeing product A, and unintentionally logged in as Alice.
- Bob can now see Alice’s order history. If Bob buys something on the website, the system may record that Alice buys it. Later, customer service agent calls Alice to confirm the order but Alice doesn’t understand what happened

The second example may sound stupid, but it did happen in one of my past projects. The reverse proxy application at that time somehow cached some urls that it was not configured to cache, leading to the situation described above. Turning off the proxy’s “kernel caching mode”, without modifying any url configuration, made the problem disappear.

There’s a lot more about caching, but that would be out of the scope of this blog. We’ll have another blog on this topic.

Methodology #5: Indexing

Indexing is a way of storing data in a suitable structure, so that data retrieval can be fast and accurate.

Database index

Sometimes, caching is not applicable due to the nature of the business, like in a banking system, where transactional data must always be consistent.

Database queries can be optimized by adding database index to the table. Database index can improve query performance by a factor of thousands to millions times. In fact, the query running time can get from O(n) in a full table scan, down to O(logn) in a indexed table, where n is the number of records in the table. Let’s say we have a table of 10.000.000.000 (ten billion) records, and the table is well-indexed, the query will need to do only 10 compares to find the matching row. Behind the scene, the indexed data is stored in a b-tree data structure, but that’s out of the scope of this blog.

Database indexing not only speed up the query running time, but also reduces the disk I/O needed to return the matching records. In OLTP databases, faster queries lead to less locking time on the table.

I’ve seen many times in my past projects, where the insert/update to the database took too long to complete, but the real reason was not the insert/update itself. The real cause was another select query, which took too long to complete and locked the whole table during its execution, making the insert/update queue up in line. Adding a index to optimize the select query, the problem is gone. The insert/update can complete and return immediately as usual.

If you want to learn more about database index, try reading use-the-index-luke.

Search index

When it comes to searching, there’s another hero in town: search index.

Most databases support full-text index out of the box, but it’s hard to configure and does not scale very well. Search queries can be very complicated, like searching for a product with a keyword that should appear in its title or content, and the product must be in sports and clothes category, with a discount percent at least 50 percent. The database can be used to fulfill the search, but the performance would be terrible.

At the moment, Solr and ElasticSearch are the most popular search engines that are being used widely. They are fast, horizontally scalable, good at full-text search and handling complicated queries.

Using a search engine in our system can yield several benefits:

Search engines will take care of what it is best at: searching, while leaving the database to do what the database is best at: storing transactional data.
Most search engines are design to scale very well horizontally. Therefore, by using a search engine, our system’s search function are already prepared for scaling. For example, ElasticSearch can be deployed in cluster of multiple nodes. When we need extra performance from the cluster, we can add more nodes to the cluster, or we can just increase the number of replicas of the index, all of which can be done online without shutting down the service.

Increasing number of replicas will enable more nodes to store the same piece of data, and hence ElasticSearch can load balance the query to get the result from more nodes, which leads to the increase in query performance.

Think of what would happen if we do the search directly from the database. The scaling would be a disaster.

With all the benefits mentioned above, using a search engine will give you some extra work to do, like to index or synchronize the data from the database to the search engine. But if your system is going to scale, the benefits are going to worth the extra effort.

Methodology #6: Classifying and Prioritizing Data

Not all data are created equal.

When our system grows too large and too complicated, we may not be able to work out a way to scale all our data together. Facebook has more than a billion users, each user has hundreds to thousand of friends, each friend has several status updates and activities every day. If everytime a user create a status, we have to notify all of the friends about that new activity in one database transaction, no system would be above to handle the workload, and even if it can, the user would have to wait very long before his or her status post completes, just because he or she has more than a thousand friends to update along the way.

Real-time vs. Near real-time vs. Offline

During a Facebook developer event, talking about how Facebook partitioned the users to multiple databases, each database containing a subset of users, and synchronize the “activity feeds” among databases, the speaker was asked: “How did Facebook keep the data consitent among databases?”. At that time, the answer blew my mind: “Fortunately, we don’t have to be consistent at all”.

In Facebook’s case, of course it’s good to notify the friends about a user’s new status right away, but it at the same time doesn’t hurt if the notification is 5 minutes later or even an hour later, not to mention half of those friends may not even be online by that time.
In an e-commerce system, most of the reports aren’t necessary to be real-time. Some of the reports can even be updated weekly or monthly (yes, I’m talking about those weekly and monthly sales performance reports :D)

Before designing a solution to scale the system, we should first classify each data into one of these types: real-time, near real-time, and offline.

Real-time: These data need to always be consistent. In other words, everytime the data of this type is read, it must be the latest and the only version of the data. Data like bank account balance, warehouse stock quantity, GPS location in navigating system, chat messages should be in this category.
Near real-time: These data can afford to be a little bit late, for example five minutes or even one hour. For example, in most of the case, emails can be a little bit late without hurting anyone. Activity feed in the above section, can also be classified as near real-time. Of course, it’s always better if these data can be real-time, but if the cost to be real-time is too high, these data can fall back to be near real-time with mininal to zero negative impact. In fact, most people don’t care or even notice a delay in the activity notification.
Offline: These data do not need to be updated regularly. They can be updated in batches at the end of the day or at the end of a week, when the system is not heavily used. For example, in an e-commerce system, reconciliation reports can be exported once a day at night, when the traffic to the website is not that critical and the system resources are free.

Know the priority of our data, we can decide how each data should be stored and should be scaled. Real-time data should be stored in a transactional database, while near real-time data can put in a queue waiting to be processed with a small delay. Offline data can be put in a replicated database, which is synchronized once a day during low traffic hours. The system then can use significantly less resources while still be able to fulfill the business requirements.

Read-heavy vs. Write-heavy

Beside the above mentioned classification, we should also take into consideration whether our data is read-heavy or write-heavy

Read-heavy: These data are read a lot more frequently than written or updated. For example, articles in a newspaper or a blog are rarely updated, but are read very frequently. For these type of data, we can use caching or replication to enable the system to read more in less time.
Write-heavy: These data are written a lot more frequently than read. For example, access logs in a system or bank transactions. For these type of data, caching or replication may not be helpful. In fact, caching or replication may even hurt the system performance, since the system have to do more works every time it has to write something, while it can rarely read a data from cache. The data may have been changed a hundred times before it is read from cache one time.

Other classifications

Above are just two ways of classify and prioritize data before desiging an appropriate scaling stategy for each type of data. In practice, we can think of more ways to classify the data. The point is, we should classify the data based on business needs and select an appropriate strategy so that the system can use less resources and can still meet the business requirements.

4. Where to go from here?

The above topics are just some of the most basic topics on designing a scalable system. There’s a lot of things that I haven’t learned or haven’t even known of. I’m going to list some topics that can be helpful when designing a scaling strategy. Hope some of them can be helpful to you. The more we know, the higher the chance we can find a good scaling solution for our system. The below topics are not listed in any intended order.

CAP theorem
How to become horizontally scalable in every layer
Vertical partitioning vs. horizontal partitioning
Read-heavy vs. write heavy
Clustering: partitioning vs. replication
Real-time vs. near real-time vs offline
How to make web server horizontally scalable using reverse proxy
How to make reverse proxy horizontally scalable
How to make database horizontally scalable
- Shared nothing database cluster vs. shared storage database cluster
- MySQL NDB vs. Percona vs. Oracle Database Cluster vs. SQL Server Cluster
Using cloud database service vs. scaling self-hosted database
Scaling system on cloud hosted environment vs. self hosted environment
DNS round robin
Caching
- Disk caching
- Local memory caching
- Distributed memory caching
  - memcached
  - Redis
Hardware scaling
- RAID storage
- SAN storage
- Fiber network interface
Network capacity consideration
- Local cache vs. network distributed cache
- local pre-compute to reduce network traffic (e.g. MapReduce Combiner)
Storage scaling
- Increasing reading bandwidth (RAID, replication, memory caching, distributed network storage, hdfs, etc.)
- Increasing writing bandwidth (RAID, partitioning, memory write buffer, distributed network storage, hdfs, etc.)
- Scaling storage capacity (RAID, distributed network storage, data compression, etc.)
Database/datawarehouse optimization
- Database index
- Column store index vs. row store index
Search optimization (ElasticSearch, Solr)
Peak-time preparation strategies (cloud vs. self-hosting, AWS Auto Scaling, Google Cloud Autoscaler
Cost optimization
- Google Cloud Preemptible, AWS Spot Instance
- Free CDN: CloudFlare, Incapsula
Resources monitoring, debugging, troubleshooting
Automate everything
Load test vs. stress test

Conclusion

When it comes to scaling, there’s no magical solution that can tackle all problems on all systems. Knowing the basics and the methodologies, we can do the analysis and find the most suitable solution, and prioritize what can be done first that will results in the biggest impact.

On the other hand, there’s no final destination in optimizing system’s scalability. Whenever we sense that our system is reaching its limit, we should work out a better solution to scale it up before it’s too late. However, if there’s no sign that the system will get overloaded anytime soon, I believe you’ll always have better works to do than further optmizing the system. If there’s only 10 billion people on earth, there’s no point designing a system for 100 billion concurrent users.

This article can no way cover everything in designing scalable systems. But I hope some of it might be helpful to you. What’s the most interesting experience you’ve got when scaling your system? Share with us in the comment! 😀

Sorry for the long post!