Design Hotel Reservation

Design a hotel reservation system. To make it simple, we assume that the hotel has only one building and the building has only one floor. Design your objects so that they work better with a non-sql database, say a document-oriented database.

The reservation system needs at least two another class. The first one is the Room class, which is identified by the room number and have several methods such as book() or unbook().

The second one is the Customer class. This class contains the information of a customer who has made a reservation.

I also use two maps to store all rooms and customers. The reason to use map is that it is easy for retrieval: I can use the name and room number to find the customer and room I want.

Two public methods: makeReservation and cancelReservation.

makeReservation() will create a Customer object, find the next available room, and assign that to the customer, so when the customer checks in, he/she can easily find the room. If there is no available room, then no reservation can be made.

cancelReservation() will remove the Customer object c out of the customers map and make the room available.

There are couple private helper methods that I don't want to go detail.

public class ReservationSystem{
 final Map rooms;
 Map customers;
 
 public ReservationSystem(List builtRoom){
  rooms = new HashMap ();
  //when the hotel is built, all the rooms are added into the system
  rooms.add(builtRoom);
  customers = new HashMap ();
 }
 
 public boolean makeReservation(String name, String id, String information){
  int room = findNextAvailableRoom();
  if(room == -1){
   System.out.println("No available room!");
   return false;
  }
  Customer c = new Customer(name, id, information, room);
  rooms.get(room).book();
  customers.put(name, c);
  return true;
 }
 
 public boolean cancelReservation(String name){
  Customer c = findCustomer(name);
  if(c == null){
   System.out.println("No reservation found!");
   return false;
  }
  customers.remove(name);
  makeAvailable(c.roomBooked);
  return true;
 }
 
 private Customer findCustomer(String name){
  if(!customers.containsKey(name))
   return null;
  return customers.get(name);
 }
 
 private void makeAvailable(int roomNumber){
  rooms.get(roomNumber).unbook();
 }
 private int findNextAvailableRoom(){
  for(Room r : rooms.values()){
   if(!r.isBooked())
    return r.roomNumber;
  }
  return -1;
 }
 
 
 class Room{
  final int roomNumber;
  private boolean available;
  
  public Room(int rN){
   roomNumber = rN;
   available = true;
  }
  
  public void book(){
   available = false;
  }
  void unbook(){
   available = true;
  }
  public boolean isBooked(){
   return !available;
  }
 }
 
 class Customer{
  String name;
  String id;
  String information;
  int roomBooked;
  
  public Customer(String name, String id, String information, int roomNumber){
   this.name = name;
   this.id = id;
   this.information = information;
   roomBooked = roomNumber;
  }
 }

Swap sequence

You are given two arrays - A & B. The length of the arrays is the same - N. The values in the arrays are integers from 0 to N - 1 in random order and no number is repeated. You need to list a sequence of two-element swaps required to reorder the array A into the order of the array B. Additionally, at each step of the sequence you are allowed to swap two elements only if one of them is 0.

The idea is very simple.
1. Find the index of element 0 in A, then in B we get an corresponding element.
2. If it is not zero, find the index of that element in A, swap them.
3. If it is zero, then find the index of first element in A that is not equal to the corresponding element in B, swap it with 0 in A. Repeat 2.

public class SwapSequence {
 public static void printSequence(int[] A, int[]B){
  int indexZ  = findIndex(A, 0);
  if(B[indexZ] == 0){
   indexZ = getIndex(A, B, indexZ);
   if(indexZ == -1)
    return;
  }
  while(B[indexZ] != 0){
   int index = findIndex(A, B[indexZ]);
   System.out.println(A[indexZ] + " " + A[index]);
   swap(A, indexZ, index);
   indexZ = B[index] == 0 ? getIndex(A, B, index) : index;
   if(indexZ == -1)
    return;
  }
  
 }
 private static int getIndex(int[] A, int[] B, int indexZ){
  for(int i = 0; i < A.length; i++){
   System.out.println(A[i] + " " + B[i]);
   if(A[i] != B[i]){
    swap(A, i, indexZ);
    return i;
   }
  }
  return -1;
 }
 private static void swap(int[] array, int i, int j){
  int tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
 }
 private static int findIndex(int[] array, int element){
  for(int i = 0; i < array.length; i++){
   if(array[i] == element)
    return i;
  }
  return -1;
 }

