DB selection

https://www.youtube.com/watch?v=cODCpXtPHbQ

• Structured data
  • yes
    • Need ACID
      • RDBMS(yes): mysql, orcle, sql server, postgres
  • no
    • Ever increasing data && + finite queries -> Columnar DB: Cassandra, HBase
    • ++ Data types && ++ queries -> document DB: mongoDB, Couch Base

interesting example: At ecommerece site, we shouldn’t sell more than the remaining quantity. it should support ACID. so we can use SQL before placing order. but once order is created, then you can use MongoDB to save the data.

Requirements

functional:

• allowRequest(request)

non functiona:

• low latency
• accurate
• scalable
• highly available since we can assume that default is allow the request if the throttling service is not available.

request processing

token bucket algorithm

one of the popular algorithm for rate-limiting algorithm.

interfaces and classes

• JobSceduler: fetch rules from RuleService periodically
• RulesCache: store token bucket objects
• ClientIdentifier: identify client form the request
• RateLimiter: provide allowRequest() api

Distributed world

as we move to distributed world, we need to share local remaining tokens to other hosts.

message boarcasting

possible approaches:

• Tell everyone everything: not scalable, message grows quadratically
• gossip communication
• distributed cache cluster
• coordination service: one host takes coordination leader role. Paxos, Raft
• random leader selection

TCP VS UDP

TCP: slow, accuracy, order guaranteed
UDP: fast, not reliable, order not guaranteed

How to integrate all this with the service?

final look

Reference

• https://www.youtube.com/watch?v=FU4WlwfS3G0&t=815s

Requirements

functional

• topK(k, startTime, endTime)
• scalable
• available
• highly performant: few ten milliseconds to return top 100 list
• accurate

single host approach

• build hashTable<Key, Count>
  • sort the whole list: O(nLog(n))
  • use heap: O(nLog(k))

but it’s not scalable.

Hash table, multiple hosts

you can scale previous approach by using data paritioner. scalability and througput has been addressed.

But streaming data is not bounded. It has infinite data. what if we need to calculate top K for a day or a week?

count-min sketch, multiple hosts

There is well-known data structure called count-min sketch, kind of approximation algorithm, which guarantees fixed memory usage. basically it tradedoff between accuracy and memory.

count-min sketch uses 2 dimensional array, each row is different hash function, column is count. whenever new event comes in, calculate hash value for each row, and increment the value of the cell by 1. This means that it could have collision, that’s why we take the smallest value as a result.

But this doesn’t give us accurate top K lists. if constraints don’t allow inaccuracy, then we need a different approach.

high level design

Reference

• https://www.youtube.com/watch?v=kx-XDoPjoHw
• http://nathanmarz.com/blog/how-to-beat-the-cap-theorem.html

Requirements

Functional:

• put(key, value)
• get(key)

Non-Functional:

• Scalable
• highly available(survives hardware/network failures)
• highly performant(fast put/get)

LRU Cache

The basic data structure for cache would be hash table since it provides O(1) time complexity for put/get operation. So far so good.

One machine has finite memory capacity so we can’t put keys endlessely. If the cache is full, we need to delete existing data so that we can add new one. Then which key should be evicted(deleted)? This is called cache eviction(replacement) policy. The most popular one is Least recently Used(LRU).

LRU discards the least recently used items first. So the algorithm needs to keep track of access time of the items.

Order can be easily expressed by linked list and cache is basically hash table. Then we can combine these two into one data structure, called Linked Hash Table.. basic idea is whenever the key is accessed, we add the item into head of the list. Then the tail of the list will be always the one last accessed, which is the target item to be removed when capacity is full.

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
44
45
46
47
48
49
50
51

class Node{
  private final String key;
  private String value;
  private Node prev, next;

  public Node(String key, String value){
    this.key=key;
    this.value=value;
  }
}

class LRUCache{
  Map<String, Node> map;
  int capacity;
  NOde head = null;
  Node tail = null;

  private deleteFromList(Node node){

  }

  private setListHead(Node node){

  }

  public put(String key, String value) {
    if(map.containsKey(key)){
      map.get(key).setValue(value);
      deleteFromList(node);
      setListHead(node);
    } else{
      if(map.size()>=capacity){
        map.remove(tail.getKey());
        deleteFromList(tail);
      }
      Node node = new Node(key,value);
      map.put(key, node);
      setListHead(node);
    }
  }

