Introduction to system design

Theories & Intro

Complex System Design : 15 Design Thinking

Intro to Architecture & System Design

Intro to Design Pattern

Example

Software architecture Example : alram clock

programming interview Elevator System Design

example : Designin Google Docs

Scalable Architecture

Scalable architectures

Principles of Scalable System Design

8 Commonly Used scalable System Design patterns

Docker terms

• docker image

  • 서비스 운영에 필요한 서버 프로그램, 운영체제, 컴파일된 환경 모두를 통째로 묶은 형태

  

• container

  • image를 실행한 상태

Dockerfile

1. Dockefile는 인프라 구성 정보를 담고 있는 일종의 docker script이다.
   • dockerfile 이미지를 build할 떄 파일을 지정해 주면 동작하게 돈다.
     명령어는 다음과 같다

Docker 이미지 생성 및 구동

1. BUILD : dockerfile 로 이미지 생성
   dockerfile로 이미지를 중첩하여 build 하는 것이 가능하다. 여러 이미지를 중첩시키면 그에 따라 image가 stack처럼 쌓이게 된다.

   • image layer example
     

2. ONBUILD : bulid 완료 후에 커멘드가 실행되도록 설정

Useful links

도커 무작정 따라하기 slides

Install docker in CLI

1. Install Homebrew

   1	ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

2. Install docker toolbox

   1 2	brew cask install docker-toolbox brew install caskroom/cask/brew-cask

How to Start docker

1. check the docker version

   1	docker version

2. list the docker machine

   1	docker-machine ls

3. create the docker machine

   1	docker-machine create --driver "virtualbox" myBoxName

4. start the docker machine

   1	docker-machine start myBoxName

5. get into the env of the docker machine

   1	eval $(docker-machine env myBoxName)

   1 2 3 4 5 6

   export DOCKER_TLS_VERIFY="1" export DOCKER_HOST="tcp://192.168.99.100:2376" export DOCKER_CERT_PATH="/Users/huklee/.docker/machine/machines/myBoxName" export DOCKER_MACHINE_NAME="myBoxName" # Run this command to configure your shell: # eval $(docker-machine env myBoxName)

6. when the certification is not working

   1	docker-machine regenerate-certs myBoxName

Start the docker image on the docker box

1. see the docker image list

   1	docker images

2. search the docker images on web

   1 2	docker search [image] # ex) docker search centos

3. download the docker image

   1	docker pull centos:latest

4. the simple test of docker

   1 2 3 4 5 6

   docker run hello-world docker run -d -i -t --name "test2" ubuntu /bin/bash # -d : background docker run -it --name "test1" centos /bin/cal docker ps

5. attach the docker process

   1	docker attach hello

   • to exit without stop :

docker daemon이 꺼져 있는 경우 / docker server is off

• Mac에서는 일단 docker Quickstart Terminal을 찾아서 키면 자동으로 docker daemon default 세팅이 된다.

• 이후에 아래 명령을 실행해 주면 된다.

  1. start the docker machine

     1	docker-machine start myBoxName

  2. get into the env of the docker machine

     1	eval $(docker-machine env myBoxName)

궁금한 점들

• docker를 사용해서 ubuntu / centos 등을 실행시키면 실제 파일 저장 경로라던가 하는 것들은 어떻게 되는 것인지?
• 왜 sudo 를 사용하면 docker-toolbox를 사용했을 때, 에러가 나는가.
• 왜 그렇게 ubuntu같은 것들도 용량이 무지하게 작은가?
• file system을 공유해서 실제 file directory처럼 사용하는 것이 가능한가?

Docker 데이터 볼륨 사용하기

install docker with homebrew on Mac

docker 개념잡기 : 아키텍쳐

python built-in functions : map / reduce / filter / zip

예전에 파이썬을 배웠을 때는 다 배웠었는데, 잘 안 사용하다가 사용법도 헷갈려서 참고차 정리해 보려고 한다!

notice

• 이 예제들은 python 3.6.0을 기준으로 작성되었음
• python 2의 경우에 몇 가지 주의할 점
  • list(map(…)), list(reduce(…))등을 쓸 필요 없이 바로 map(…), reduce(…)을 바로 list 타입으로 사용 가능
  • from functools import reduce 사용할 필요 없이 바로 reduce(…) 사용 가능

Map, reduce, filter

map

1
2
3
4
5

class map(object)
 |  map(func, *iterables) --> map object
 |  
 |  Make an iterator that computes the function using arguments from
 |  each of the iterables.  Stops when the shortest iterable is exhausted.

map은 함수를 iterable한 list, tuple, set, dictionary 등에 대해서 원소별 결과를 모아서 return해준다. 따라서 function의 경우, input argument의 경우 1개인 함수만 사용 가능하다.

