
# Introduction
- In this article, we discuss one of the most important nonlinear data structures in
computing—trees.

## General Tree
- A Tree is an abstract data type that stores elements hierarchically.
- Formally, a tree T as a set of nodes storing elements such that the nodes have a parent-child relationship that satisfies the following properties
  - If T is nonempty, it has a special node, called the root of T, that has no parent
  - Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w

```python
class Tree:
  class Position:
    def __ne__(self, other):
      return not (self == other)

  def root(self):
    return NotImplementError('must be implemented by subclass')

  def parent(self):
    """ return Position representing p's parent"""

  def num_children(self):
    return NotImplementError('must be implemented by subclass')

  def children(self, p):
    """Generate an iteration of Position p has"""

  def is_root(self, p):
    return self.root() == p

  def is_leaf(self, p):
    return self.num_children(p) == 0

  def is_empty(self):
    return len(self) == 0

  def depth(self, p):
    if self.is_root(p):
      return 0
    else:
      return 1 + self.depth(self.parent(p))

  def height(self, p)
    if self.is_leaf(p)
      return 0
    else:
      return 1 + max(self.height(c) for c in self.children(p))
```

## Binary Tree
- Every node has at most two children
- Each child node is labeled as being either a left child or a right child
- A left child precedes a right child in the order of children of a node

```python
class BinaryTree(Tree):
  def left(self,p):
    """return a position representing p's left child"""
    """return None if p does not have a left child"""
  
  def right(self, p):
    """return a position representing p's right child"""
    """return None if p does not have a right child"""

  def sibling(self,p):
    parent = self.parent(p)
    if parent is None:
      return None
    else:
      if p == self.left(parent):
        return self.right(parent)
      else:
        return self.left(parent)

  def children(self,p):
    if self.left(p) is not None:
      yield self.left(p)
    if self.right(p) is not None:
      yield self.right(p)
```

### Linked Binary Tree
- https://leetcode.com/problems/linked-list-in-binary-tree/
- 

Trees


# Introduction
A relational database like SQL is a collection of data items organized in tables.
In this article, I'll try to dig deeper into `RDBMS and Scalability`.

## Replication
### Master-slave replication
The master serves reads and writes, replicating writes to one or more slaves, which serve only reads.  
Slaves can also replicate to additional slaves in a tree-like fashion.  
If the master goes offline, the system can continue to operate in read-only mode until a slave is promoted to a master or a new master is provisioned.  
Disadvantage is that additional logic is needed to promote a slave to a master.  

### Master-master replication
Both masters serve reads and writes and coordinate with each other on writes.  
If either master goes down, the system can continue to operate with both reads and writes.
Disadvantage is that most master-master systems are either loosely consistent (violating ACID) or have increased write latency due to synchronization.  
Conflict resolution comes more into play as more write nodes are added and as latency increases.  

### Common disadvantage
- There is a potential for loss of data if the master fails before any newly written data can be replicated to other nodes.
- If there are a lot of writes, the read replicas can get bogged down with replaying writes and can't do as many reads.
- The more read slaves, the more you have to replicate, which leads to greater replication lag.

## Federation
Federation (or functional partitioning) splits up databases by function.  
For example, instead of a single, monolithic database, you could have three databases: forums, users, and products, resulting in less read and write traffic to each database and therefore less replication lag.  
Smaller databases result in more data that can fit in memory, which in turn results in more cache hits due to improved cache locality.  
With no single central master serializing writes you can write in parallel, increasing throughput.

### Disadvantage
- Federation is not effective if your schema requires huge functions or tables.
- You'll need to update your application logic to determine which database to read and write.

## Sharding
Sharding distributes data across different databases such that each database can only manage a subset of the data.  
Taking a users database as an example, as the number of users increases, more shards are added to the cluster.

### Disadvantages
- You'll need to update your application logic to work with shards, which could result in complex SQL queries.
- Data distribution can become lopsided in a shard. For example, a set of power users on a shard could result in increased load to that shard compared to others.
- Rebalancing adds additional complexity. A sharding function based on consistent hashing can reduce the amount of transferred data.
- Joining data from multiple shards is more complex.
- Sharding adds more hardware and additional complexity.

## Denormalization
Denormalization attempts to improve read performance at the expense of some write performance  
In most systems, reads can heavily outnumber writes 100:1 or even 1000:1.  
A read resulting in a complex database join can be very expensive, spending a significant amount of time on disk operations.