  public String get(String key){
    if(!map.containsKey(key)){
      return null;
    }
    Node node = map.get(key);
    deleteFromList(node);
    setListHead(node);
    return node.getValue();
  }
}

2 possible approaches

dedicated cache cluster

• isolation of resources between service and cache
• can be used by multiple services
• flexibility in choosing hardware

  co-located cache

  cache service is co-located with the service host.
• No extra hardware and operation cost
• scales together with the service

choosing a cache host

Definitely one cache host can’t server all the items. They need to be split across multiple hosts by hash of key of the item. How keys can be distributed?

MOD

Cache host number = hash_function(key) MOD #hosts

mod operator would be the most easy one to implement but it has obvious weakness. entire cache need to be rewritten whenever a new host is added or deleted. Generally this kind of overhead is not acceptable in production environment.

Consistent hashing

consistent hashing is basically placing host on a circle. 12 oclock will be value 0 or 2^32. the point will be mapped to the point on the circle boundary based on the hash value. for example 2^32/4 will be mapped to 3 o’clock. we will place cache host along the circle with even distance. the keys between the two hosts belong to the first clockwise host.

1
2
3
4
5

before:
H1 --- H2 --- H3 --- H1

after:
H1 --- H2 --- H2.5 --- H3 --- H1

Let’s say we added H2.5 between H2 and H3. then the affected hosts are H2 and only. very limited blast radius compared to the MOD approach.

Cache client

cache client knows about all cache servers. all cache clients should have the same list of servers. It stores list of servers in sorted order. just like TreeMap in java. binary search is used to identify server, which is O(logn). It uses TCP or UDP protocol to talke to servers. If cache server is unavailable, client proceeds as if it was a cache miss.

maintaining a list of cache servers

• use configuration file in local host
• use external file like S3
• use configuration service like ZooKeeper
  • config service will check heartbeat with all the cache hosts. if it fails it will be deleted from the cache list

high availability

hot shard problem can be solved by replication.

there are two categories of data replication protocols.

• a set of probablistic protocol -> eventual consistency
  • gossip
  • epdemic broadcast
  • trees
  • bimodal multicast
• consensus protocol -> strong consistency
  • 2 or 3 phase commit
  • paxos
  • raft
  • chain replication

master-slave replication

what else?

• consistency. The consistency issues can happen. consistency can be achieved by performing synchronous replication. but this will introduce additional latency and overall complexity of the system. so it’s heavily depends on the service requireemnts.

• data expiration. The data can be expired after some time later depends on business requiremetns. If that’s the case we can schedule a batch job to remove expired keys. Or passively delete expired cache on a regular basis.

• Local cache can be used on the clinet library side. LRU cache or Guava cache can be used.

• Security.
  • firewall
  • encrypt the data
• monitoring and loggin
  • number of errors, latency, cache hit/miss, cpu, memory
• cache client
  • maintain a list of cache servers
  • pick a shard
  • remote call
  • delegate many responsibilities to proxy, ref twemproxy project
    or make cache servers responsible for picking a shard
• consistent hasing has 2 flaws. domino effect and not split the circle evenly-> add server on the circle multiple times

Reference

• https://youtu.be/iuqZvajTOyA
• TCP vs UDP, https://www.geeksforgeeks.org/differences-between-tcp-and-udp/

requirements

Functional

• sendMsg(messageBody)
• receiveMessage()

Non-functional

• scalable(handles load increases, more queues, and messages)
• highly avaiable(survive hardware/network failures)
• performant(single digit latency for main operations)
• durable(once submitted, data is not lost)

High-level architecture

VIP and Load balancer

VIP can be SPOF. so VIP partitioning is required.

FrontEnd Service

• a lightweight web service
• stateless service deployed across several data centers

Functions

• request validation
  • required parameters are present
  • data falss within an acceptable range
• Authentication/Authorization
  • validating identity of a user of a service
• TLS(SSL) termination
  • SSL on the load balancer is expensive
  • termination is
• Server-side encryption
• Caching
• Rate limiting(Throttling)
  • leaky bucket algorithm
