Usually, when interviewing for an engineering or software position, you end up doing some sort of “coding challenge”. A friend of mine has recently left the company and is doing one at the moment. He asked me for help on solving a particular challenge, which I felt was a good exercise for me.
This blog post talks a bit about the challenge and my approach to solving it. Also, this post works as a personal reminder that sometimes it is not about picking the best tool, but the right data structure.
“90% of the time, you can solve your problem with just the right data structures” - someone, once, on Reddit probably.
The Challenge
The problem is, and I’m paraphrasing:
“Build a phone information aggregator API. This system takes a list of phone numbers and returns the count of valid phones broken down per prefix and business sector.”
For example, given 5 phone numbers, where 4 of them are valid, the system should return:
- a count of 1 phone for Technology, and 1 phone for Banking associated with the
+1prefix, - and a count of 2 phones for Clothing associated with the
+3519173prefix.
1$ curl -X POST http://localhost:8080/aggregate \
2 -H 'Content-Type: application/json' \
3 -d '["+1983248", "00351917355", "+147 8192", "+351917312", "+ 918851"]'
1{
2 "1": {
3 "Technology": 1,
4 "Banking": 1
5 },
6 "3159173": {
7 "Clothing": 2,
8 }
9}
How to approach the problem
The problem revolves around building an API that exposes the functionality of aggregating phone numbers by industry sector. We can divide it into 4 parts:
- Expose an API through an HTTP Service
- Check if the given phone numbers have valid prefixes
- Interact with an external service to get the corresponding sector
- Serialize the response in the expected format
The interesting part of this problem is the 2nd step, “validate phone number prefix”:
{ "number": "+1", "sector": "Technology" } api->>client: HTTP 200 OK
{ "1": { "Technology": 1 } } deactivate api end deactivate client
Valid phone numbers
Validating a phone number in this context means:
- we have an extensive list of “phone prefixes” (around 900k prefixes) that should be considered the “ground truth”
- and for every given phone number, we want to cross-check against that list, and if valid, make an API call to an external service
1~/projects/phone-validator $ head -n 10 prefixes.txt
21
32
444
53000000
63000001
73000002
83000003
93000004
103000005
113000006
12
13~/projects/phone-validator $ wc -l prefixes.txt
14 900005 prefixes.txt
So for example: If I have the phone number “+1983236248”, and a list of prefixes of [1, 2, 44], the prefix is “+1”.
Getting the prefix sector
To group by “sector” we need to use an external API. The OG challenge gives us an URL to use, but since that would be too much on the nose for what company this challenge is for, I’ll just explain what it does 👀:
- The API has a GET request that goes to “https://a-challenge.company.com/sector/:number" where it returns the corresponding industry sector. For example: given the number
+98 72 349, which belongs to a company in the Banking sector, the GET request tohttps://a-challenge.company.com/sector/+98%2072%20349would return the following:
1$ curl https://a-challenge.company.com/sector/+98%2072%20349
2{
3 "number": "+9872349",
4 "sector": "Banking"
5}
phone number | API end API --> | Get sector | ExternalService
Developing the API
For tackling this challenge, I’m experimenting with Starlette, which is a simple async Python framework. This project is built by following the tutorial on Starlette documentation.
You can find this projects codebase on https://github.com/andreffs18/phone-validator
First, we create a single server.py file that opens two endpoints, and starts the server:
1# ~/project/phone-validator/server.py
2import logging
3import os
4import time
5import uvicorn
6
7from starlette.applications import Starlette
8from starlette.middleware import Middleware
9from starlette.responses import JSONResponse
10from starlette.routing import Route
11
12
13logger = logging.getLogger("uvicorn")
14logger.setLevel(logging.DEBUG)
15
16
17async def startup():
18 logger.info(f"Ready to start")
19
20
21async def shutdown():
22 logger.info("Ready to shutdown")
23
24
25async def health(request):
26 time.sleep(1)
27 return JSONResponse({"ok": "ok"}, 200)
28
29
30async def aggregate(request):
31 time.sleep(1)
32 return JSONResponse({"ok": "ok"}, 200)
33
34
35logger.info("🌀 Starting app...")
36app = Starlette(
37 debug=os.environ.get("DEBUG", True),
38 routes=[
39 Route("/", health),
40 Route("/aggregate", aggregate, methods=["POST"]),
41 ],
42 on_startup=[startup],
43 on_shutdown=[shutdown],
44)
45
46
47if __name__ == "__main__":
48 uvicorn.run("project.server:app", host="0.0.0.0", port=8080, reload=True)
To run the service just do the following:
1# ~/project/phone-validator/
2$ uvicorn server:app --port 8080 --host 0.0.0.0 --reload
And to test that everything is working, we just need to POST /aggregate endpoint:
1~/projects/phone-validator $ curl http://localhost:8080/aggregate
2{"ok": "ok"}
Validating inputs
We need to check for valid phone numbers. The rules of the challenge are:
“A number is considered valid if it contains only digits, an optional leading
+, and whitespace anywhere except immediately after the+. A valid number has exactly 3 digits or more than 6 and less than 13.00is acceptable as replacement for the leading+. All dashes and parentheses are ignored.”
This can be easily mapped to:
1# ~/project/phone-validator/services.py
2def is_valid_phone_number(phone_number: str) -> Union[str, bool]:
3 """
4 A phone number is considered valid if:
5 * all dashes and parentheses are ignored
6 * an optional leading `+` or `00`
7 * whitespace anywhere except immediately after the `+`.
8 * has exactly 3 digits or more than 6 and less than 13
9 * it contains only digits,
10 """
11 phone_number = phone_number.replace("-", "")
12 phone_number = phone_number.replace("(", "")
13 phone_number = phone_number.replace(")", "")
14
15 if phone_number.startswith("+") or phone_number.startswith("00"):
16 phone_number = phone_number.lstrip("+")
17 phone_number = phone_number.lstrip("00")
18
19 if phone_number.startswith(" "):
20 logger.debug('number does start with " "')
21 return False
22
23 phone_number = phone_number.replace(" ", "")
24 if len(phone_number) != 3:
25 if not (6 < len(phone_number) < 13):
26 return False
27
28 if not phone_number.isdigit():
29 logger.debug("number is not a digit")
30 return False
31
32 return phone_number
Checking prefixes
The core of the problem.
In the spirit of “let’s just make this work and then improve”, we can check if a given number contains a valid prefix just by iterating through the list of prefixes and asserting that the phone number starts with that string:
1# ~/project/phone-validator/services.py
2with open(os.path.join(os.getcwd(), "prefixes.txt")) as tmp:
3 PREFIXES = list(filter(None, map(lambda line: line.strip(), tmp.readlines())))
4
5async def get_prefix(phone_number: str) -> Union[str, bool]:
6 for prefix in PREFIXES:
7 if phone_number.startswith(prefix):
8 return prefix
9 return False
This is doing what we want, but it is not the best and is far from being an optimized solution.
Let’s put a pin in this and revisit the topic later
Fetching sectors
Instead of making actual requests to an external provider, we will be mocking the service using the following OpenAPI Spec:
1# ~/project/phone-validator/sector_service.yml
2openapi: 3.0.3
3info:
4 title: Challenge Mock
5 version: 1.0.0
6paths:
7 /sector/{phoneNumber}:
8 get:
9 summary: Return given's phone number sector
10 parameters:
11 - name: phoneNumber
12 in: path
13 description: Phone Number
14 required: true
15 schema:
16 type: string
17 responses:
18 '200':
19 description: successful operation
20 content:
21 application/json:
22 schema:
23 $ref: '#/components/schemas/Sector'
24components:
25 schemas:
26 Sector:
27 required:
28 - number
29 - sector
30 type: object
31 properties:
32 number:
33 type: string
34 example: "+1478192"
35 sector:
36 type: string
37 enum: [Auto, Banking, Energy, Health Care, Insurance, Materials, Entertainment,
38 Pharmaceuticals, Real Estate, Retailing, Technology, Telecommunication,
39 Transportation, Utilities]
40 examples: Banking
I’m creating a mock service with prism. Without going into much detail, prism allows you to generate a mock/proxy server from a given OpenAPI Spec or Postman collection. It has this cool feature that makes all responses “dynamic” which provides some variability to the tests we are doing:
1$ prism mock sector_service.yml --dynamic
2[8:32:56 AM] › [CLI] … awaiting Starting Prism…
3[8:32:56 AM] › [CLI] ℹ info GET http://127.0.0.1:4010/sector/rem
4[8:32:56 AM] › [CLI] ▶ start Prism is listening on http://127.0.0.1:4010
Requesting the mock server we get:
1$ curl http://127.0.0.1:4010/sector/testing
2{"number": "non", "sector": "Entertainment"}
3
4$ curl http://127.0.0.1:4010/sector/testing
5{"number": "i", "sector": "Insurance"}
6
7$ curl http://127.0.0.1:4010/sector/testing
8{"number": "in", "sector": "Real Estate"}
Adding this external call to our project is as mapping that curl request into a python request
1# ~/project/phone-validator/services.py
2import requests
3from pydantic import BaseModel
4
5
6class Response(BaseModel):
7 """
8 Example:
9 {'number': '+1478192', 'sector': 'Clothing'}
10 """
11 number: str
12 sector: str
13
14
15async def get_sector(phone_number: str) -> str:
16 response = requests.get(f"http://localhost:4010/sector/{phone_number}")
17 response = Response(**response.json())
18 return response.sector
All together now
We have all the pieces that we need:
- The
is_valid_phone_numbermethod checks if the given phone number is valid - The
get_prefix(the part of this challenge I’m interested in exploring) finds the prefix in a given phone number and returns it - Finally the
get_sector, which talks to our mock server, returns a “fake” sector given a phone prefix
We are now in a condition where we can refactor our “/aggregate” route with the behavior we need:
1# ~/project/phone-validator/server.py
2async def aggregate(request):
3 phone_numbers = await request.json()
4 output = {}
5 for input_phone_number in phone_numbers:
6 phone_number = is_valid_phone_number(phone_number=input_phone_number)
7 if not phone_number:
8 logger.error(f"{input_phone_number} is not valid")
9 continue
10
11 prefix = await get_prefix(phone_number=phone_number)
12 if not prefix:
13 logger.error(f"{phone_number} does not have a valid prefix")
14 continue
15
16 if prefix not in output:
17 output[prefix] = {}
18 sector = await get_sector(phone_number=phone_number)
19 if sector not in output[prefix]:
20 output[prefix][sector] = 0
21
22 output[prefix][sector] += 1
23
24 return JSONResponse(output, 200)
Spinning up our service, and making the original request from the challenge instructions, gives us this:
1$ curl -X POST http://localhost:8080/aggregate \
2 -H 'Content-Type: application/json' \
3 -d '["+1983248", "00351917355", "+147 8192", "+351917312", "+ 918851"]' | jq
4
5{
6 "1": {
7 "Banking": 1,
8 "Utilities": 1
9 },
10 "3519173": {
11 "Auto": 2
12 }
13}
Benchmarking this solution
Thinking back on the solution we have, the get_prefix that we’ve implemented is arguably not the best approach. That is the point of this blog post: What is the most performant solution for this problem? But first, how bad is this solution?
- Is this slow, and how slow? In the worst-case scenario (ie: validating the last prefix) how much time it takes?
- Is the
PREFIXlist that big of a memory footprint? Or is it just a couple of kilobytes? - How many parallel requests am I able to serve with this solution?
To do this assessment I restructured the project and added some extra functionality:
- Create
routes.pyfile where theaggregate()andhealth()routers live - Created a new
backend/folder where I abstracted the functionget_prefixinto the filebackend/in_memory.py - Configured the
startup()even hook of the Starlette server to choose its “backend” using an environment variable - Added docker-compose to the project so I can start the whole project with just
docker-compose up - Initialized
prometheus-middlewareon the Startlette app, so we can have a/metricsendpoint to have some observability using Grafana dashboards
This is what the project looks like now:
1# ~/project/phone-validator/
2.
3├── README.md
4├── Dockerfile
5├── sector_service.yml
6├── docker-compose.yml
7├── pyproject.toml
8├── poetry.lock
9├── prefixes.txt
10├── backends
11│ └── in_memory
12│ ├── def get_prefix()
13│ ├── def startup_backend()
14│ └── def shutdown_backend()
15├── server.py
16│ ├── def startup()
17│ ├── def shutdown()
18│ └── def init_server()
19├── routes.py
20│ ├── def health()
21│ └── def aggregate()
22└── services.py
23 ├── def is_valid_phone_number()
24 └── def get_sector()
1# ~/project/phone-validator/docker-compose.yml
2version: "3.2"
3services:
4 prometheus:
5 image: prom/prometheus:v2.30.3
6 ports:
7 - 9000:9090
8 volumes:
9 - ./tmp/prometheus:/etc/prometheus
10 - ./tmp/prometheus/prometheus-data:/prometheus
11 command: --web.enable-lifecycle --config.file=/etc/prometheus/prometheus.yml
12
13 grafana:
14 image: grafana/grafana:latest
15 ports:
16 - 3000:3000
17 volumes:
18 - ./tmp/grafana/provisioning/datasources:/etc/grafana/provisioning/datasources
19 - ./tmp/grafana/grafana-data:/var/lib/grafana
20 environment:
21 - GF_DEFAULT_APP_MODE=development
22 depends_on:
23 - prometheus
24
25 api:
26 restart: always
27 build:
28 context: .
29 dockerfile: Dockerfile
30 depends_on:
31 - mock
32 - grafana
33 ports:
34 - 8080:8080
35 volumes:
36 - .:/app/
37
38 mock:
39 image: stoplight/prism
40 ports:
41 - 4010:4010
42 volumes:
43 - ./sector_service.yml:/usr/src/prism/packages/cli/sector_service.yml
44 command: mock sector_service.yml --dynamic --host 0.0.0.0
To find the grafana dashboard or check the project’s code, you can go here: https://github.com/andreffs18/phone-validator
Qualifying the solution
Let’s take a look question by question:
Is this slow, and how slow? In the worst-case scenario (ie: last prefix) how much time it takes?
We can see this by measuring the time it takes to get a response. This involves all of the steps of requests on the sequence diagram below:
{ "number": "+1", "sector": "Technology" } api->>client: HTTP 200 OK
{ "1": { "Technology": 1 } } deactivate api deactivate client
To test this we will monitor the “Requests Time Taken” panel on our Grafana dashboard, which tells us how much time each request takes, plus we will be using “hey” to benchmark the endpoint.
A quick side note: with this blog post I ended up spending most of the time playing around with benchmarking tools and afaik hey doesn’t handle well high concurrency levels. So if your planing on doing some heavy loads, the recommended alternative is apache benchmark.
The question we want to answer is: What’s the P95 of the /aggregate endpoint, with a phone number that has the first, middle, or last prefix of the list?
1# How many elements in the prefixes list
2$ wc -l prefixes.txt
3 900005 prefixes.txt
4
5# First valid prefix
6$ head -n1 prefixes.txt
71
8
9# Last valid prefix
10$ tail -n1 prefixes.txt
116
12
13# Prefix in the middle of the list
14# $ head -n (900005/2) prefixes.txt | tail -n1
15$ head -n450002 prefixes.txt| tail -n1
163449998
For 60 seconds, we ran the following command simulating one HTTP client with the number +1983248, then +344999813123, and lastly +6983248.
1$ hey -z 60s -c 1 -m GET \
2 -H "Content-Type: application/json" \
3 -d '["{{ NUMBER }}"]' \
4 http://localhost:8080/aggregate
Keep in mind that this was done on my Laptop, a 2015 MacBook Pro with 3.1 GHz Dual Core Intel i7, with 16GB of memory.
| Prefix | Req/s | P95 | Total Reqs |
|---|---|---|---|
| +1983248 (first) | 27.7820 | 0.0731 secs | 1668 responses |
| +344999813123 (middle) | 6.8536 | 0.2894 secs | 412 responses |
| +6983248 (last) | 4.0407 | 0.4103 secs | 243 responses |
Answering our question, we can see that with the current implementation, when we validate the phone prefix, the further away we are from the beginning of the "PREFIX" list, the slower the API takes to handle the request. Concretely, we get a 7X performance hit on the P95 of the service, depending on the input.
Is the PREFIX list that big of a memory footprint?
Looking at our “Services Memory” panel, we can see how much loading all prefixes into memory users from our available memory.
How many parallel requests am I able to serve with this solution?
Similar to the question above, how many requests can this solution handle during 60 seconds by either having 2, 4, or 8 concurrent clients making those requests?
Baseline: 1 client
| Solution | Clients | Prefix | Req/s | P95 | Total Reqs |
|---|---|---|---|---|---|
| in_memory | c1 | +1983248 (first) | 27.7820 | 0.0731 secs | 1668 responses |
| in_memory | c1 | +344999813123 (middle) | 6.8536 | 0.2894 secs | 412 responses |
| in_memory | c1 | +6983248 (last) | 4.0407 | 0.4103 secs | 243 responses |
| in_memory | c2 | +1983248 | 48.3398 | 0.0836 secs | 2902 responses |
| in_memory | c2 | +344999813123 | 9.4420 | 0.4440 secs | 568 responses |
| in_memory | c2 | +6983248 | 4.3614 | 0.8041 secs | 263 responses |
| in_memory | c4 | +1983248 | 59.2556 | 0.1272 secs | 3558 responses |
| in_memory | c4 | +344999813123 | 9.5636 | 0.6002 secs | 577 responses |
| in_memory | c4 | +6983248 | 3.8022 | 1.8013 secs | 232 responses |
| in_memory | c8 | +1983248 | 46.7732 | 0.3957 secs | 2814 responses |
| in_memory | c8 | +344999813123 | 7.9378 | 1.4435 secs | 481 responses |
| in_memory | c8 | +6983248 | 2.3447 | 9.0418 secs | 144 responses |
Similar to our first question, the further away we are from the beginning of the “PREFIX” list, the least amount of requests we can handle in parallel.
Alternatives
Of course, if I were to submit this challenge, this would not be the solution that I would be most proud of… in a nutshell, it doesn’t scale (slow and would need many instances to support the increased load).
Although very simple, it’s naive to assume that we would want to do string comparisons on a set of 900k elements for every request we get, on a possible very busy service.
So how can I solve this? Well:
- My first thought is to use a database and leverage its capabilities of searching + indexing.
- My second thought (and to be honest, going back to my “Algorithms and Data Structures” book) is to find a better data structure that solves this problem cleanly
To answer the first idea, I’ll be using Mongo, Postgres, and Redis databases to check the differences in RPS, P95, and Total Requests. For the second one, I’ll be comparing the original “In Memory” with a “Trie” data structure.
Setting up backends
Not spending too much time showing the setup of these solutions as before (the code can be found in the repo) but for all these different solutions I did:
- Installed the dependencies to be able to play with the different solutions
- Added new files to the
backend/folder to then initialize each solution using a .env variable - Added both the database + an open-source dashboard to my docker-compose so I could see what was going on
1# ~/project/phone-validator/
2.
3├── README.md
4├── Dockerfile
5├── sector_service.yml
6├── docker-compose.yml
7├── pyproject.toml
8├── poetry.lock
9├── prefixes.txt
10├── backends
11│ ├── in_memory
12│ │ └── (...)
13│ ├── trie
14│ │ └── (...)
15│ ├── mongo
16│ │ └── (...)
17│ ├── postgres
18│ │ └── (...)
19│ └── redis
20│ └── (...)
21├── server.py
22│ ├── def startup()
23│ ├── def shutdown()
24│ └── def init_server()
25├── routes.py
26│ ├── def health()
27│ └── def aggregate()
28└── services.py
29 ├── def is_valid_phone_number()
30 └── def get_sector()phone number | Mongo API <--> | Validate
phone number | Postgres API <--> | Validate
phone number | Redis API <-.->| Validate
phone number | InMemory API <-.->| Validate
phone number | Trie end API ---> | Get sector | ExternalService
Using databases
Mongo
For Mongo, I just added all prefixes to a collection with the key “prefix”, and make an $in query with the “exploded” number.
1# ~/project/phone-validator/backends/mongo.py
2import motor.motor_asyncio
3from services import read_prefix_file
4
5
6async def get_prefix(request, phone_number: str) -> Union[str, bool]:
7 mongo_client = motor.motor_asyncio.AsyncIOMotorClient("mongo", 27017)
8 # explode phone number in a list of sub-numbers
9 # eg: phone_number = "1234" -> ["1234", "123", "12", "1"]
10 prefixes = [phone_number[:index] for index in range(len(phone_number), 0, -1)]
11 result = await mongo_client.test.test_value.find_one({"prefix": {"$in": prefixes}})
12 if not result:
13 return False
14
15 return result["prefix"]
16
17
18async def startup_backend(app: Starlette, logger: Logger) -> None:
19 mongo_client = motor.motor_asyncio.AsyncIOMotorClient("mongo", 27017)
20 # create index on prefix column with ascending sort order
21 await mongo_client.test.test_value.create_index([("prefix", "1")], background=False)
22
23 prefixes = read_prefix_file()
24 # one object per key, with the actual line being the value of the "key" field
25 await mongo_client.test.test_value.insert_many(map(lambda prefix: {"prefix": prefix}, prefixes))
26 # deallocate memory from a list of 900k prefixes
27 del prefixes
28 logger.info('Ready to go with mongo database "test"')
Postgres
For Postgres, I’ve also initialized the DB with a “prefix” column and added all prefixes but the approach to query is a bit different:
- Find in the “prefix” table a “phone number” that “LIKE"s each prefix.
- Because there might be more than one (ie: “+344999813123” find prefixes “1”, “2”, “44”, “3449998”), we want to get the “longest common string” which would be the last one of the ordered list.
1# ~/project/phone-validator/backends/postgres.py
2import psycopg
3
4from services import read_prefix_file
5
6
7async def get_prefix(request, phone_number: str) -> Union[str, bool]:
8 async with await psycopg.AsyncConnection.connect("postgresql://postgres:postgres@postgres:5432/postgres") as postgres_client:
9 async with postgres_client.cursor() as cur:
10 await cur.execute(
11 f"SELECT * FROM prefix WHERE '{phone_number}' LIKE '%' || prefix || '%' ORDER BY prefix DESC LIMIT 1"
12 )
13 result = await cur.fetchone()
14
15 if not result:
16 return False
17 return result[0]
18
19
20async def startup_backend(app: Starlette, logger: Logger) -> None:
21 prefixes = read_prefix_file()
22
23 async with await psycopg.AsyncConnection.connect("postgresql://postgres:postgres@postgres:5432/postgres") as postgres_client:
24 async with postgres_client.cursor() as cur:
25 await cur.execute("CREATE TABLE IF NOT EXISTS prefix (prefix INT PRIMARY KEY NOT NULL);")
26
27 amount = 5000
28 chunks = [prefixes[i : i + amount] for i in range(0, len(prefixes), amount)]
29 for prefixes in chunks:
30 prefixes = ",".join([f"({prefix})" for prefix in prefixes])
31 # setup column "prefix" with all lines as rows
32 await cur.execute(f"INSERT INTO prefix (prefix) VALUES {prefixes} ON CONFLICT (prefix) DO NOTHING;")
33
34 logger.info('Ready to go with postgres database "postgres"')
Redis (is it a database?)
For Redis, the simplest way I could find was to mimic the solution I did for Mongo:
- add all prefixes to a key as a member,
- then we can use the
smismembercommand to check if a given list of values belongs to the set.
That returns a list of “0’s” and “1’s” that match the list of “exploded prefixes”, so just doing an XOR between the results and our “exploded number”, gives us our prefix
1# ~/project/phone-validator/backends/redis.py
2import redis
3from services import read_prefix_file
4
5
6async def get_prefix(request, phone_number: str) -> Union[str, bool]:
7 r = redis.Redis(host="redis", port=6379, db=0)
8 # explode phone number in a list of sub-numbers
9 # eg: phone_number = "1234" -> ["1234", "123", "12", "1"]
10 prefixes = [phone_number[:index] for index in range(len(phone_number), 0, -1)]
11 result = r.smismember("prefix", prefixes)
12 # parse zipped list of prefixes with an array of returned booleans
13 # eg: zip(["1234", "123", "12", "1"], [0, 0, 0, 1]) => ["1"]
14 result = list([p for p, r in zip(prefixes, result) if r])
15 if not result:
16 return False
17 return result[0]
18
19
20async def startup_backend(app: Starlette, logger: Logger) -> None:
21 r = redis.Redis(host="redis", port=6379, db=0)
22
23 prefixes = read_prefix_file()
24 # create set "prefix" and add all lines as members.
25 r.sadd("prefix", *prefixes)
26 logger.info('Ready to go with redis database "0"')
Using data structures
Trie structure
Trie is more than a binary tree and the thing to notice is that with this data structure (compared against the original “in_memory” solution) our memory footprint increases a lot.
“A naive implementation of a trie consumes immense storage due to larger number of leaf-nodes caused by sparse distribution of keys” - Wikipedia
The best part of this solution is that it keeps operations to find a valid prefix in constant time.
1# ~/project/phone-validator/backends/trie.py
2from pytrie import StringTrie
3from services import read_prefix_file
4
5
6async def get_prefix(request, phone_number: str) -> Union[str, bool]:
7 return request.app.state.trie.longest_prefix(phone_number, default=None)
8
9
10async def startup_backend(app: Starlette, logger: Logger) -> None:
11 trie = StringTrie()
12 for p in read_prefix_file():
13 trie[p] = True
14
15 app.state.trie = trie
16 logger.info(f"Ready to go with {len(app.state.trie)} lines")
Comparing results
The same tests were made: for each solution, during 60 seconds, simulate 1, 2, 4, and 8 concurrent clients, asking for the first, middle, and last prefix of the list.
This bash script should handle this nicely:
1# ~/project/phone-validator/loadtest/run.sh
2#!/bin/bash
3for MODE in "in_memory" "trie" "mongo" "postgres" "redis"
4do
5 mkdir loadtest/$MODE;
6 echo "👀 Starting \"$MODE\" load test..."
7 echo "BACKEND=backend.$MODE" >> .env
8 source .env
9 docker-compose --env-file .env up -d
10 echo "Sleeping for 60 to let server bootstrap"
11 sleep 60
12
13 for number in "+1983248" "+344999813123" "+6983248"
14 do
15 for clients in 1 2 4 8
16 do
17 echo "Running for 60seconds '-c $clients' for '$number' ..."
18 hey -z 60s -c $clients -m POST -H "Content-Type: application/json" \
19 -d "[\"$number\"]" http://localhost:8080/aggregate > loadtest/$MODE/output-c$clients-$number.txt
20 echo "Sleeping for 60"
21 sleep 60
22 done
23 done
24
25 # Print RPS, P95 and Total Requests once finished
26 for file in loadtest/$MODE/*.txt; do
27 echo $file
28 cat $file | sed -n -e 7p -e 32p -e 43p
29 echo ""
30 done
31done
Some highlights:
- The most consistent solution across every dimension (prefix used and number of clients) is the Trie
- Strangely, Mongo uses almost 2GB of memory and I haven’t figured it out yet 🤔
- It comes as a surprise to me that with Postgres, we get very few RPS
- “hey” can’t handle very well high load. Apache Benchmark is a good alternative
- Redis is amazing 🤩 its comparable with the Trie solution.
Conclusion
Choosing the right tool for the job is important, but it’s not always the most crucial factor. In many cases, the right data structure is more essential when solving complex problems.
For example, in a coding challenge, you may be tempted to use a built-in function like reverse() to check for a palindrome, but using a stack could be a faster and more efficient solution.
When working on software projects, it’s not always necessary to choose the latest tool or framework, sometimes it’s better to stick with what you know, or maybe even re-learn old solutions by going back to basics.
By the end of this post, I figure that I could use this project to test new versions of each tool, or new data structures that I might learn more about in the future.
For example, if Postgres gets bumped, or if I get the time to play with a “Patricia Tree” (funny name), I can just implement a backend, docker-compose up and compare with the other solutions.
The project is self-contained enough that it allows me to expand with new solutions “as plugins” and keep the core functionality being tested.
Which I think is pretty sweet 🤓
Resources
- Setting up grafana dashboards: https://medium.com/javarevisited/monitoring-setup-with-docker-compose-part-2-grafana-2cd2d9ff017b
- Trie data structure: https://en.wikipedia.org/wiki/Trie
👋