### Disadvantages
- Data is duplicated.
- Constraints can help redundant copies of information stay in sync, which increases complexity of the database design.
- A denormalized database under heavy write load might perform worse than its normalized counterpart.

## SQL tuning
It's important to benchmark and profile to simulate and uncover bottlenecks.

## SQL or NoSQL
### Reasons for SQL
- Structured data
- Strict schema
- Relational data
- Need for complex joins
- Transactions
- Clear patterns for scaling
- More established: developers, community, code, tools, etc
- Lookups by index are very fast

### Reasons for NoSQL
- Semi-structured data
- Dynamic or flexible schema
- Non-relational data
- No need for complex joins
- Store many TB (or PB) of data
- Very data intensive workload
- Very high throughput for IOPS



RDBMS and Scalability


# Introduction
In this article, I'll try to design `Twitter`.

## STEP1: Constraints and user cases
### Use Case
- People can post tweets
- Follow other people
- Favorite tweets

### What we should figure out
- How many users do we expect this system to handle?
  - Aim for 10 million users generating around 100 million requests per day
  - Expect that each user will be following 200 other users on average, but expect some extraordinary users with tens of thousands of followers
- How many requests will that generate?
  - Expect that there will be a maximum of 10 million tweets per day and each tweet will probably be favorites twice on average but again, expect some big outliers

### Math
- Edge of the network of users
  - 200 follows * 10 MN = 2 BN edges
- The number of favorites
  - 10 MN tweets * 2(twice fav) = 20 MN favorites

### Summary
- 10 million users
- 10 million tweets per day
- 20 million tweets favorites per day
- 100 million HTTP requests to the site(daily)
  - 1150 requests per second
- 2 billion "follow relations"
- Some users and tweets could generate an extraordinary amount of traffic

## STEP2: High-level Design
### Layer
- Application Layer
  - posting new tweets(write)
  - following a user(write)
  - favoring a tweet(write)
  - displaying data about users and tweets(read)
- Data storage layer
  - the data storage that we will use to store all the data that needs to be persisted

## STEP3 Understanding bottlenecks and Scalable Design
### Handling user requests
- 1150 HTTP requests per second
- Set a load balancer and a set of application servers running behind it
- The load balancer routes requests to the servers using some predefined logic
- Disadvantage
  - A single load balancer is a single point of failure, configuring multiple load balancers further increases complexity.

### Storing the data
- The data
  - Users profiles
  - A set of tweets
  - Follow relationships
  - Favorites
- Tweets will be generated at an average speed of 10 million per day
  - for a single year there will be 3.65 billion incoming tweets
  - Aim for a solution that can store efficiently at least 10 BLN tweets for now
  - 1 tweet : 140 characters
  - 140 * 10 BLN = 1.4 trillion => 2.8 TB(1 character: 2byte, 1TB = 2^40 bytes)
- 2 billion each connection
  - follower and followed => 2 user IDs
  - 8(two 4 bytes integer) * 2BN = 16BN bytes => 16 GB(1GB = 2^30 bytes)
- The favorites are expected to grow at a rate of 20 mln per day
  - Let’s say we want to be able to store at least 20 bln such objects
  - They can probably just point to one user and one tweet through their IDs
  - 8 bytes(User IDs) + 4 bytes(Tweet ID) = 12 bytes
  - 12 * 20 BLN = 240 BLN bytes => 240 GB
- Expected Data: 2.6 - 2.7 terabytes

### Read/Write access
- In order to handle the incoming read requests we may need to use a caching solution
  - A database stores data on disk and it is much slower to read from disk than from memory
  - Databases usually have their own caching mechanisms but with memcached we have better control over what gets cached and how
- Add the appropriate indexes
  - This will also be vital for executing quick queries joining tables
- Partitioning the data

## STEP4: Low-level Design(Optional)
### Database Scheme

### Building a RESTful API


Design Twitter


# Introduction
In this article, I'll try to design `Pastebin.com (or Bit.ly)`.

## STEP1: Constraints and user cases
### Use Case
- Shortening: take a url => return a much shorter url
- Redirection: take a short url => redirect to the original url
- Custom url
- Analytics
- Automatic link expiration
- Manual link removal
- UI vs API