• request dispatching
  • circuit breaker pattern prevents an application from repeately trying to execute an opertion that will be likely to fail
  • bulkhead pattern helps to isolate elements of an application into pools so that if one fails, the other will continue to function.
• request depulication
  • may occur when a successful sendMessage fails to reach a client.
• usage data collection
  • billing/ realtime usage

Metadata service

• caching layer between frontend and a storage
• many read, little writes
• strong consistency storage preferred

backend service

• where and how do we store message? -> RAM and local disk
• how do we replicate data?
• how does FrontEnd select a backend host to send data to? Metadata service
• how does frontend know where to retrive data from? Metadata service

Option A: Leader-follower relationshiop

OPtion B:

comparions OPtion A/B :

What else is important

• Queue creation and deletion
• message deletion
  • do not delete message. it can be deleted by batch job
  • consumer needs to call deleteMessae
• message replication
  • async replication: low latency. how to sync when one host is down?
  • sync replication: high latency. hit consistency
  • hard to achieve exactly once delivery
• push vs pull
• FIFO. doesn’t guarantee the strict order of the message
• security: encrypte messages
• monitoring

final look

DB selection

https://www.youtube.com/watch?v=cODCpXtPHbQ

• Structured data
  • yes
    • Need ACID
      • RDBMS(yes): mysql, orcle, sql server, postgres
  • no
    • Ever increasing data && + finite queries -> Columnar DB: Cassandra, HBase
    • ++ Data types && ++ queries -> document DB: mongoDB, Couch Base

interesting example: At ecommerece site, we shouldn’t sell more than the remaining quantity. it should support ACID. so we can use SQL before placing order. but once order is created, then you can use MongoDB to save the data.

Reference

interesting topics during design pattern lectures

implmenetation by intentions

1
2
3
4
5
6
7
8
9

public void printReport (String CustomerID) { 
    if(!isValid(CustomerID)) throw new ArgumentException(); 
    Employee[] emps = getEmployees(CustomerID);
    if(needsSorting(emps)) 
        sortEmployees(emps); 
    printHeader(CustomerID);
    printFormattedEmployees(emps);
    printFooter(CustomerID);
}

one public method contains multiple private methods fulfilling one specifc logic at a time. it’s your logical sequences when you implement printReport in your head. by doing this you can achieve

• Method cohesion
• separation of concerns
  • sergeant method: calls other methods
  • private methods: implementing code
• clarity - clear code is better than comments
• easy in finding/forming certain patterns
• no extra work is required

Commonality-Variability Analysis, CVA

Assume you start a new project solving software problem in a certain domain. you heard bunch of requirments from your clients. how would you find a entities, create an abstraction with whom, find a suitable patterns among them.

at this time CVA can help you

requirements

• US Tax
• Canadian PST, GST
• Validation of addresses strcuture in different locations

from this requirments you can derive a following potential entities and abstractions.

examle of CVA:

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

Country
----
US
Canada

Tax
-----
Canadian Province
Canadian Fed
US

AddressValidation
------
US
Canada

Privacy Policy

nberserk built the WordGrep app as a Free app. This SERVICE is provided by nberserk at no cost and is intended for use as is.

This page is used to inform visitors regarding my policies with the collection, use, and disclosure of Personal Information if anyone decided to use my Service.

If you choose to use my Service, then you agree to the collection and use of information in relation to this policy. The Personal Information that I collect is used for providing and improving the Service. I will not use or share your information with anyone except as described in this Privacy Policy.

The terms used in this Privacy Policy have the same meanings as in our Terms and Conditions, which is accessible at WordGrep unless otherwise defined in this Privacy Policy.

Information Collection and Use

For a better experience, while using our Service, I may require you to provide us with certain personally identifiable information, including but not limited to name. The information that I request will be retained on your device and is not collected by me in any way.

The app does use third party services that may collect information used to identify you.

Link to privacy policy of third party service providers used by the app

• Google Play Services
• Google Analytics for Firebase

Log Data

I want to inform you that whenever you use my Service, in a case of an error in the app I collect data and information (through third party products) on your phone called Log Data. This Log Data may include information such as your device Internet Protocol (“IP”) address, device name, operating system version, the configuration of the app when utilizing my Service, the time and date of your use of the Service, and other statistics.

