hotstar peak handling how

1. WC 2019 IND vs NZ Semifinal resulted in 25.3M concurrent users. Usage of around 10Tbps bandwidth which is 70% of India's capacity.

2. Scale proactively - can't scale in real time. Autoscaling results in insufficient capacity errors at times.

3. Graceful degradation - turn off less critical services when there is too much traffic. Reduce video quality for users. If auth system is having issues(DB in the backend is slow) - allow users to watch without login.

4. Peak traffic shift - as soon as Dhoni got out people went to the home screen. Home screen calls a lot of APIs - recommendation/watch history/general content.

5. Push notifications result in a traffic peaks.

6. Prewarm infra before match time.
7. No dumb clients - clients should add jitter to requests so as not to overwhelm the backend in case of issues.
8. Reject early - drive away a lot of spurious traffic - don't let it come to your backend.

Video

Blog

Facebook live streaming - split input feed into smaller chunks and deliver via hierarchy of cache servers. Don't let too many requests come to the origin server. First request will be a cache miss and rest will be held until the first one comes back.

reservoir sampling

good answer by sumitra narayan

Algorithm R from wikipedia:

(* S has items to sample, R will contain the result *)
ReservoirSample(S[1..n], R[1..k])
// fill the reservoir array
for i = 1 to k
   R[i] := S[i]
// replace elements with gradually decreasing probability
for i = k+1 to n
   j := random(1, i) // important: inclusive range
   if j <= k R[j] := S[i]

String search algorithms - Naive vs Rabin Karp vs KMP

Naive algorithm is O(n) in average as the probability of a random match is very low and even low for 2 consecutive character matches : 26^2. For 1 million char text and 1000 char word 1.04 million comparisons in average case. Worst case O(m*n) so if the above example 1 billion comparisons.

Rabin karp - used in plagiarism detection. Uses rolling hash - for e.g. if the text is ABCD, and we want to search a word of size 3 then we first compare the hash of ABC which is a*7^0 + b*7^1 + c*7^2. If it doesn't match the hash of the word then we move forward like this 1. first drop A => prev_hash - a*7^0. 2. Then divide the balance by 7 => (prev_hash - a*7^0)/7. 3. Then add D => (prev_hash - a*7^0)/7 + D*7^2. Worst case O(m*n)

KMP - Knuth Morris Pratt - uses a pre-computed table to decide from where to resume search in case of failure. Worst case O(n).

Binary search simplified

class Main {

public static void main(String[] args) {

//refer https://medium.com/@elizarov/programming-binary-search-6e999783ba5d

//refer https://www.geeksforgeeks.org/variants-of-binary-search/

//refer https://repl.it/@dharmendratolan/GoodnaturedPertinentIntegrationtesting

// java signed and unsigned right shift

int test = Integer.MAX_VALUE;

System.out.println(test);

int t1 = test + 1;

System.out.println(t1);

int t2 = (test + test) >>> 1;

System.out.println(t2);

int t3 = (test + test) >> 1;

System.out.println(t3);

int[] a = {3,3,3,20,20,20};

int k = 3;

k = 3;

System.out.println("any(" + k + ")" + any(a,k));

k = 4;

System.out.println("any(" + k + ")" + any(a,k));

k = 20;

System.out.println("any(" + k + ")" + any(a,k));

k = 3;

System.out.println("firstGte(" + k + ")" + firstGte(a,k));

k = 20;

System.out.println("firstGte(" + k + ")" + firstGte(a,k));

k = 19;

System.out.println("firstGte(" + k + ")" + firstGte(a,k));

k = 21;

System.out.println("firstGte(" + k + ")" + firstGte(a,k));

k = 3;

System.out.println("firstGt(" + k + ")" + firstGt(a,k));

k = 20;

System.out.println("firstGt(" + k + ")" + firstGt(a,k));

k = 19;

System.out.println("firstGt(" + k + ")" + firstGt(a,k));

k = 3;

System.out.println("lastLte(" + k + ")" + lastLte(a,k));

k = 20;

System.out.println("lastLte(" + k + ")" + lastLte(a,k));

k = 19;

System.out.println("lastLte(" + k + ")" + lastLte(a,k));

k = 3;

System.out.println("lastLt(" + k + ")" + lastLt(a,k));

k = 20;

System.out.println("lastLt(" + k + ")" + lastLt(a,k));

k = 19;

System.out.println("lastLt(" + k + ")" + lastLt(a,k));

k = 21;

System.out.println("lastLt(" + k + ")" + lastLt(a,k));

}

private static Integer lastLt(int[] a, int k) {

// last LT means the element just at the left of k(or virtual k)

int l = -1;

int r = a.length;

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] < k) {

l = m;

} else {

r = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return l;

}