### Decide which one should be worry about
- Shortening: take a url => return a much shorter url
- Redirection: take a short url => redirect to the original url
- Custom url
- High availability of the system

### What we should figure out
- Amount of traffic the system should handle
- Amount of data the system should work
- How many requests a month should the site handle 
- How many new URLs per month should the site handle

### Estimation
- Compare with well-known services and assume constraints
- Twitter: 15 BN new tweets
- All shortened URLs per month: 1.5 BN
  - Between 1 in 20 and 1 in 10 tweets contains a shortened URL
- Sites below the top 3: shorten 300M per month
  - This service is not gonna be in the top 3 most popular URL shortening services
  - But it's gonna be in the top 10
  - These the top three sites probably shortened 80% leaving the other 20%
- We: 100MLN urls each month
  - Large players will probably be getting between 10% to a third of that

### Math(Requests and URLs)
- New urls per month: 100MLN
- 1BN requests per month
  - 20% of all URLs generate 80% of the traffic
- Requests per second 400+ (40: shortens, 360: redirects)
  - 1BN / (30 day * 24 hour * 60 min * 60 second)
  - 10% come from shortening and 90% come from redirection
- Total urls: 5 years x 12 months x 100MLN = 6BN urls

### Math(Data)
- 3TBs for all urls, 36GB for all hashes (over 5 years)
  - (6BN urls * 500 bytes) / 1TB(2 ** 40)
  - 500 bytes per URL
- New data written per second: 40 * (500 + 6): 20K
  - 6 bytes per hash(6 characters: url)
- Data read per second: 360 redirects * 506 bytes: 180K

## STEP2: Abstract design
### Layer
- Application server layer(serves the requests)
  - Shortening service
    - generate on your hash
    - check if it's in the datastore, if not store new mapping
  - Redirection service
- Data storage layer(keep track of the hash => url mappings)
  - Acts like a big hash table
    - stores new mappings
    - retrieves a value given a key

### define how the hashing would work
- hashed_url = convert_to_base62(md5(original_url + random_salt))[:6]

## STEP3 Understanding bottlenecks
- What is the URL shortening problem all about 
- Where are we going to have heartache once we start scaling

### Bottlenecks
- Traffic is probably not going to be very hard, data - more interesting

## STEP4 Scalable Design
### Constraints
- Billions of objects
- Each object is fairly small(< 1K)
- There are no relationships between the objects
- Reads are 9x more frequent than writes (360 reads, 40 writes per second)
- 3TBs of urls, 36GB of hashes

### Application Server Layer
- Start with one machine
- Measure how far it takes us (load tests)
- Add a load balancer + a cluster machines over time to deal with spike-y traffic, to increase availability

### Data Storage
- Use one MySQL table with two fields
- mappings
  - hash: varchar(6)
  - original_url: varchar(512)
- Create unique index on the hash(36GB+) : We want to hold it in memory
  - Op1: Vertical scaling of the MySQL machine for a while
  - Op2: Eventually, partition the data by taking the first char of the hash mod the number of partitions
    - 5 partitions, 600GB of data, 8GB of indexes
- Think about a master-slave setup
  - Master-slave (reading from the slaves, writes to the master)



Design Pastebin.com (or Bit.ly)


# Introduction
- Python lists have some notable disadvantages
  - The length of a dynamic array might be longer than the actual number of elements that it stores
  - Amortized bounds for operations may be unacceptable in real-time systems
  - Insertions and deletions at interior positions of an array are expensive
- Linked Lists avoid the three disadvantages noted above for array-based sequences
- In this article, I'll try to dig deeper into `Linked Lists`

## Singly Linked Lists
- An important property of a linked list is that it does not have a predetermined fixed size
- It uses space proportionally to its current number of elements

### Inserting an Element at the Head of a Singly Linked List
```python
newest = Node(e) # create new node instance storing reference to element e
newest.next = L.head # set new node’s next to reference the old head node
L.head = newest # set variable head to reference the new node
L.size = L.size + 1 # increment the node count
```

### Inserting an Element at the Tail of a Singly Linked List
```python
newest = Node(e) # create new node instance storing reference to element e
newest.next = None # set new node’s next to reference the None object
L.tail.next = newest # make old tail node point to new node
L.tail = newest # set variable tail to reference the new node
L.tail = L.size + 1 # increment the node count
```

