Case study: Social graph - search shortest path in the graph

 Here is the gist. 

	This editor is synced in real time with your peer.
	Use it to share thoughts and resources, such as:
	- Features scope
	- API design
	- Pseudo code for specific components
	- Data model/schema
	- Back-of-the-envelope calculations
	- Reference links
	- Link to whiteboard or diagram such as https://sketchboard.me/new
	Good luck!
	Features: add freind
	LOok up freind's freind
	all you freind
	termniate
	Search - network, public figure - brute force
	Closest_step
	API design:
	AddFriend
	Terminate
	GetAllFreinds
	FindPathGivenTwoFreind()
	Friend-UID , name,
	FindPath - BFs -> shortest path - BFS - 200 social graph -> 200 -> friend - mark visit-> 200^5 = 10^10 -> billion
	10% populatuion - 5 billion on this graph -
	# source node (ID, name)
	# friends (ID, name)
	# Bob -> Andrew -> Dylan
	search(Bob) -> [Bob -> Andrew -> Dylan]
	search service -> all search queust -> Messge queue -> More than service, parsing, language, search search -> cache -> datbase / NO SLQ / oj
	cache - shard -> consistent hashing -
	single point failure - replication -> cache server ->
	Static - CDN
	CAP - reading - consistent -> latest / high availablity/ less consitent. partition tolerant ->
	100 -> break new relationsip -> circle
	search -> read service/ write service -> Message queue
	Key - value -> a person with all friend
	Facebok DAO -> Look aside - write through - make consistent - client
	cache serve -> load datastore -> cache - DAO - memcache -
	a user -> put level 3 freinds -> preprocess - level -> a node 200^3 = 800000 friend -> space sacrifice -> short -> search source/ destination -> optimize
	Data model/ schema
	Facebook - a freidn take picture at californai bridge - Alice likes the photo -> comment
	freind/ picture/ calfifor bridge / comment/ phot
	comment (useID, time , location, from, to )
	a lot of edges in graph
	graph model
	so many friends -> inteligent -> brute force
	multiple - time-close -> multiple - which one
	Find name -> similar ->
	search by name
	advanced search -
	Database -> use information - name, time to regist, location, email addre
	NoSQL - graph -
	static
	Cache - 30 days - special
	Analysis - search
	API - search
	query API - name -> last, firstname -> language, extra space, wrong char -> refine, -> name -> cache -> relation ship - by monthly
	200 -> 200 -> 40000 -> Alice ->
	https://www.geeksforgeeks.org/bidirectional-search/#:~:text=In%20normal%20graph%20search%20using,form%20source%20to%20goal%20vertex.

view raw SearchFindshortestPathFriend hosted with ❤ by GitHub