0% completed
Designing Typeahead Suggestion
Every case study in this chapter follows the same seven steps from System Design Interviews: A step by step guide, and builds its design from the components in the System Design Master Template. Keep both open beside you, and try each problem yourself before reading the solution.
.....
.....
.....
Jeremiah Stones
· 4 days ago
I’d like to gently challenge the assertion that "there is no way to write a reference to a node that has not been built yet." This is a limitation of this specific single-pass, text-stream format, not an engineering impossibility.
In practice, you can easily serialize references using node indexing or deferred resolution:
-
Index Mapping: If nodes are assigned sequential IDs based on CSV position (0: C2, 1: A2), references like top-K candidates can be serialized as array indices (e.g., C2[1:22]). During deserialization, a 2-pass read or an array lookup resolves these indices to node references.
-
Relative Offsets / Zero-Copy: Formats like FlatBuffers solve this by constructing nodes bottom-up (leaf-first) and storing position-independent relative byte offsets. This allows d
jerrytansk
· 2 months ago
instead of dealing with tries and serialization and deserialization into a file format for persistence on disk and all that, why don't we just drop in a elasticsearch cluster. It supports prefix based queries and takes care of all these problems for you, at scale. The drawback is the additional complexity it requires, but any production system at scale would require a system as complex as elasticsearch anyway.
Jessie
· 3 years ago
I'm just curious why this system design would go through the process of building up and storing trees over and over vs using an existing implementation of a graph based database? The only thing I can really come up with is maybe some added efficiency by having data in memory and the access time of a db being potentially a bit slower, but it seems like they might also have some built in efficiencies that you may not be able to, or knowledgeable enough to recreate.
CQ
· 4 years ago
Why can't we use hash table of prefixes to achieve the same thing (instead of using trie)? We can have a word hash table storing (word, count) and a prefix hash table storing (prefix, top 10 reference to (word, count)). Each time we need to do an update, we first do a word table update. Let's say we have (CAPTAIN, 10) becoming (CAPTAIN, 11) Then we just enumerate all the prefixes of this word (for example, for CAPTAIN, we enumerate C, CA, CAP, CAPT ..) and then check if (CAPTAIN, 11) made to top 10. If yes, replace that row of the prefix table When we query, we just fetch one single row from prefix table. We can do batch offline update & partitioning similarly (probly even easier this way) and the rows that we need for prefix table is about the same as the node of tries.
Junaid Effendi
· 4 years ago
Isn't this true for all types of partitioning?
""" Partitioning based on the maximum capacity can still lead us to hotspots, e.g., if there are a lot of queries for terms starting with ‘cap’, the server holding it will have a high load compared to others. """
Even with hash, cap will produce same hash thus same server so hotspot can still occur?
Reading Progress
0%