 public static void main(String[] args) {
  int[] A = {0, 4, 8, 7, 1, 2, 5, 3, 6};
  int[] B = {1, 7, 6, 5, 8, 4 ,2, 3 ,0};
  printSequence(A, B);
  System.out.println(Arrays.toString(A));

 }

}

Read bytes

Given an API ReadFromDisk() which returns a block of 256 bytes from disk. Implement the API Read(SizeInBytes) which reads SizeInBytes bytes from the disk by calling only ReadFromDisk. Notice that every call to ReadFromDisk() will read the next 256 bytes from disk.

Update 2015 - 03 - 30
I realize that I understood the ReadN problem wrong, the char[] buff is the output array. Here is the updated version. I updated the ReadN too.

public int read2(byte[] buff, int sizeInBytes){
  int index = 0, next = 0;
  //assume return -1 if reach the end of the file
  byte[] tmp = new byte[256];
  while(index < sizeInBytes && (next = readFromDisk(tmp))!= -1)
   for(int i = 0; i< next && index < sizeInBytes; buff[index++] = tmp[i++]);
  return index;
 }
 public int readFromDisk(byte[] buff){
  return 256;
 }

This is similar to the LeetCode's ReadN question. I hijacked the code from java src (see here if you want the original).

public void read(int sizeInBytes) throws IOException{
  //readFromDisk() will read 256 bytes and put into 
  //the byte array, so we only need the size / 256
  int size = sizeInBytes / 256;
  byte[] b = new byte[size];
  int c = readFromDisk();
  //assume readFromDisk() will return -1 if the 
  //length is less than 256
  if(c == -1)
   return;
  b[0] = (byte)c;
  int i = 1;
  for(; i < size; i++){
   c = readFromDisk();
   //reach the end of the file
   if(c == -1)
    break;
   b[i] = (byte)c;
  }
 }
 public int readFromDisk(){
  return 255;
 }

Snakes and Ladders

Design an optimized algorithm to solve snakes and ladders with the least amount of roles possible under the assumption that you get whatever role you want when you role the dice.

I didn't even know about the game at first. As usual, if the question asks about "minimum" something, there is highly chance that it is a DP.

Just to describe the game for short:

It is a common board game, where you roll the dice and proceed the amount you get;
If you hit the lower side of the ladder, you are lucky, you move up to the upper side of the ladder;
If you face a snake (upper side of the snake), congratulations, go back to the tail (lower side) of the snake;
If you are the first one to proceed to the destination, you win.

If you are so interested in playing the game, consult Wikipedia.

Ok, back to the problem. Create a 1D array of length n * n, which is the minimum roles needed to proceed to that spot. If index < 6, then as long as it's not the upper side of the snake, it takes minimum 1 step. If index > 6, then it takes minimum from index - 6 to index - 1 plus 1 step, assuming normal condition. If it is the upper side of the ladder, it equals the step needed to go to the lower side of the ladder. If it is the upper side of a snake, since every time you hit this square, you always have to return, it takes infinity to go to the destination.

I use a struct to store the information on the board. The board of the test case can be viewed as this:

import java.util.*;
public class SnakesNLadders {
 public static int roles(Struct[][] board){
  if(board == null || board.length == 0 || board[0].length == 0 || board.length != board[0].length)
   return 0;
  int n = board.length;
  int[] roles = new int[n * n];
  for(int i = 0; i < n * n; i++){
   int x = i / n;
   int y = (x % 2 != 0) ? (n - 1 - i % n) : i % n;
   if(i < 6){
    roles[i] = board[x][y].s.equals("SU") ? Integer.MAX_VALUE / 2 : 1;
   }
   else{
    roles[i] = Integer.MAX_VALUE;
    for(int j = i - 6; j < i; j++)
     roles[i] = Math.min(roles[i], roles[j] + 1);
    if(board[x][y].s.equals("LU"))
     //in case the lower end of the ladder is the upper end of the
     //snake
     roles[i] = Math.min(ladder(board, x, y, roles),  roles[i]);
    else if(board[x][y].s.equals("SU"))
     roles[i] = Integer.MAX_VALUE / 2;
   }
  }
  
  return roles[n * n - 1];
 }
 private static int ladder(Struct[][] board, int x, int y, int[] roles){
  int n = board.length;
  int xc = board[x][y].x;
  return xc % 2 != 0 ? roles[xc * n + (n - 1 - board[x][y].y)]
     : roles[xc * n + board[x][y].y];
 }
 /**
  * consists the string which represents the status of the square:
  * "SU": snake upper side
  * "SL": snake lower side
  * "LU": ladder upper side
  * "LL": ladder lower side
  * as well as the coordinates of its corresponding end
  * e.g., "SU", 1, 1 indicates the lower side of the snake is at x = 1, y = 1 
  * @author shirleyyoung
  *
  */
 private static class Struct{
  String s;
  //the coordinate of the corresponding square
  int x;
  int y;
  public Struct(String s, int x, int y){
   this.s = s;
   this.x = x;
   this.y = y;
  }
 }
 public static void main(String[] args) {
  Struct[][] board = new Struct[4][4];
  for(int i = 0; i < 4; i++)
   //indicate nothing in the square
   Arrays.fill(board[i], new Struct("", -1, -1));
  board[0][1] = new Struct("SL", 1, 2);
  board[1][2] = new Struct("SU", 0, 1);
  board[0][3] = new Struct("LL", 2, 3);
  board[2][3] = new Struct("LU", 0, 3);
  board[1][1] = new Struct("SL", 3, 2);
  board[3][2] = new Struct("SU", 1, 1);
  board[1][0] = new Struct("LL", 2, 0);
  board[2][0] = new Struct("LU", 1, 0);
  System.out.println(roles(board));
 }
}

Markov String Generator

Update 2015 - 03 - 31:

Ok, I optimized to code and removed those cumbersome extra space. Now my code reads the strings from the file and generate the table directly.

public class StringGenerator2 {
 private class Frequency{
  String s;//hashcode of the string
  int count;//occurrence
  public Frequency(String s, int c){
   this.s = s;
   this.count = c;
  }
 }
 Map> table;
 Random r;
 public StringGenerator2(String fileName) throws FileNotFoundException, IOException{
  table = new HashMap> ();
  r = new Random();
  generateTable(fileName);
  assert(isUniqueList());
 }
 public void generateTable(String fileName) throws FileNotFoundException, IOException{
  BufferedReader reader = new BufferedReader(new FileReader(fileName));
  String line;
  String last = null;
  while((line = reader.readLine()) != null){
   String[] row = line.split(" ");
   for(String s : row){
    String puntua = null;
    if(!Character.isLetter(s.charAt(s.length() - 1))){
     puntua = s.substring(s.length() - 1);
     s = s.substring(0, s.length() - 1);
    }
    if(!table.containsKey(s))
     table.put(s, new ArrayList ());
    if(last != null)
     add(table.get(last), s);
    if(puntua != null)
     add(table.get(s), puntua);
    last = s;
   }
  }
  reader.close();
  mapFrequency();
 }
 private void add(List next, String s){
  int index = -1;
  for(int i = 0; i < next.size(); i++){
   if(next.get(i).s.equals(s)){
    index = i;
    break;
   }
  }
  if(index != -1)
   next.get(index).count++;
  else
   next.add(new Frequency(s, 1));
 }
 private void mapFrequency(){
  for(Entry> e : table.entrySet()){
   List next = e.getValue();
   for(int i = 1; i < next.size(); i++){
    next.get(i).count += next.get(i - 1).count;
   }
  }
 }
 private boolean isUniqueList(){
  Set words = new HashSet ();
  for(List next : table.values()){
   words.clear();
   for(Frequency f : next){
    if(!words.add(f.s))
     return false;
   }
  }
  return true;
 }
 public void generator(String outputName, int length) throws IOException{
  if(table.size() == 0){
   System.out.println("No training set found!");
   return;
  }
  FileWriter writer = new FileWriter(outputName);
  int index = 0;
  String last = null;
  int countWord = 0;//number of words in one line
  while(index < length){
   String s = null;
   if(last == null || !table.containsKey(last)){
    //generate a random string from the key set
    Object[] keys = table.keySet().toArray();
    s = (String) keys[r.nextInt(keys.length)];
   } else
    s = getNext(table.get(last));
   writer.append(s).append(" ");
   countWord++;
   if(countWord == 15){
    writer.append("\n");
    countWord = 0;
   }
   last = s;
   index++;
  }
  writer.append(".\n");
  writer.flush();
  writer.close();
 }
 private String getNext(List next){
  int size = next.size();
  int nextIndex = r.nextInt(next.get(size - 1).count) + 1;
  for(Frequency f : next){
   if(nextIndex <= f.count)
    return f.s;
  }
  return next.get(r.nextInt(size)).s;
 }
  
}

Too much fun for this morning. I saw this problem posted on Career Cup yesterday. I couldn't understand what the problem really meant (see here), especially after I took a look at Wikipedia's couldn't-be-more-confusing explanation on Markov chain. But Google never let me down. I found this blog, which explained it in a clearer way. In short, using Markov chain to generate a new String is like using Bayesian  to predict when the first snow in next year will happen: based on the probability of when the first snow in last couple years happened.

In short, given a training set of strings, we create a table of the probability of all the next strings after a given string. Then when we need to generate a new string, we randomly select the first string from our training set, then pick the next string based on the probability of each "next" string in the table given the last generated string.

To get the next string based on the pre-calculated probability, I used this method. Basically when you get the probability distribution. You generate a random number, and based on the corresponding range in the PDF, you select the string.

I have to say that my implementation is not a good one. First, I used a list to store all strings into the memory, it definitely will cause a problem if there are too many strings. However, I don't know how to check if the current string is already in the table if I don't put everything into the memory.

Next, I calculate the frequency, to do that, I used another map, which is used to count the occurrence of each "next" string, then use two arrays to sum up, and finally use a list of structure (string, accumulated frequency) to store all "next" strings, given one string key in the table. See how much extra space I have used, this is definitely not good.

Moreover, when we hit a punctuation, I added the punctuation into the "next" list but didn't include it as a key.

To actually generate the string is easy, as I mentioned before, just keep randomly generate the next string in the "next" string list based on the frequency.

There are lots of ways to optimize this implementation. But I think this is enough for interview/learning purpose.

package markovChain;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
import java.util.Map.Entry;
public class StringGenerator {
 List trainingSet;
 String file;
 public StringGenerator(String file) throws FileNotFoundException, IOException{
  this.file = file;
  trainingSet = new ArrayList ();
  read();
 }
 /**
  * read training set and buffered it into a list
  * @throws FileNotFoundException
  * @throws IOException
  */
 public void read() throws FileNotFoundException, IOException{
  BufferedReader reader = new BufferedReader(new FileReader(file));
  String line;
  while((line = reader.readLine()) != null){
   String[] row = line.split(" ");
   for(String s : row)
    trainingSet.add(s);
  }
  reader.close();  
 }
 /**
  * Generate frequency table
  * @param output
  * @param length
  * @throws IOException
  */
 private Map> generateTable(){
  Map> frequencyTable = new HashMap> ();
  frequencyTable.put(trainingSet.get(0), new ArrayList ());
  for(int i = 1; i < trainingSet.size(); i++){
   String s = trainingSet.get(i);
   String p = null;
   if(!Character.isLetter(s.charAt(s.length() - 1))){
    p = s.substring(s.length() - 1, s.length());
    s = s.substring(0, s.length() - 1);
   }
   if(!frequencyTable.containsKey(s)){
    frequencyTable.put(s, new ArrayList ());
    if(p != null)
     frequencyTable.get(s).add(p);
   }
   String last = trainingSet.get(i - 1);
   if(!Character.isLetter(last.charAt(last.length() - 1)))
    last = last.substring(0, last.length() - 1);
   frequencyTable.get(last).add(s); 
  }
  Map> nextFrequency = getFrequency(frequencyTable);
  return nextFrequency;
 }
 private Map> getFrequency(Map> frequencyTable){
  Map> countFre = new HashMap>();
  for(Entry> e : frequencyTable.entrySet()){
   String key = e.getKey();
   List next = e.getValue();
   Map f = new HashMap();
   for(String s : next){
    if(!f.containsKey(s))
     f.put(s, 1);
    else
     f.put(s, f.get(s) + 1);
   }
   List nextFrequency = mapFrequency(f);
   countFre.put(key, nextFrequency); 
  }
  return countFre;
 }
 private List mapFrequency(Map f){
  String[] array = new String[f.size()];
  int[] c = new int[f.size()];
  int index = 0;
  for(Entry ec : f.entrySet()){
   array[index] = ec.getKey();
   c[index] = ec.getValue();
   index++;
  }
  for(int i = 1; i < c.length; i++){
   c[i] += c[i - 1];
  }
  List rst = new ArrayList ();
  for(int i = 0; i < c.length; i++)
   rst.add(new Frequency(array[i], c[i]));
  return rst;
 }
 
 
 /**
  * generate the string
  * @param output
  * @param length
  * @throws IOException
  */
 public void Generator(String output, int length) throws IOException{
  if(trainingSet.size() == 0){
   System.out.println("No training set found!");
   return;
  }
  Map> nextFrequency = generateTable();
  Random r = new Random();
  FileWriter writer = new FileWriter(output);
  int i = 0;
  String last = null;
  int countWord = 0;
  while(i < length){
   String s = null;
   if(last == null || !nextFrequency.containsKey(last))
    s = trainingSet.get(r.nextInt(trainingSet.size()));
   else
    s = getNext(nextFrequency.get(last));
   writer.append(s).append(" ");
   countWord++;
   if(countWord == 15){
    writer.append("\n");
    countWord = 0;
   }
   last = s;
   i++;
  }
  writer.append(".\n");
  writer.flush();
  writer.close();
 }
 private String getNext(List nextFre){
  int size = nextFre.size();
  Random r = new Random();
  int next = r.nextInt(nextFre.get(size - 1).count) + 1;
  for(Frequency f : nextFre){
   if(next <= f.count)
    return f.s;
  }
  return nextFre.get(r.nextInt(size)).s;
 }
 /**
  * the structure that contains the string and its count
  * @author shirleyyoung
  *
  */
 private class Frequency{
  String s;
  int count;
  public Frequency(String s, int c){
   this.s = s;
   count = c;
  }
 } 
}

Test
In order to show my averseness to the research that I am working on. I decide to use some paragraphs from the papers I am reading as the test case.

"The dynamics of flexible polymers in shear is of great practical interest because this type of flow occurs whenever a fluid flows past a surface. 

Macroscopic, non-Newtonian rheological properties of polymer solutions, such

as flow-dependent viscosities and normal

stresses, result from microscopic stresses that

arise when polymeric molecules are stretched

and affect the solvent motion. Thus, much

effort has been directed at predicting the molecular

dynamics of polymers in shear flows. However, it has been difficult to rigorously

test these predictions because the dynamics

of a polymer molecule in shear have

not been observed directly. Experimental efforts

have mainly focused on measuring bulk

rheological properties or on measuring the

scattering of light or neutrons by polymer

solutions. Here we describe how single-molecule imaging techniques can be

used to study the configurations of polymers

in shear flow so that the detailed molecular predictions of theories can be tested.

In short, Shirley doesn't care about how polymer tumbles in shear flow!

Polymer dynamics are of central importance in materials science,

mechanical engineering, biology and medicine. The dynamics of

macromolecular solutions and melts in shear flow are typically

studied using bulk experimental methods such as light and

neutron scattering and birefringence. But the effect of shear

on the conformation and dynamics of individual polymers is

still not well understood. Here we describe observations of the

real-time dynamics of individual, flexible polymers fluorescently

labelled DNA molecules under a shear flow. The sheared

polymers exhibit many types of extended conformation with an

overall orientation ranging from parallel to perpendicular with

respect to the flow direction. For shear rates much smaller than

the inverse of the relaxation time of the molecule, the relative

populations of these two main types of conformation are

controlled by the rate of the shear flow. These results question

the adequacy of assumptions made in standard models of polymer

dynamics."

Here is the 300 strings generated from the input.

"mainly focused on measuring bulk rheological properties or on measuring the rate of extended conformation 

and dynamics of individual flexible polymers in shear is still not been difficult to rigorously 

test these predictions of shear on measuring bulk rheological properties or on measuring bulk rheological 

properties of assumptions made in shear is still not been difficult to rigorously test these 

two main types of polymer solutions Here we describe how polymer solutions , the detailed 

molecular dynamics of the molecular predictions of light and normal stresses result from microscopic stresses 

that the shear on measuring the molecular predictions of polymers exhibit many types of individual 

flexible polymers fluorescently labelled DNA molecules are controlled by the shear is of extended conformation 

with an overall orientation ranging from microscopic stresses result from microscopic stresses that arise when 

polymeric molecules are of polymers in shear flow Polymer dynamics of flow occurs whenever a 

shear flows However , by the molecule in shear rates much effort has been observed 

directly Experimental efforts have mainly focused on the effect of conformation with an overall orientation 

ranging from microscopic stresses that arise when polymeric molecules under a surface . flexible polymers 

exhibit many types of light and normal stresses , rheological properties of the adequacy of 

a shear flow so that the detailed molecular dynamics of conformation are of polymers in 

shear flow occurs whenever a surface . under a shear flow Polymer dynamics of assumptions 

made in shear flow are controlled by the dynamics of extended conformation and neutron scattering 

and affect the molecule the effect of great practical interest because the scattering and affect 

the scattering of polymers is still not been difficult to study the solvent motion Thus 

, much smaller than the inverse of shear flow Polymer dynamics of conformation and medicine."

Well, not that bad. 

Print frequency

Given an unsorted array of natural numbers. Where numbers repeat in array. Out put numbers in the order of frequency. Where number of out put is passed as parameter.
For Ex:
Array -> [0, 0, 100, 3, 5, 4, 6, 4, 2, 100, 2, 100]
n -> 2
Out put -> [100, 0] or [100, 2]
Since 100 is repeated 3 times and 0, 2 is repeated 2 times, out put up to 2 most frequent elements, program should out put either 100, 0 or 100, 2

It doesn't look like there are ways (not on top of my mind) that we can avoid extra space. The PriorityQueue I created is fixed to the size of n, and it is a min heap. So each time I poll out the head if it is smaller than the one that is supposed to be put in, and add the new one into the queue. In the end, iterate through the queue and print out all elements in it.

public static void frequencyPrinter(int[] num, int n){
  if(num == null || num.length == 0)
   return;
  Map count = new HashMap ();
  for(int i : num){
   if(!count.containsKey(i))
    count.put(i, 1);
   else
    count.put(i, count.get(i) + 1);
  }
  PriorityQueue> pq = new PriorityQueue> (n, new countComparator());
  for(Entry e : count.entrySet()){
   if(pq.size() < n)
    pq.add(e);
   else{
    if(e.getValue() > pq.peek().getValue()){
     pq.poll();
     pq.offer(e);
    }
   }
  }
  Iterator> it = pq.iterator();
  while(it.hasNext()){
   System.out.println(it.next().toString());
  }
 }
 private static class countComparator implements Comparator>{
  public int compare(Entry a, Entry b){
   return a.getValue() - b.getValue();
  }
 }

Common sense (?) about YouTube

The Web Servers

Source: https://www.youtube.com/watch?v=w5WVu624fY8

NetScaler
load balances: mark down/up machines,
cache static contents: Apache is not very good at handling very large static contents.

mod_fastcgi: request look dynamic, follow certain rules

Run linux
can usually scale by adding machines
Python is fast enough
Web code speed is usually not the bottleneck
More often spending on time waiting on databases, caches, RPC (remote procedure call) calls.
Development code is important

<<100 ms page service times
dynamic Python -> C compiler, use psyco to speed up Python
selectively write encryptions, such as C extensions
pre-generated cached HTML

Serving Video
Issues: bandwidth, hardware, limited power in a data center, hardware doesn't consume too much power
Each video is hosted by "mini-cluster"
mini-cluster: small number machines that serve exact the same set of videos, few redundancy;
couple machines in one cluster:
1. scalability: more disks serving each content
2. head room: one machine goes down, other machines can take off the slack
3. online backups of everything

from Apache -> lighttpd
single process -> multi-process

Serving Video
Put the most popular content on to the CDNs
The moderately played and least played videos go to YouTube servers.
The traffic profile that goes to YouTube servers: some videos have 10 - 20 views / day, but if aggregate all those videos, it's still a lot. Rate control becomes more important, cache becomes more important. And want to tune the amount memory of each system so that it won't be too small. But not too large, because otherwise when you expand the number of machines, it will cost too much money without much benefit.

Keep it simple
simple network path: not too many network devices are in the path between the client and video servers
commodity hardware
simple common tools
Bundles of Linux, build layers on top of them, can be modified if needed
OS page cache size is critical
Handle random seeks(SATA tweaks, etc. )

Serving Thumbnails
Thumbnails images that correspond to each video are around 100 * 90 pixels, so ~ 5kb each, A lot of them, each video has multiple thumbnails. There are 4 times number of thumbnails than there are videos. Videos are across thousands of machines, but thumbnails are concentrated on small number of machines. Need to deal with lots of small objects: In & Out (INO) cache, direct entry caches, page caches, all over OS level
High request / second: any given web page, when search a key word, there are lots thumbnails, but there is only one video.
Start with Apache: unified pool (same machine that is serving the web traffic is also serving static images(thumbnails)) -> separate pool, high load, low performance
-> squid(reverse proxy): far more efficient with CPU, load increases, performance decreases over time
-> lighttpd (modified)

Source:https://www.youtube.com/watch?v=w5WVu624fY8

Main thread: epoll reading content that is already in memory

Assign disk reads to different Worker Thread
As long as keep all the fast stuff on the main thread, serving lots of request per second, all the slow stuff can come a little bit later

-> BTFE

Google's BTFE

Based on Bigtable(Google distributed data store)

avoids small file problem

set up new machines becomes faster and easier

fast, fault-tolerant

various forms of caching: cache multiple levels so that the latency between server and user is not so much

Databases

MySQL

only store metadata (users, video description titles tags, etc)

In the beginning: one main DB and one backup

main database is swapping: it is not using more memory than the system has: The Linux 2.4 kernels, it thinks the page caches is more important than applications, if the page caches is 1.6 gb, the application is 3.5 gb, if there is only 4 gb of physical memory, rather than reduce the size of page cache, it instead swapped out mySQL, but mySQL needs to be on memory, so it goes back and forth, so swapping in and swapping out is very frequently. 

DB Optimizations

Query optimizations

Batch jobs whenever they are too expensive to do

memcache: instead of going to database all the time, use memcache D, hashtable on TCP socket, allows you to get and set data based on some string based key; using memory is better than using the disk

App server caching: database caches, database machine OS caches, memcache, memory space of the app server process: access the data very often (hundreds of times / second), sometimes precalculate the data, and store the data in memory

Replication

Spread reload across other databases when the traffic grows, which are replaying the transactions happening on the master databases. All the writes go to the master database, they spread to single replica that is attached to that database, asynchronized process. 

Source: https://www.youtube.com/watch?v=w5WVu624fY8

All the writes are in multiple places, in some situations that writes are exhausting the databases;

If there are too many replicas, management issues;

Replica Lag (downside)

Replication is asynchronous

If there are multiple machines which have different CPU speed, slightly different lags on each machine;

On the Master database, updates comes from multiple threads. Each thread is executing a single update. 

On the replica data base, MySQL serialize everything onto one thread, it can be bottleneck.Update 3 cannot execute until update 2 is finished assuming update 2 is a long update. 

Source: https://www.youtube.com/watch?v=w5WVu624fY8

Unhealthy Replication Thread

Consider there are 5 updates, 3 are results of pages that are not in memory, so result in cache misses. Cache misses stalls the replication thread. At certain point the replica cannot keep up with the master database. The master database is using all the CPUs and all the disks, but the replica can only use 1 CPU and 1 disk, causing a reduction in replication speed. 

DB updates involve:

1. reading the affected DB pages

2. Applying the changes

MySQL use 1 thread to buffer or the sql from the master database, and another one executing the sql. 

The solution: since replication is behind, the cache primer thread can see the not-yet-replayed SQL queries and pre-fetch the affected rows. 

Replica Pools

Since it cannot deal with all database load, prioritized video watching above everything else. Split replica databases into two pools:

Source: https://www.youtube.com/watch?v=w5WVu624fY8

Database Partitions

A gigantic database: split it to different pieces, each is independent

partition by user

spread writes AND reads

much better cache locality -> less I/O

30% hardware reduction with same amount of traffic

Scalable systems
simple
solve the problem at hand:
product of evolution:the complexity will come over time

Need the flexibility

Scalable techniques
divide and conquer: partition things. distribute things
approximate correctness: the system of the state is what what is reported to be so if you can't tell that your system is fundamentally skewing and inconsistent, then it's not
e.g., if you write a comment, and another person on the other side of the world is loading the watch page, he or she may not care what you write, but you may want to see the comment, so inconsistency comes to make sure the writer sees the comment first, and thus can save some cost.
expert knob twiddling: consistency, durability
jitter: introduces randomness, things have tendency to stack up
e.g., cache expirations: if there is a popular video, we want to cache it. If we set usual cache timeout for an hour or 10 minutes, but for a very popular video (the most popular one yesterday), the cache timeout maybe 24 hours. If everything expires at one given time, then every machine will observe that expiration exactly the same time and go back and try to compute it, and this is awful. By jittering, the desired expiration time is about 24 hours and up, but we will randomly jittering (adding variances) around 18 to 30 hours , and that prevent things from stacking up. Because system has the tendency to synchronize lines up.
cheating: when you have monotonically increasing counters like a view count, you could do a full transaction every time you update that, or you can do a transaction once in a while and update by a random amount, as long as the change people will believe it is real.

Scalable components
Well defined inputs:
Well defined dependencies
frequently end up behind an RPC (remote procedure call)
leverage local optimizations

Efficiency
uncorrelated with scalability
The most efficient thing would be to cram everything in process and see
focus on algorithms: focus on macro level, they way individual the components break out doesn't matter,
libraries:
wiseguy
pycurl
spitfire
serialization formats

tools
Apache
linux
mySQL
vitess
zookeeper