Loading...
functional requirements
business onwer can add/update/delete businesses
user can search nearby businesses with given radius
user can specify 0.5km, 1km, 3km, 5km
sort the result by a ranking model
non functional requirements
CAP p is must
Availability: high availability, able to handle peak traffic
Consistency: eventually consistency
latency: low latency for search
Scalability: the design can be scaled horizontally
Capacity
100M DAU, each user search 5 times every day
10M business in total, 10k business is created everyday
search qps: 100M * 5 / 10 ^ 5 = 5000/s
write tps: 10k / 10 ^ 5 = 0.1/s
every bussiness takes 300B text, 10MB image(in CDN or Object storage)
bandWidth
5000/s * 300B * 10 = 15GB/s
Storage
300B * 10M = 3GB for metadata
10MB * 10M = 100TB for images
api
addBusiness api/v1/business/add
updateBusiness api/v1/business/update/{id}
searchBusiness api/vi/business/search
request
{
userID: 1232,
longitude: 90,
latitude: 90,
radius: 3,
filters:{
"type": "gas"
"status": "open"
}
Pagination:{
"offset": 0,
"size"：10
}
}
response{[{business_1}, {business_2}]}
db schema
business DB (sql)
it bigInt --pk
name char(20)
desc char(256)
latitude double
longitude double
urlList char(1024)
type int //
status int // 0 closed 1 open
createdAt timestamp
updatedAt timestamp
user DB
id bigInt --pk
name char(20)
email char(50)
phone int
createdAt timestamp
updatedAt timestamp
geohash DB
id bigInt --pk
geohash string
businessId bigint
createdAt timestamp
updatedAt timestamp
business serivce: upload/edit business
search serivce: query by filters.
data flow
write
1 owner call upload/update api
2 lb route it to business service
3 upload images to object storage, get image urlList
4 create/update metadata in business db
5 update cache
search
1 user call search api
2 lb route it to search service
3 search service call geohash cache,
get business idlist of 9 geohash code to handle boundary issue
4 if cache miss, call geohash db
5 get businessIdList from cache
6 if cache missed, get it from db, write it to cache
7 search server do filter, call ranking service to rank results
8 return business list to user.
9 user download image from CDN
geohash
len size
4 40km * 20km 10km
5 5km * 5km 1km, 3km, 5km
6 1.2km * 0.6 0.5km
quadtree
1 memory data structure, load it to memory costs
lot of time.
2 dynamically adjust node size according to business density
It's useful to get k-nearest neighbours
3 it's difficult to update, takes O(logn) time, have to consider
rebalance.
db usage:
business db: highly structured, low write qps, acid required, so use sql.
geohash db:low write qps, acid required, so use sql.
why db doesn't store goehashIdlist in db?
we store 3 geohash record for every business,
update/add the json has concurrency issue.
business service: upload image to object storage
cache: use redis
geohash cache: key geohash, value: businessId set
business cache: key busineesId
value: business json
trade off
geohash vs quadtree
geohash
1 easy to implement, no need to build a tree
2 support search by radius
3 Easy to update
scalability
server: stateless can easily scale
db: shard geohash by geohash code or business id
by geohash code
pros: query db in one shard
cons: hotkey issue: one area too dense
by business id
pros: reduce hotkey issue
cons: query db in all shards
single point failure
db: 2 slaver for each master in shards
for hot shards, have more slavers
master down: slaver become new master
slaver down: sync from master via binlogs
server: stateless, easy to scale
lb: send heart beat to each other. If one lb down, others can be backup