Loading...
Let's assume 100M DAU, 100 searches per day. Each search with 3 words, on average word length is 5 letters.
1. QPS estimation.
READ - So 100M * 100 /24*3600 = 100K/s searches
For each search, the sentence length would be 5(chars) * 3(words) = 15 chars, then we will have 100K/s * 15 = 1.5M/s requests for suggestions.
Peak READ QPS x5 = 7.5M/s raw requests.
WRITE - assuming we sample 10% searches to log, that is 10k/s write.
Of course, this is READ heavy system for user query path and we should optimize more for READ requests than WRITE.
2. Storage estimation. There are roughly 200K English words in total. For each word, there are 5 entries for prefixes, such as for "apple", there are prefixes like "a", "ap", "app", "appl" and "apple".
suggestions?q=a
suggestions?q=ap
suggestions?q=app
suggestions?q=appl
suggestions?q=apple
We need 5 * 200K entries to store the results for around 5*200K = 1 million entries.
1 millions * (5 bytes for word prefix + 5*10 bytes for suggestions) = 55 MB
This could in theory be stored in memory. so we could cache in memory (Redis).
This will return top 10 suggesitons as JSON to be displayed in the UI.
This will log the word search history and increase the count of the given word that has been searched.
The DB schema is like with prefix as partition key, the value is word list with top 10 pairs of (word:score) with the top score, saying:
{
"a", [("apple", 89), ("application":55), ("amazon":40),...], lastUpdateTimestamp.
"ap", [("apple", 89), ("application":55), ("apache":35),...], lastUpdateTimestamp.
"app", [("apple", 89), ("application":55),("appoint", 33),...], lastUpdateTimestamp.
}
......
We return the word,score pairs to tell the rank per the score. There is ranking service running in the background
Besides the prefix and (word,score) list, we use the lastUpdateTimestamp to decide when the entry should be expired later on.
{
2024/11/1/09:00, "apple", 50
2024/11/1/10:00, "apple", 16
2024/11/2/06:00, "boy", 29
2024/11/2/07:00, "apple", 2
}
Let's break down the system:
Query Path:
Update Path:
Here’s a basic conceptual implementation of a TF-IDF based ranking algorithm that could replace the rudimentary scoring system in Redis.
Here’s a basic conceptual implementation of a TF-IDF based ranking algorithm that could replace the rudimentary scoring system in Redis.
import math
from collections import defaultdict
Example data
documents = {
"doc1": "apple banana apple",
"doc2": "banana orange",
"doc3": "apple orange apple banana"
}
def compute_tf(doc):
tf = defaultdict(int)
words = doc.split()
for word in words:
tf[word] += 1
for word in tf:
tf[word] /= len(words)
return tf
def compute_idf(docs):
idf = defaultdict(float)
N = len(docs)
for doc in docs.values():
for word in set(doc.split()):
idf[word] += 1
for word in idf:
idf[word] = math.log(N / idf[word])
return idf
Compute TF for each document
tf = {doc: compute_tf(content) for doc, content in documents.items()}
Compute IDF across all documents
idf = compute_idf(documents)
Compute TF-IDF
tf_idf = defaultdict(dict)
for doc, tf_values in tf.items():
for word, value in tf_values.items():
tf_idf[doc][word] = value * idf[word]
Display TF-IDF values
print(tf_idf)
With this technique, dynamically generated suggestions can leverage historical term frequency in user queries to promote terms relevant to ongoing sessions.
INSERT INTO hourly_data (timestamp, word, value, frequency) VALUES
('2024-11-01 09:00:00', 'apple', 50, 'hourly'),
('2024-11-01 10:00:00', 'apple', 16, 'hourly'),
('2024-11-02 06:00:00', 'boy', 29, 'hourly'),
('2024-11-02 07:00:00', 'apple', 2, 'hourly');
// Below are python code to aggregate hourly data to daily data.
from cassandra.cluster import Cluster
from datetime import datetime
from collections import defaultdict
Connect to Cassandra cluster
cluster = Cluster(['127.0.0.1']) # Replace with your Cassandra nodes
session = cluster.connect('your_keyspace') # Replace with your keyspace
Query the data from the hourly_data table
query = "SELECT timestamp, word, value FROM hourly_data"
rows = session.execute(query)
Initialize a dictionary to aggregate daily data
daily_data = defaultdict(lambda: defaultdict(int))
Aggregate hourly data into daily data
for row in rows:
# Extract date part from timestamp and convert to date string
date = row.timestamp.date() # Get only the date part (year-month-day)
word = row.word
value = row.value
# Sum the values for each category and date
daily_data[date][word] += value
Output aggregated daily data
for date, words in daily_data.items():
for category, total_value in words.items():
print(f"Date: {date}, Category: {category}, Total Value: {total_value}, Frequency: 'daily'")