### Removing an Element from a Singly Linked List
```python
if L.head is None:
  Indicate an error: the list is empty.
L.head = L.head.next # make head point to next node (or None)
L.size = L.size − 1
```

## Circularly Linked Lists
- there is a more tangible notion of a circularly linked list, as we can have the tail of the list use its next reference to point back to the head
of the list

## Doubly Linked Lists
- A linked list in which each node keeps an explicit reference to the node before it and a reference to the node after it.
- These lists allow a greater variety of O(1)-time update operations, including insertions and deletions at arbitrary positions within the list.

```python
class Node:
__slots__ = _element , _prev , _next # streamline memory

def init (self, element, prev, next): # initialize node’s fields
  self._element = element # user’s element
  self._prev = prev # previous node reference
  self._next = next # next node reference
```

## The Positional List ADT


Linked Lists


# Introduction
In this article, I'll try to dig deeper into `Stacks, Queues, and Deques`.

## Stacks
A stack is a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle  
Stack supports the following methods  

```python
S.push(e) # Add element e to the top of stack S
S.pop() # Remove and return the top element from the stack S an error occurs if the stack is empty
S.top() # Return a reference to the top element of stack S, without removing it; an error occurs if the stack is empty
S.is_empty() # Return True if stack S does not contain any elements
len(S) # Return the number of elements in stack S; in Python, we implement this with the special method __len__
```

### Running time
- O(1)
- The size of the stack would no longer be synonymous with the length of the list
- Pushes and pops of the stack would not require changing the length of the list

## Queues
Queue is a collection of objects that are inserted and removed according to the first-in, first-out (FIFO) principle

```python
Q.enqueue(e) # Add element e to the back of queue Q.
Q.dequeue() # Remove and return the first element from queue Q; an error occurs if the queue is empty.
Q.first() # Return a reference to the element at the front of queue Q, without removing it; an error occurs if the queue is empty.
Q.is_empty() # Return True if queue Q does not contain any elements.
len(Q) # Return the number of elements in queue Q; in Python, we implement this with the special method __len__
```

## Double-Ended Queues
- It supports insertion and deletion at both the front and the back of the queue


Stacks, Queues, and Deques


# Introduction
In this article, we explore Python's various “sequence” classes, namely the builtin list, tuple, and str classes.  
Each supports indexing to access an individual element of a sequence, using a syntax such as seq[k].

## Low-Level Arrays
- Any byte of the main memory can be efficiently accessed based upon its memory address
- In this sense, we say that a computer’s main memory performs as random access memory (RAM)
- we say that any individual byte of memory can be stored or retrieved in O(1) time

## Referential Arrays
- Python represents a list or tuple instance using an internal storage mechanism of an array of object references.
- At the lowest level, what is stored is a consecutive sequence of memory addresses at which the elements of the sequence reside
- Although the relative size of the individual elements may vary, the number of bits used to store the memory address of each element is fixed
- Python can support constant-time access to a list or tuple element based on its index
```python
[ Rene , Joseph , Janet , Jonas , Helen , Virginia , ... ]
[0,1,2,3,4,5]
```

### Shallow copy
The below references the same elements as in the first list.  
If the contents of the list were of a mutable type, a deep copy, meaning a new list with new elements.  
It can be produced by using the deepcopy function from the copy module.

```python
backup = list(primes)
```

## Compact Arrays
- `Strings` are represented using an array of characters (not an array of references)
- Compact arrays such like `Strings` have several advantages over referential structures in terms of computing performance
  - the overall memory usage will be much lower
  - the primary data are stored consecutively in memory

## Dynamic Arrays
- A dynamic array is that a list instance maintains an underlying array that often has greater capacity than the current length of the list
- base: 56
  - length:  4: 56 + 8 * 4  = 88
  - length: 16: 56 + 8 * 16 = 184
