1. single machine single thread
- start from a pool of URLs
- issue HTTP get the URLs
- parse the URL get and identify URLs we want to crawl further
- add the new URLs into pool and keep crawling / no duplicate - bloom filter
2. crawling policy
- how often to retrieve the crawled page?
- robot.txt
3. de-dup
bloom filter
4. parse
5. dns - bottle neck
Reference:
http://blog.gainlo.co/index.php/2016/06/29/build-web-crawler/
Design and Implementation of a High-Performance Distributed Web Crawler
Jul 5, 2016
Jul 4, 2016
Design random id generator
requirements:
- id limited to 64 bits
- id is increased by date
single machine
- integer? hard to scale to multiple server case
one ticket server
- bottle neck
multiple server
-each server with a id / o ruse mac address
-guid: random or mac+timestamp
- twitter's snowflake
clock synchronization
-NTP
reference:
http://www.slideshare.net/davegardnerisme/unique-id-generation-in-distributed-systems
- id limited to 64 bits
- id is increased by date
single machine
- integer? hard to scale to multiple server case
one ticket server
- bottle neck
multiple server
-each server with a id / o ruse mac address
-guid: random or mac+timestamp
- twitter's snowflake
clock synchronization
-NTP
reference:
http://www.slideshare.net/davegardnerisme/unique-id-generation-in-distributed-systems
flickr's ticket server: http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
design a cache system
1. LRU cache (leas recent used)
If resource A is request by client
- if A is in cache, return
- if A is not in cache and the cache still have empty slot, read A from disk to cache and return
- if A is not in cache and cache is full, evict the least recent used slot, read A from disk to cache and return
Implement of LRU: cache and double linked list
2. Eviction policy
- random replacement (in ARM architecture)
- LRU
- least frequently used (keep a count for each entry)
- windowed LFU
3. Concurrency: 2 clients want write to the same entry
- lock / section lock
- commit log
4. Distributed cache:
value saves reference to other machine
reference
Memcached http://www.slideshare.net/oemebamo/introduction-to-memcached
https://en.wikipedia.org/wiki/Cache_algorithms
If resource A is request by client
- if A is in cache, return
- if A is not in cache and the cache still have empty slot, read A from disk to cache and return
- if A is not in cache and cache is full, evict the least recent used slot, read A from disk to cache and return
Implement of LRU: cache and double linked list
2. Eviction policy
- random replacement (in ARM architecture)
- LRU
- least frequently used (keep a count for each entry)
- windowed LFU
3. Concurrency: 2 clients want write to the same entry
- lock / section lock
- commit log
4. Distributed cache:
value saves reference to other machine
reference
Memcached http://www.slideshare.net/oemebamo/introduction-to-memcached
https://en.wikipedia.org/wiki/Cache_algorithms
Design facebook
Design the Facebook news seed function
Reference:
Design the Facebook timeline function
Reference:
Design the Facebook chat function
Reference:
- Erlang at Facebook
- Facebook Chat
- http://blog.gainlo.co/index.php/2016/04/19/design-facebook-chat-function/
design a key-value store
1. basic key-value: hash table in memory on single machine. while memory is not enough, a.compress data b.store reference to external/disk file
2. distributed key-value storage
-partition data / sharding
-balance loading
-system availability - replica
-consistency - the commit log, or coordinator holds the latest copy, or cordinator resolve the conflicts on the flyby reading multiple servers
- reading performance: use cache (refer to design a cache system)
refer: http://blog.gainlo.co/index.php/2016/06/14/design-a-key-value-store-part-i/
redis http://www.slideshare.net/dvirsky/introduction-to-redis
http://key-value-stories.blogspot.com/2015/02/memcached-internals-design.html
https://groups.google.com/forum/#!topic/memcached/BA67vpuGQYU
2. distributed key-value storage
-partition data / sharding
-balance loading
-system availability - replica
-consistency - the commit log, or coordinator holds the latest copy, or cordinator resolve the conflicts on the flyby reading multiple servers
- reading performance: use cache (refer to design a cache system)
refer: http://blog.gainlo.co/index.php/2016/06/14/design-a-key-value-store-part-i/
redis http://www.slideshare.net/dvirsky/introduction-to-redis
http://key-value-stories.blogspot.com/2015/02/memcached-internals-design.html
https://groups.google.com/forum/#!topic/memcached/BA67vpuGQYU
design a short url
use cases:
1.Convert convert_to_62based(md5(url)+random())
2.Redirect
3.Delete?
4.Premium/self defined key
5.UI for convert or API?
6.URL expire?
7. Show ads before redirect?
8.scale and performance
100 requests/seconds, 10 convert, 90 redirect
1year new added 365*24*3600*10= 315M entries
each item 500bytes disk. that's 160G bytes. 5year - 1T?
9. more details of implementation - key-value store: Cassandra (https://en.wikipedia.org/wiki/Apache_Cassandra), mySQL or plain text file, memory cache, etc
reference:
http://www.hiredintech.com/system-design/
https://developers.google.com/url-shortener/v1/getting_started
Jun 22, 2016
compile root file system (busybox)
1. Busybox
compiling config
a.
Don’t set the static library.
b.
Should set up the cross compile prefix.
c.
Set ‘Not support big files’
d.
Set ‘Not use local /usr’
2. Compile
busybox
a.
make menuconfig
b.
make
c.
make install
d.
the default installing directory for busybox is
busybox_root/_install
3. If
using initramfs format as rootfs, when compiling kernel we should set up
kernel’s config file to support initramfs. Including the following setting:
CONFIG_INITRAMFS_SOURCE="/home/project/a/busybox/_install" (this
directory _install is from the above step 3)
The above path is rootfs’s directories path.
When compiling kernel, it will create the cpio.gz file
in
kernel_root/usr/initramfs_data.cpio.gz.
At
the same time, the rootfs will be compiled with kernel image. So the file Image
includes kernel and rootfs.
Subscribe to:
Posts (Atom)