함수는 labmda를 사용하여 anonymous fucntion을 넘겨주어도 좋고, def를 사용해서 함수 변수를 사용해도 된다.

example

1
2
3
4
5
6
7
8
9
10

def square1(x):
  return x**2
square2 = lambda x:x**2
arr = list(range(5))
list(map(lambda x:x**2, arr))
list(map(square1, arr))
list(map(square2, arr))
# [0, 1, 4, 9, 16]

reduce

1
2
3
4
5

reduce(...)
    reduce(function, sequence[, initial]) -> value
    Apply a function of two arguments cumulatively to the items of a sequence,
    from left to right, so as to reduce the sequence to a single value.

reduce는 map과 달리 여러 iterable한 elem들을 한 개로 쭉 모아주는 역할을 수행할 수 있다. 2개씩 모아서 함수를 수행하므로, input argument가 2개인 함수만 사용이 가능하다.

예를 들어서 아래와 같이 * operator를 누적하면 factorial을 만든다던가, accumulated sum를 간단하게 구현할 수 있다.

1
2
3
4
5
6
7
8
9
10
11

from functools import reduce
def fact(n):
  return reduce(lambda x,y:x*y, range(1,n + 1))
def accSum(n):
  return reduce(lambda x,y:x+y, range(1,n + 1))
print(fact(5))
# 120
print(accSum(10))
# 55

filter

zip, unzip

zip

unzip

multiprocessing pool function in Python built-in

1
2
3
4
5
6
7
8
9
10
11
12

def f(x):
    return x*x
if __name__ == '__main__':
    t = timer()
    pool = ThreadPool(processes=1)              # start 4 worker processes
    result = pool.apply_async(f, [10])    # evaluate "f(10)" asynchronously
    print (result.get(timeout=1))           # prints "100" unless your computer is *very* slow
    t.timerStart()
    a = pool.map(f, range(10**6))         # prints "[0, 1, 4,..., 81]"
    t.timerEnd()

여기서 결과가 이상하다. 맥북 에어의 문제인지는 확인이 필요할 듯

1
2

process=1
# 0.329390287399292 sec elapsed

1
2

process=2
0.35915374755859375 sec elapsed

1
2

process=4
0.3417470455169678 sec elapsed

https://gist.github.com/huklee/9685eba85d9cce172619bae14c9191c6

further questions

프로세스를 늘려도 더 느려지기만 하지, 전혀 빨라지지 않는다. 너무 가벼운 연산이라 그런가? 아니면 context switching 하는 데 cost가 더 비싼 연산이라 그런가? CPU가 i5라서 문제인가? 현재 너무 많은 프로그램을 쓰고 있어서 memory가 딸려서 그런 문제인가? 다른 machine에서 돌려봐야 알 것 같다.

using a pool of workers

Mini mapreduce framework for python

Pool Example

• in this example, why is the code bad for parallel processing?

Parallel MapReduce in Python in Ten Minutes

Pydoop

Google octopy

useful links

Is there a simple Python map-reduce framework that uses the regular filesystem?

Streaming mapreduce in Python

a biginner’s guide on Hadoop by Matt. Rathbone

MIT Big data 수업에서의 Mapreduce in Python on AWS

Top users

Jake Wharton

#Java #Butter_knife
https://github.com/JakeWharton

Chris lattner

#Swift #Apple
https://github.com/lattner

Chris Banes

#Java #Anroid #Pallete
https://github.com/chrisbanes

Takayama Fumihiko

#C++ #Karbiner
https://github.com/tekezo

Donne Martin

#python #ipython #gitsome #saws
https://github.com/donnemartin

Kenneth Reitz

#python #requests #python-guide
https://github.com/kennethreitz

Armin Ronacher (mitsuhiko)

#python #flask #pallets
https://github.com/mitsuhiko

Usefult links

python git awards
Java git awards
javascript git awards

Skia

Skibitmap overview

안드로이드, 크롬에서 사용되는 google에서 support하는 2D graphic library이다. 주요 지원되는 파일 종류는 BMP, GIF, ICO, jpeg, png, bmp, ebp 등이다. Google에서 관리하고 운영되는 open source이다.

Skia is an open source 2D graphics library which provides common APIs that work across a variety of hardware and software platforms. It serves as the graphics engine for Google Chrome and Chrome OS, Android, Mozilla Firefox and Firefox OS, and many other products.
Skia is sponsored and managed by Google, but is available for use by anyone under the BSD Free Software License. While engineering of the core components is done by the Skia development team, we consider contributions from any source.

Performance & support