- A list is a referential structure, the result of getsizeof for a list instance only includes the size for representing its primary structure
- The remaining issue to consider is how large of a new array to create
- A commonly used rule is for the new array to have twice the capacity of the existing array that has been filled
```python
import sys
for k in range(26):
  a = len(data)
  b = sys.getsizeof(data)
  print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a,b))
  data.append(None)

Length:   0; Size in bytes:   56
Length:   1; Size in bytes:   88
Length:   2; Size in bytes:   88
Length:   3; Size in bytes:   88
Length:   4; Size in bytes:   88
Length:   5; Size in bytes:  120
Length:   6; Size in bytes:  120
Length:   7; Size in bytes:  120
Length:   8; Size in bytes:  120
Length:   9; Size in bytes:  184
Length:  10; Size in bytes:  184
Length:  11; Size in bytes:  184
Length:  12; Size in bytes:  184
Length:  13; Size in bytes:  184
Length:  14; Size in bytes:  184
Length:  15; Size in bytes:  184
Length:  16; Size in bytes:  184
Length:  17; Size in bytes:  256
Length:  18; Size in bytes:  256
Length:  19; Size in bytes:  256
Length:  20; Size in bytes:  256
Length:  21; Size in bytes:  256
Length:  22; Size in bytes:  256
Length:  23; Size in bytes:  256
Length:  24; Size in bytes:  256
Length:  25; Size in bytes:  256
```

## Multidimensional Data Sets
- We can represent a two-dimensional array as a list of rows,
with each row itself being a list of values
- An advantage of this representation is that we can naturally use a syntax such
as data[1][3]

```python
> data = ([0] * 2) * 4
> data
[0, 0, 0, 0, 0, 0, 0, 0] # This is a mistake

> data = [[0] * 2] * 4
> data
[[0, 0], [0, 0], [0, 0], [0, 0]] # Still a mistake
> data[0][1] = 2
> data
[[0, 2], [0, 2], [0, 2], [0, 2]] # same reference

> data = [[0]*2 for i in range(4)]
> data
[[0, 0], [0, 0], [0, 0], [0, 0]]
> data[0][1] = 2
> data
[[0, 2], [0, 0], [0, 0], [0, 0]] # references are isolated
```


Array-Based Sequences


# Introduction
Recursion is a technique by which a function makes one or more calls to itself during execution, or by which a data structure relies upon smaller instances of the very same type of structure in its representation.

## The Factorial Function
- n!
  - if n = 0: 1
  - if n >= 1: n(n-1)(n-2)...3*2*1 => n(n-1)!
```python
def factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n-1)
```

## Binary Search
This algorithm maintains two parameters, low and high, such that all the candidate entries have index at least low and at most high.
Initially, low = 0 and high = n − 1.  
We then compare the target value to the median candidate, that is, the item data[mid] with index

```python
mid = [(low + high)/2]
```

We consider three cases:
- If the target equals data[mid], then we have found the item we are looking for, and the search terminates successfully.
- If target < data[mid], then we recur on the first half of the sequence, that is, on the interval of indices from low to mid − 1.
- If target > data[mid], then we recur on the second half of the sequence, that is, on the interval of indices from mid + 1 to high.
- An unsuccessful search occurs if low > high, as the interval [low,high] is empty.

```python
def binary_search(data, target, low, high):
  if low > high:
    return False
  else:
    mid = (low + high) // 2
    if target == data[mid]:
      return True
    elif target > data[mid]:
      return binary_search(data,target,mid+1,high)
    else:
      return binary_search(data,target,low,mid-1)

if __name__ == "__main__":
  data = [2,4,5,7,8,9,12,14,17,19,22,25,27,28,33,37]
  print(binary_search(data,22,0,len(data)-1)) # True
```

### Analyze Performance
- Range = 2^(Loop)
- log2(Range) = Loop
- log2(Range) = loge(Range) / loge(2) ≒ loge(Range)
- Range: n -> Loop = logn
- Time Complexity : O(log(n))

|Range|Loop|
|--|--|
|2|1|
|4|2|
|8|3|
|16|4|
|...|...|
|2^k|k|

## Fibonacci Numbers
### Bad Fibonacci Numbers
- 1,1,2,3,5,8...
- The number of calls more than doubles for each two consecutive indices
- This snowballing effect is what leads to the exponential running time

```python
def fibo(n):
  print("called {}".format(n))
  if n == 0:
    return 0
  elif n == 1:
    return 1
  result = fibo(n-1) + fibo(n-2)
  print("n: {} result: {}".format(n,result))
  return result

if __name__ == "__main__":
  print(fibo(5))
```

### Good Fibonacci Numbers
- We can compute much more efficiently using a recursion in which each invocation makes only one recursive call