private static Integer lastLte(int[] a, int k) {

// last LTE means (the last k) or (element just left of virtual k)

int l = -1;

int r = a.length;

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] <= k) {

l = m;

} else {

r = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return l;

}

private static Integer firstGt(int[] a, int k) {

//firstGt means the element just right of k (or virtual k)

int l = -1;

int r = a.length;

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] > k) {

r = m;

} else {

l = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return r;

}

private static Integer firstGte(int[] a, int k) {

//firstGte means (the first k) or (the element just right of virtual k)

int l = -1;

int r = a.length;

//exact match

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] >= k) {

r = m;

} else {

l = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return r;

}

private static Integer any(int[] a, int k) {

int l = -1;

int r = a.length;

//exact match

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] == k) {

ans = m; break;

}

else if(a[m] > k) {

r = m;

} else {

l = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return ans;

}

}

MapReduce paper Notes

Paper is here.

MR programming model - Map - written by the user - takes an input key/value pair (file_name/file_contents) and emits intermediate pairs like (word, 1) for Wordcount. MR library combines all intermediate pairs and gives them to a reduce task which gives the final output for that intermediate key.

Handling master failure - just abort the MR task since there is only one master and hence failure is unlikely. Other option is to periodically save state of the master and pick up from there.

Locality - to preserve bandwidth, the MR master tries to schedule map task on a machine having the copy of the data or near to a replica of the data.

Backup tasks for Stragglers - When a MapReduce operation is close to completion, the master schedules backup executions of the remaining in-progress tasks. The task is marked as completed whenever either the primary or the backup execution completes.

Custom partitioning - default is hash(key) mod R, at times it's not enough. For e.g. if it's web links and we want all links with same hostname in same output, then hash(hostname(key)) mod R is right hashing approach.

Combiner function - after the Map task is executed a big payload is sent over the network to the reducer. To reduce the size we can combine the intermediate keys which come out from the map. Reduce and Combine will most likely have the same code - just that output of Reduce will be written to an output file whereas output of the Combiner will be sent over the network to Reduce.

Debugging - there is a way to sequentially execute the MR tasks to debug them better.

Counters - there are ways to keep counts of specific things. They are sent from worker machines to master (piggybacking on the ping response).

Implementing Sort - TeraSort is a standard map/reduce sort, except for a custom partitioner that uses a sorted list of N − 1 sampled keys that define the key range for each reduce. In particular, all keys such that sample[i − 1] <= key < sample[i] are sent to reduce i. This guarantees that the output of reduce i are all less than the output of reduce i+1.

Some numbers - Cluster of 1800 machines with each one having two 2GHz Intel Xeon processors with HyperThreading enabled, 4GB of memory, two 160GB IDE disks and a gigabit Ethernet link.

Grep which scanned through 10^10 100 bytes records (1TB in total) took 150 seconds.

Sorting was around 1000 seconds.

Advantages - 

Code to deal with fault tolerance/distribution and parallelization is removed from the core task code.

Conceptually simpler.

MapReduce exploits a restricted programming model to parallelize the user program automatically and to provide transparent fault-tolerance.

CAP theorem

http://ksat.me/a-plain-english-introduction-to-cap-theorem/ 

CA => Consistent and available

C => same state

A => every request should receive a response

P => any number of messages in intercom can be lost

If

C => same state

AND

A => every request should receive a response, so every write request should be Success or Failure

THEN

!P => since you can't lose intercom messages

CP

If

C => same state

AND

P => any number of messages in intercom can be lost

THEN

!A => can't respond to write requests since there is no assurance of being C as the messages are lost

AP

A=> take write requests and respond

AND

P => any number of messages in intercom can be lost

THEN

!C => in absence of communication they will be in different states.

http://blog.thislongrun.com/2015/04/the-unclear-cp-vs-ca-case-in-cap.html  

trinity piano grade 1 enchanted garden notes

Enchanted garden notes:
Bar 1-8: https://www.youtube.com/watch?v=NUKosaWmJVc&list=LLKd4SDfv1ujxDFLpKOh4fIw
Notice treble clef for both the hands.

Right hand:
AD AD BBCB AD AD AD BBCB A

Left hand:
GF GF GE GF GF  GF GE GF
D_  D_ D_  D_ D_ D_  D_ D_

Bar 9-12 make up the phrase: (notice left hand switching to bass clef)

https://www.youtube.com/watch?v=TQa8BOJUuuw&list=LLKd4SDfv1ujxDFLpKOh4fIw

Right hand:
A_CFG_AGA_CFG_AGF_ (finger 3 on A and ends with 1st finger on F)

Left hand:
F C R | Bf F R | F C R | Bf F R (play with fingers 1,5 or 2,5 based on hand size)