방대한 그래픽 라이브러리라서 API 쓰는 방법 자체도 조금 만만치 않고, 일반 사용자용은 아닌 것으로 보인다. 대부분의 third-party가 native한 그래픽 decode library인 libpng, libjpeg, libwebp 등을 쓰고 있어서 성능은 거의 최강급으로 보인다.

In skia/include/images/SkImageDecoder.h file, there is the image list decoding supported by Skia:

1
2
3
4
5
6
7
8
9
10
11
12

enum Format {
    kUnknown_Format,
    kBMP_Format,
    kGIF_Format,
    kICO_Format,
    kJPEG_Format,
    kPNG_Format,
    kWBMP_Format,
    kWEBP_Format,
    kLastKnownFormat = kWEBP_Format
};

간단한 사용방법

파일을 bitmap으로 최종변환하기 위해서는 내부적으로 정의된 SkBitmap 클래스를 사용해서 decoding을 해야 한다. 추후에 샘플 코드를 작성해서 올리도록 하겠다.

Useful links

Skia Graphics Engine Wikipedia
Skia official page
Sk codec test page
Skbitmap test page

Useful links

• Architecture references
  Google Architecture

  Big Data Architecture

  Google Cloud Platform Architecture

  Analytical pipeline architecture

  All about Google Analytics

  Emerging Data Stack

  Hadoop Echo system

• Videos
  What is Google analytics?

leetcode problem solving

https://leetcode.com/problems/validate-binary-search-tree/

Following two solutions are simple to solve this problem.

• Solution A. BST should maintain the following features.

  1. for any node, all values of nodes in the left subtree should be smaller than the node.
  2. for any node, all values of nodes in the right subtree should be bigger than the node.

• Solution B. if the tree accepted following features,

  1. the maximum value of the left subtree is smaller than the parent node.
  2. the minimum value of the right subtree is bigger than the parent node.

Solution A is the key idea of latter solution with child comparison.
Solution B is the key idea of former solution with root comparison.

Here’s my C++ implementations of the solutions.

Min / Max validation with root comparison O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// ======================= Root comparison approach ============================
class BSTinfo{
public:
  bool isValid;
  int maxVal;
  int minVal;
  BSTinfo(bool is, int minV, int maxV) : isValid(is), maxVal(maxV), minVal(minV){};
};
BSTinfo isValidBSTinfo(TreeNode* root){
  // 00. edge & base cases
  if (root == nullptr)
    return BSTinfo(true, -1, -1);
  if (root->left == nullptr && root->right == nullptr)
    return BSTinfo(true, root->val, root->val);
  // 01. in case one subtree is a leaf node
  if (root->left == nullptr){
    BSTinfo rInfo = isValidBSTinfo(root->right);
    if (rInfo.isValid && root->val < rInfo.minVal)
      return BSTinfo(true, root->val, rInfo.maxVal);
    return BSTinfo(false, -1, -1);
  }
  if (root->right == nullptr){
    BSTinfo lInfo = isValidBSTinfo(root->left);
    if (lInfo.isValid && lInfo.maxVal < root->val)
      return BSTinfo(true, lInfo.minVal, root->val);
    return BSTinfo(false, -1, -1);
  }
  // 02. other cases
  BSTinfo lInfo = isValidBSTinfo(root->left);
  BSTinfo rInfo = isValidBSTinfo(root->right);
  if (lInfo.isValid && rInfo.isValid){
    if (lInfo.maxVal < root->val && root->val < rInfo.minVal)
      return BSTinfo(true, lInfo.minVal, rInfo.maxVal);
  }
  return BSTinfo(false, -1, -1);
}
bool isValidBST(TreeNode* root) {
    return isValidBSTinfo(root).isValid;
}

Min / Max validation with child comparison O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// ======================= Child comparison approach ===========================
bool isValidBST_(TreeNode* pNode, TreeNode* minNode, TreeNode* maxNode){
  // 00. base case
  if (pNode == nullptr)
    return true;
  // 01. edge cases : in case one subtree is invalid
  bool isLeftInvalid = minNode && minNode->val >= pNode->val;
  bool isRightInvalid = maxNode && maxNode->val <= pNode->val;
  if (isLeftInvalid || isRightInvalid)
    return false;
  // 02. other cases
  bool isLeftValid = isValidBST_(pNode->left, minNode, pNode);
  bool isRightValid = isValidBST_(pNode->right, pNode, maxNode);
  return isLeftValid && isRightValid;
}
bool isValidBST(TreeNode* root) {
    return isValidBST_(root, nullptr, nullptr);
}

Useful links

bunsanzi visitor counter
tea3 popular posts
issan hexo theme