```python
def fibo(n):
  if n <= 1:
    return (n,0)
  else:
    (a, b) = fibo(n-1)
    return (a+b, a)

if __name__ == "__main__":
  print(fibo(5)[0])
```

## Ref
https://qiita.com/tan5o/items/c977908f1e69ab2e8af1


Recursion


# Introduction
In this article, I'll try to dig deeper into `Python Basics`.

# Mutable vs Immutable
## Mutable
- The object ids are same
```python
a = [1,2,3]

print("a = %s" % a)
print("id(a) = %s" % id(a))

a.append(4)

print("a = %s" % a)
print("id(a) = %s" % id(a))

a = [1, 2, 3]
id(a) = 4397053320
a = [1, 2, 3, 4]
id(a) = 4397053320
```

## Immutable
- The object ids are changed
```python
a = "abc"

print("a = %s" % a)
print("id(a) = %s" % id(a))

a = a + "def"

print("a = %s" % a)
print("id(a) = %s" % id(a))

a = abc
id(a) = 4432244216
a = abcdef
id(a) = 4434341816
```

## Variable

|class|Immutable|
|--|--|
|bool|✅|
|int|✅|
|float|✅|
|list||
|tuple|✅|
|str|✅|
|set||
|frozenset|✅|
|dict||

## Multiple variable
### Mutable
```python
a = [1,2,3]
b = a

a.append(4)

print ("a = %s" % a)
print ("b = %s" % b)

a = [1, 2, 3, 4]
b = [1, 2, 3, 4]
```

### Immutable
```python
a = "abc"
b = a

a = a + "def"

print ("a = %s" % a)
print ("b = %s" % b)

a = abcdef
b = abc
```

# Python Conveniences
## Conditional Expressions
```python
# Case 1
if n >= 0:
  param = n
else:
  param = −n

result = foo(param) # call the function

# Case 2
param = n if n >= 0 else −n # pick the appropriate value
result = foo(param)
```

## Comprehension Syntax
```python
# Case 1
result = []
for k in range(1, n+1):
  if n % k == 0:
    result.append(k)

# Case 2
result = [k for k in range(1, n+1) if n % k == 0]
```

## Packing and Unpacking of Sequences
```python
for x, y in [ (7, 2), (5, 8), (6, 4) ]:
for k, v in mapping.items():
```

## Simultaneous Assignments
```python
j = 1
k = 2
id(j) # 4343226616
id(k) # 4343226648

j,k = k, j

id(j) # 4343226648
id(k) # 4343226616
j # 2
k # 1
```

## Modules and the Import Statement
- If the module is imported from another scripts, the code under `if name == __main__ :` is not executed
- It is executed only when if the module is directly invoked as a script
```python
if name == __main__ :
```

Python Basics


# Introduction
In this article, I'll try to dig deeper into `Scalability`.

## Clones
### App Codebase
Public servers of a scalable web service are hidden behind a load balancer.  
This load balancer evenly distributes load onto your cluster of app servers.   
So user should always get the same result of their request back.  
Every server contains exactly the same codebase and doesn't store any user related data like sessions on local server.  

### Sessions
Regarding sessions, they need to be stored in a centralized data store.  
It can be an external database or an external persistent cache, like Redis.  
This external persistent cache will have better performance than an external database.  
By external I mean that the data store does not reside on the application servers.  
Instead, it is somewhere in or near the data center of your application servers.  

### Deployment
How can you make sure that a code change is sent to all your servers without one server still serving old code?  
You can now create an image file.  
Whenever you start a new instance/clone, just do an initial deployment of your latest code and you are ready!

## Database
Our servers can now horizontally scale and we can already serve thousands of concurrent requests.   
But somewhere down the road our application gets slower and slower and finally breaks down. 
You can choose from the following 2 paths:

### Path #1
- The following new actions to keep our database running will be more expensive and time consuming than the previous one. 
  - Stick with MySQL and keep the “beast” running.  
  - Do master-slave replication (read from slaves, write to master) and upgrade our master server by adding RAM  
  - “sharding”, “denormalization” and “SQL tuning” 

### Path #2
- Denormalize right from the beginning and include no more Joins in any database query. 
- You can stay with MySQL, and use it like a NoSQL database, or you can switch to a better and easier to scale NoSQL database like MongoDB or CouchDB.

