Tools vs Data Structures

Learning that tools don’t solve all your problems

| #redis #postgresql #mongo #grafana #prometheus #benchmarking #data-structures #starlette #prism #openapi | ± 21 mins

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 +1 prefix,
  • and a count of 2 phones for Clothing associated with the +3519173 prefix.
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”:

sequenceDiagram autonumber actor client as Client participant api as Service API participant external as External API client->>api: HTTP POST /aggregate -d ["+1983236248"] activate client activate api alt Invalid Phone Nunber api->>api: Validate phone number prefix api->>client: HTTP 400 Bad Request deactivate api end activate api alt Valid Phone Nunber api->>api: Validate phone number prefix api->>+external: HTTP GET /sector/+1 external->>-api: HTTP 200 OK
{ "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 to https://a-challenge.company.com/sector/+98%2072%20349 would return the following:
1$ curl https://a-challenge.company.com/sector/+98%2072%20349
2{
3  "number": "+9872349",
4  "sector": "Banking"
5}
--- title: High-Level Architecture Diagram --- graph LR API[Service] ExternalService[External Service] Client[API Client] Client --> | POST /aggregate | API subgraph 'phone-validator' Project API --> | Validate
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. 00 is 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_number method 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 PREFIX list 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.py file where the aggregate() and health() routers live
  • Created a new backend/ folder where I abstracted the function get_prefix into the file backend/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-middleware on the Startlette app, so we can have a /metrics endpoint 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:

sequenceDiagram autonumber actor client as Client participant api as Service API participant external as External API client->>api: HTTP POST /aggregate -d ["+1983236248"] activate client activate api api->>api: Validate phone number prefix api->>+external: HTTP GET /sector/+1 external->>-api: HTTP 200 OK
{ "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.

    PrefixReq/sP95Total Reqs
    +1983248 (first)27.78200.0731 secs1668 responses
    +344999813123 (middle)6.85360.2894 secs412 responses
    +6983248 (last)4.04070.4103 secs243 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

      SolutionClientsPrefixReq/sP95Total Reqs
      in_memoryc1+1983248 (first)27.78200.0731 secs1668 responses
      in_memoryc1+344999813123 (middle)6.85360.2894 secs412 responses
      in_memoryc1+6983248 (last)4.04070.4103 secs243 responses
      in_memoryc2+198324848.33980.0836 secs2902 responses
      in_memoryc2+3449998131239.44200.4440 secs568 responses
      in_memoryc2+69832484.36140.8041 secs263 responses
      in_memoryc4+198324859.25560.1272 secs3558 responses
      in_memoryc4+3449998131239.56360.6002 secs577 responses
      in_memoryc4+69832483.80221.8013 secs232 responses
      in_memoryc8+198324846.77320.3957 secs2814 responses
      in_memoryc8+3449998131237.93781.4435 secs481 responses
      in_memoryc8+69832482.34479.0418 secs144 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()
      --- title: High-Level Architecture Diagram --- graph LR Redis[(Redis)] Postgres[(Postgres)] Mongo[(MongoDB)] API[Starlette API] InMemory([In Memory]) Trie([Trie]) ExternalService Client[API Client] Client --> | POST /aggregate | API subgraph 'phone-validator' Project API <--> | Validate
      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 smismember command 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

        👋


        comments powered by Disqus