Cookies

Cookies are files with a small amount of data that are commonly used as anonymous unique identifiers. These are sent to your browser from the websites that you visit and are stored on your device’s internal memory.

This Service does not use these “cookies” explicitly. However, the app may use third party code and libraries that use “cookies” to collect information and improve their services. You have the option to either accept or refuse these cookies and know when a cookie is being sent to your device. If you choose to refuse our cookies, you may not be able to use some portions of this Service.

Service Providers

I may employ third-party companies and individuals due to the following reasons:

• To facilitate our Service;
• To provide the Service on our behalf;
• To perform Service-related services; or
• To assist us in analyzing how our Service is used.

I want to inform users of this Service that these third parties have access to your Personal Information. The reason is to perform the tasks assigned to them on our behalf. However, they are obligated not to disclose or use the information for any other purpose.

Security

I value your trust in providing us your Personal Information, thus we are striving to use commercially acceptable means of protecting it. But remember that no method of transmission over the internet, or method of electronic storage is 100% secure and reliable, and I cannot guarantee its absolute security.

Links to Other Sites

This Service may contain links to other sites. If you click on a third-party link, you will be directed to that site. Note that these external sites are not operated by me. Therefore, I strongly advise you to review the Privacy Policy of these websites. I have no control over and assume no responsibility for the content, privacy policies, or practices of any third-party sites or services.

Children’s Privacy

These Services do not address anyone under the age of 13. I do not knowingly collect personally identifiable information from children under 13. In the case I discover that a child under 13 has provided me with personal information, I immediately delete this from our servers. If you are a parent or guardian and you are aware that your child has provided us with personal information, please contact me so that I will be able to do necessary actions.

Changes to This Privacy Policy

I may update our Privacy Policy from time to time. Thus, you are advised to review this page periodically for any changes. I will notify you of any changes by posting the new Privacy Policy on this page.

This policy is effective as of 2020-09-02

Contact Us

If you have any questions or suggestions about my Privacy Policy, do not hesitate to contact me at wordgrep@gmail.com.

rake is Makefile for ruby world. I am not big fan of Ruby but I like Rake as a task execuion library.

task defintion & dependency

1
2
3
4
5
6
7

task :A do
    sh "echo A task executed"
end

task B: [:A ] do
    sh "echo A task executed"
end

find directory where rake is invoked.

sometimes, maven or gradle build command should be executed at project root directory. but current directory is changed by Rake where the Rakefile is located. so build command would fail by that reason. in this case we can get the origial directory by using the following Ruby APIs.

1
2
3
4
5

dir = Rake.application.original_dir
Dir.chdir(dir) do
    sh "mvn"
    sh "gradle"
end

two useful command line tools. highly recommen to use those.

fzf - fuzzy finder

see this video : https://www.youtube.com/watch?v=qgG5Jhi_Els

https://github.com/junegunn/fzf

ripgrep

whenever I need to use grep, I have to find the right syntax on the web. It’s because the syntax is not intuitive at all. but after switiching to ripgrep, no more search is required.

https://github.com/BurntSushi/ripgrep

1

rg 'fn write\('

When you are working with remote compute, usally you use SSH. It is secure and easy. but when you are working with long running task, your ssh session will be disconnected. to prevent this kind of inproductivity, tmux comes in.

session

tmux has session. this session will be persistent as long as the remote computer is alive. You can completely restore your context-command histroy, current directory, running progrm.

1
2
3
4
5
6

tmux new -s default # new session
tmux ls 

tmux attach -t <session>
tmux> quit # terminate session
tmux> tmux detach # detach current session. session is not terminated

window

pane

window can be splitted into several panes. tmux can store/restore panes.

1
2
3

prefix + \" : split active pane horizontally
prefix + arrow key : switch to another pane
prefix + o : move to next pane

shortcut

1
2

prefix : ctrl + b
prefix + d : detach session

screen scroll

prefix + [ will initiate scroll move mode. you can use down/up, /(keyword search), pageup/pagedown to move your scren buffer. by pressing ‘q’ or ‘enter’ you can termiate this mode.

iTerm2 integration

1
2

tmux -CC            # create new tmux session
tmux -CC attach     # attach to existing session