## Cache
Our users still have to suffer slow page requests when a lot of data is fetched from the database.  
The solution is the implementation of a cache.  
With “cache” it means in-memory caches like Memcached or Redis.  

###  In-memory caches
A cache is a simple key-value store and it should reside as a buffering layer between application and data storage.  
Whenever application has to read data it should at first try to retrieve the data from cache.
Only if it’s not in the cache should it then try to get the data from the main data source.

### Why should you do that?
Because a cache is lightning-fast.  
It holds every dataset in RAM and requests are handled as fast as technically possible.

### 2 Patterns
#### Cached Database Queries
That’s still the most commonly used caching pattern.  
Whenever you do a query to our database, we store the result dataset in cache.  
A hashed version of your query is the cache key.  
The next time you run the query, we first check if it is already in the cache.  
This pattern has several issues and the main issue is the expiration.
It is hard to delete a cached result when you cache a complex query.
When one piece of data changes, you need to delete all cached queries who may include that table cell.

#### Cached Objects
In general, see your data as an object like you already do in your code (classes, instances, etc.).  
Let your class assemble a dataset from your database and then store the complete instance of the class or the assembled dataset in the cache. 
When your class has finished the “assembling” of the data array, directly store the data array, or better yet the complete instance of the class, in the cache.  
This allows you to easily get rid of the object whenever something did change and makes the overall operation of your code faster and more logical.

### Some ideas of objects to cache
- user sessions (never use the database!)
- fully rendered blog articles
- activity streams
- user<->friend relationships 

## Asynchronism
- In general, there are two ways / paradigms asynchronism can be done. 

### SSG
- Doing the time-consuming work in advance and serving the finished work with a low request time.
- Pages of a website, maybe built with a massive framework or CMS, are pre-rendered and locally stored as static HTML files on every change. 
- This pre-computing of overall general data can extremely improve websites and web apps and makes them very scalable and performant.

### Async
A user comes to your website and starts a very computing intensive task which would take several minutes to finish.
So the frontend of your website sends a job onto a job queue and immediately signals back to the user: your job is in work, please continue to the browse the page.  
The job queue is constantly checked by a bunch of workers for new jobs.  
If there is a new job then the worker does the job and after some minutes sends a signal that the job was done. 
The frontend, which constantly checks for new “job is done” - signals, sees that the job was done and informs the user about it.

## Performance vs scalability
- If you have a performance problem, your system is slow for a single user
- If you have a scalability problem, your system is fast for a single user but slow under heavy load

### Scalability
- A service is said to be scalable if when we increase the resources in a system, it results in increased performance in a manner proportional to resources added
- To improve the reliability of the offered service. Introducing redundancy is an important first line of defense against failures

### Why is scalability so hard?
- Scalability cannot be an after-thought
  - It requires applications and platforms to be designed with scaling in mind, such that adding resources actually results in improving the performance or that if redundancy is introduced the system performance is not adversely affected.
- Growing a system through scale-out generally results in a system that has to come to terms with heterogeneity
  - Resources in the system increase in diversity as next generations of hardware come on line, as bigger or more powerful resources become more cost-effective or when some resources are placed further apart
  - Heterogeneity means that some nodes will be able to process faster or store more data than other nodes in a system and algorithms that rely on uniformity either break down under these conditions or underutilized the newer resources.

## Latency vs throughput
- Generally, you should aim for maximal throughput with acceptable latency.
  - Latency is the time to perform some action or to produce some result
  - Throughput is the number of such actions or results per unit of time



Scalability


# Introduction
Most Engineers must hear the word, Object-Oriented Programming(OOP).  
However, there are few engineers who can explain it.  
In this article, I'll try to dig deeper into this topic.

## 1. The Forgotten History of OOP
### 1-1. Low level languages to High level languages
Low level languages like machine code and assembly appeared in the 1940s.  
By the end of the 1950s, the first popular high-level languages appeared.  
After that, C-family languages have replaced both COBOL and FORTRAN for most applications.  
In the course of its programing languages development, they've established how easy it is for people to express the work they want the PC to do.

### 1-2. Structured languages
Structured languages were proposed to further improve productivity and quality of programming.  
They increased independence of subroutines to make them more maintainable.  
They also need to reduce the number of global variables shared by multiple subroutines.  
However, they have to use global valuable when they need to retain information beyond the execution time of a subroutine.     
In this case, it's difficult to know which subroutine is modifying a global variable.

### 1-3. OOP
To solve the above problems, Object-oriented programming (OOP) was coined by Alan Kay.  
OOP is a style of programming that focuses on using objects to design and build applications.
OOP organizes the program to combine data and functionality and wrap it inside something called an `Object`.

* Objects  
Objects represent a real-world entity and the basic building block of OOP.  
ex) an Online Shopping System will have objects such as shopping cart, customer,product item, etc.

* Class  
Class is the prototype or blueprint of an object. It is a template definition of the attributes and methods of an object.  
ex) in the Online Shopping System, the Customer object will have attributes like shipping address, credit card, etc., and methods for placing an order, canceling an order, etc.

## 2. The four principles of OOP
### 2-1: Encapsulation
Encapsulation is the mechanism of binding the data together and hiding it from the outside world.  
It is achieved when each object keeps its state private so that other objects don’t have direct access to its state.  
Instead, they can access this state only through a set of public functions.

```python
class Product:

    def __init__(self):
        self.__maxprice = 900

    def sell(self):
        print("Selling Price: {}".format(self.__maxprice))

    def set_max_price(self, price):
        self.__maxprice = price

product = Product()
product.sell() # Selling Price: 900

# change the price
product.__maxprice = 1000
product.sell() # Selling Price: 900

# using setter function
product.set_max_price(1000)
product.sell() # Selling Price: 1000
```

### 2-2. Abstraction
Abstraction can be thought of as the natural extension of encapsulation.  
It means hiding all but the relevant data about an object in order to reduce the complexity of the system.  
In a large system, objects talk to each other, which makes it difficult to maintain a large code base;  
Abstraction helps by hiding internal implementation details of objects and only revealing operations that are relevant to other objects.

```python
from abc import ABC, abstractmethod

class Parent(ABC):
  def common(self):
    print('In common method of Parent')

  @abstractmethod
  def vary(self):
    pass

class Child1(Parent):
  def vary(self):
    print('In vary method of Child1')

class Child2(Parent):
  def vary(self):
    print('In vary method of Child2')

# object of Child1 class
child1 = Child1()
child1.common() # In common method of Parent
child1.vary() # In vary method of Child1

# object of Child2 class
child2 = Child2()
child2.common() # In common method of Parent
child2.vary() # In vary method of Child2
```

### 2-3: Inheritance
Inheritance is a mechanism to eliminate code duplication by grouping common parts of class definitions

### 2-4: Polymorphism
Polymorphism is the ability of an object to take different forms and thus, depending upon the context, to respond to the same message in different ways.  
ex) a chess game; a chess piece can take many forms, like bishop, castle, or knight and all these pieces will respond differently to the ‘move’ message.

```python
class Bishops:

    def move(self):
        print("Bishops can move diagonally")

class Knights:

    def move(self):
        print("Knights can move two squares vertically and one square horizontally, or two squares horizontally and one square vertically")

# common interface
def move_test(chess_piece):
    chess_piece.move()

#instantiate objects
bishop = Bishops()
knight = Knights()

# passing the object
move_test(bishop) # Bishops can move diagonally
move_test(knight) # Knights can move two squares vertically and one square horizontally, or two squares horizontally and one square vertically
```

## 3. Example
### CreditCard Class
- Actually, we need to consider type check error if arg is invalid value
```python
class CreditCard
  def __init__(self, customer, bank, acnt, limit):
    # encapsulation nonpublic
    self._customer = customer
    self._bank = bank
    self._account = acnt
    self._limit = limit
    self._balance = 0

  # accessor
  def get_customer(self):
    return self._customer

  def get_bank(self):
    return self._bank

  def charge(self, price):
    if price + self._balance > self._limit: # if charge would exceed limit
      return False                          # cannot accept charge
    else:
      self._balance += price
      return True

class PredatoryCreditCard(CreditCard):
  def __init__(self, customer, bank, acnt, limit, apr):
    super().__init__(customer, bank, acnt, limit)
    self._apr = apr

  def change(self, price):
    success = super().charge(price)
    if not success:
      self._balance += 5
    return success

  def process_month(self):
    if self._balance > 0:
      monthly_factor = pow(1 + self._apr, 1/12)
      self._balance *= monthly_factor
```

Object-Oriented Programming(OOP)


> “Yeah It's on. ”


## Hello World!
