Разработка сокращения URL-адресов

От: Из: Общие

Недавно во время собеседования с известной организацией мне поставили задачу разработать программу сокращения URL-адресов. Вот точная постановка проблемы:

  1. Создайте простую службу сокращения URL-адресов, которая будет принимать URL-адрес в качестве аргумента через REST API и в результате возвращать сокращенный URL-адрес.

  2. URL-адрес и сокращенный URL-адрес должны храниться в памяти приложением.

    а. [BONUS] Храните эти вещи не в памяти, а в текстовом файле.

  3. Если я снова запрошу тот же URL-адрес, он должен дать мне тот же URL-адрес, что и раньше, вместо создания нового.

  4. [BONUS] Поместите это приложение в образ Docker, написав файл Docker и предоставив ссылку на образ Docker вместе со ссылкой на исходный код.

Проблема выглядела проще, и я тоже набрал все бонусные баллы, но до сих пор не получил от них ответа (даже отзывов).

Вот мой подход:

  • Поскольку они запросили несколько механизмов хранения, я создал фабрику для хранилищ ключ-значение и реализовал хранилища на основе памяти и файлов.
  • Я мог придумать два подхода к сокращению URL-адресов: 1) Хеширование 2) База 62 счетчика. База 62 казалась правильным подходом, но они добавили требование, чтобы для одного и того же длинного URL-адреса возвращался такой же сокращенный URL-адрес. Поскольку Base 62 работает со счетчиком автоинкремента, выполнение этого требования без дополнительной памяти / хранилища невозможно. Поэтому я пошел с хешированием длинных URL-адресов (я знаю, что есть вероятность коллизий, я упомянул об этом как о компромиссе).

Вот мое базовое хранилище ключей и значений:

kvstore_base.py

from abc import ABC, abstractmethod


class KVStoreBase(ABC):
    """
    Base key-value store class that provides abstract methods required for
    any storage mechanism used to store shortened URLs.
    """

    def __init__(self, store):
        """
        Constructor.

        :param store: Object of any storage mechanism.
        """
        self.store = store

    @abstractmethod
    def __getitem__(self, key: str) -> str:
        pass

    @abstractmethod
    def __setitem__(self, key: str, value: str) -> None:
        pass

    @abstractmethod
    def __contains__(self, key: str) -> bool:
        pass

file_store.py

import io

from .kvstore_base import KVStoreBase


class FileStore(KVStoreBase):
    """
    Memory store, which uses 'dict' data structure to
    store the key-value pairs.
    """

    def __init__(self):
        super().__init__(open("db.txt", "a+"))

    def __getitem__(self, key: str) -> str:
        """
        Get value for the given key from dict
        :param key: Key for which the value is to be retrieved.
        :return: value
        """
        # iterate over file and search for given key.
        try:
            # move pointer to initial position in file
            self.store.seek(0, io.SEEK_SET)
            for line in self.store:
                suffix, long_url = line.split()
                if suffix == key:
                    return long_url
        except Exception as err:
            print(str(err))
        return ""

    def __setitem__(self, key: str, value: str) -> None:
        """
        Set value for the given key into dict.
        :param key: Key to be added.
        :param value: Value corresponding to the key.
        :return: None
        """
        # move pointer to the end of the file for writing.
        self.store.seek(0, io.SEEK_END)
        if self.store.tell() != 0:
            self.store.write(f"n{key} {value}")
        else:
            self.store.write(f"{key} {value}")
        self.store.flush()

    def __contains__(self, key: str) -> bool:
        """
        Check whether the given key is present in the dict.
        :param key: Key whose presence is to be checked.
        :return: True if key is present, False otherwise.
        """
        return True if self.__getitem__(key) else False

    def __del__(self) -> None:
        """
        Free file resource.
        """
        self.store.close()

kvstore_factory.py

from .memory_store import MemoryStore
from .file_store import FileStore
from .kvstore_base import KVStoreBase


class Factory:
    """
    KV Store factory to instantiate storage objects.
    """

    kvstore_map: dict = {"MEMORY": MemoryStore, "FILE": FileStore}

    @staticmethod
    def get_instance(instance_type: str) -> KVStoreBase:
        """
        Instantiate given KV store class dynamically.
        :param instance_type: Type of KV store to be instantiated.
        :return: KV store object.
        """
        try:
            return Factory.kvstore_map[instance_type]()
        except KeyError:
            raise Exception("Invalid instance requested.")

Я использовал FastAPI для создания конечных точек, вот два основных маршрута (один для сокращения URL-адреса и один для перенаправления):

маршруты / urls.py

import hashlib
from urllib.parse import urlparse

from fastapi import APIRouter, HTTPException, Request

from ..utils.store_connector import StoreConnector
from ..models.urls import Url
from starlette.responses import RedirectResponse

router = APIRouter()
store = StoreConnector().store


def _get_base_url(endpoint_url: str) -> str:
    """
    Extract base url from any endpoint URL.
    :param endpoint_url: Endpoint URL from which the base URL is to be extracted.
    :return: Base URL
    """
    return f"{urlparse(endpoint_url).scheme}://{urlparse(endpoint_url).hostname}:{urlparse(endpoint_url).port}"


@router.post("/shorten", tags=["URLs"])
async def shorten(url_obj: Url, request: Request) -> Url:
    """
    Shorten the given long URL.
    :param request: request object
    :param url_obj: URL object
    :return: shortened URL.
    """
    suffix = hashlib.sha256(url_obj.url.encode("utf-8")).hexdigest()[:8]
    if suffix not in store:
        # store short-url-suffix: long-url into data store.
        store[suffix] = url_obj.url

    return Url(url=f"{_get_base_url(request.url_for('shorten'))}/{suffix}")


@router.get("/{suffix}", tags=["URLs"])
async def redirect(suffix: str) -> RedirectResponse:
    """
    Redirect to long URL for the given URL ID.
    :param suffix: URL ID for the corresponding long URL.
    :return: Long URL.
    """
    long_url = store[suffix]
    if long_url:
        # return permanent redirect so that browsers store this in their cache.
        response = RedirectResponse(url=long_url, status_code=301)
        return response
    raise HTTPException(status_code=404, detail="Short URL not found.")

Я представил механизм хранения переменной среды docker и создал класс соединителя хранилища, который вызывает фабрику в зависимости от конфигурации пользователя.

store_connector.py

import os
import sys
from sys import stderr

from .singleton import Singleton
from ..kvstores.kvstore_factory import Factory
from ..kvstores.kvstore_base import KVStoreBase


class StoreConnector(metaclass=Singleton):
    """
    Key Value store singleton class that can be used across all modules.
    """

    def __init__(self):
        try:
            store_type = os.environ.get("STORE_TYPE", "MEMORY")
            self._store = Factory.get_instance(store_type)
        except KeyError as ex:
            print(ex, file=stderr)
            # one of the required environment variable is not set
            print(
                "One of the required environment variables is not set",
                file=stderr,
            )
            sys.exit(1)
        except Exception as ex:
            print(ex, file=stderr)
            sys.exit(1)

    @property
    def store(self) -> KVStoreBase:
        return self._store

Вот моя структура каталогов:

    url-shortener/
├── Dockerfile
├── LICENSE
├── README.md
├── requirements.txt
├── src
│   ├── __init__.py
│   ├── kvstores
│   │   ├── __init__.py
│   │   ├── file_store.py
│   │   ├── kvstore_base.py
│   │   ├── kvstore_factory.py
│   │   └── memory_store.py
│   ├── main.py
│   ├── models
│   │   ├── __init__.py
│   │   └── urls.py
│   ├── routes
│   │   ├── __init__.py
│   │   └── urls.py
│   └── utils
│       ├── singleton.py
│       └── store_connector.py
├── start.sh
└── tests
    ├── __init__.py
    ├── test_file_store.py
    ├── test_kvstore_factory.py
    ├── test_memory_store.py
    ├── test_routes.py
    └── test_store.py

В инструкции подчеркнули следующие моменты:

  • Читаемость кода
  • Тесты — Модульные тесты определенно и многое другое, если вы можете подумать о
  • Хорошая структура вашего кода и хорошо написанные имена файлов и переменных и т. Д.

Итак, чего из этого не хватает в моем коде?

1 ответ
1

На мой взгляд, ваш код выглядит красиво и читабельно; Я могу понять большую часть того, что происходит. Однако в некоторых моментах я не уверен:

(1) Ваша обработка исключений кажется мне немного странной

В filestore.py, вы поймаете все исключения в своем __getitem__ метод. Как правило, это плохая практика — если вы ожидаете исключение определенного типа, вам следует перехватить только это конкретное исключение. Есть некоторые ситуации, когда вы можете захотеть перехватить и подавить все исключения, но они редки, и (по крайней мере, для меня) не очевидно, почему это одно из них. В строке документации нет ничего, что могло бы объяснить, почему вы ее ловите и просто распечатываете. Вместо того, чтобы ловить все ошибки в __getitem__ и возвращая пустую строку, если у вас не получилось, я бы поймал KeyErrorс в routes/urls.py

Точно так же в kvstore_factory.py, мне непонятно, почему ты поймала KeyError исключение — особый вид исключения, информативный о том, что могло его вызвать — и заменить его общим Exception. Если вы хотите добавить полезную дополнительную информацию в сообщение об ошибке, я бы сделал следующее:

# kvstore_factory.py

class Factory:
    kvstore_map: dict = {"MEMORY": MemoryStore, "FILE": FileStore}

    @staticmethod
    def get_instance(instance_type: str) -> KVStoreBase:
        try:
            return Factory.kvstore_map[instance_type]()
        except KeyError as err:
            raise KeyError("Invalid instance requested.") from err

Или это:

# kvstore_factory.py

class InvalidInstanceRequest(KeyError):
    """
    Raised when a user requests an instance
    that does not exist in Factory.kvstore_map
    """


class Factory:
    kvstore_map: dict = {"MEMORY": MemoryStore, "FILE": FileStore}

    @staticmethod
    def get_instance(instance_type: str) -> KVStoreBase:
        try:
            return Factory.kvstore_map[instance_type]()
        except KeyError as err:
            raise InvalidInstanceRequest("Invalid instance requested.") from err

Наконец, я не понимаю, почему в store_connector.py, вы перехватываете исключения, а затем вызываете sys.exit. Почему бы просто не вызвать исходное исключение заново, вот так? Я думаю, что это приведет к более удобочитаемой трассировке. Я бы вынул второй except предложение полностью — если все, что вы делаете, это печатаете его, а затем вызываете sys.exit(), с тем же успехом вы можете вообще не ловить его и позволить исключению завершить программу.

# store_connector.py

import os

from .singleton import Singleton
from ..kvstores.kvstore_factory import Factory


class StoreConnector(metaclass=Singleton):
    def __init__(self):
        try:
            store_type = os.environ.get("STORE_TYPE", "MEMORY")
            self._store = Factory.get_instance(store_type)
        except KeyError as ex:
           raise KeyError("One of the required environment variables is not set") from ex

(2) Два второстепенных момента

Во-первых, в kvstore_factory.py, вы могли бы иметь гораздо более богатые подсказки по типу. Я также не совсем понимаю, почему вы используете staticmethod, когда classmethod казалось бы здесь более изящным.

# kvstore_factory.py

from typing import ClassVar
from .memory_store import MemoryStore
from .file_store import FileStore
from .kvstore_base import KVStoreBase


class Factory:
    kvstore_map: ClassVar[dict[str, KVStoreBase]] = {"MEMORY": MemoryStore, "FILE": FileStore}

    @classmethod
    def get_instance(cls, instance_type: str) -> KVStoreBase:
        try:
            return cls.kvstore_map[instance_type]()
        except KeyError as ex:
            # exception handling as discussed above 

# -- snip --

Во-вторых, вы можете упростить __contains__ метод в file_store.py просто написав return bool(self[key])

(3) Я бы добавил логику в routes/urls.py в другом месте

Точный способ хеширования URL-адресов кажется деталью реализации. Мне кажется странным, что эта логика в routes/urls.py. Я мог бы переписать ваш код так:

kvstore_base.py:

# kvstore_base.py

import hashlib
from abc import ABC, abstractmethod
from collections.abc import MutableMapping
from functools import cache

@MutableMapping.register
class KVStoreBase(ABC):
    def __init__(self, store):
        self.store = store

    def get_shortened_url(long_url: str) -> str:
        shortened_url = self.shorten_url(long_url)
        self[shortened_url] = long_url
        return shortened_url

    @staticmethod
    @cache
    def shorten_url(url: str) -> str:
        return hashlib.sha256(url.encode("utf-8")).hexdigest()[:8]

    @abstractmethod
    def __getitem__(self, key: str) -> str: ...

    @abstractmethod
    def __setitem__(self, key: str, value: str) -> None: ...

    @abstractmethod
    def __contains__(self, key: str) -> bool: ...

маршруты / urls.py:

# routes/urls.py

from urllib.parse import urlparse

from fastapi import APIRouter, HTTPException, Request

from ..utils.store_connector import StoreConnector
from ..models.urls import Url
from starlette.responses import RedirectResponse

router = APIRouter()
store = StoreConnector().store


def _get_base_url(endpoint_url: str) -> str:
    return f"{urlparse(endpoint_url).scheme}://{urlparse(endpoint_url).hostname}:{urlparse(endpoint_url).port}"


@router.post("/shorten", tags=["URLs"])
async def shorten(url_obj: Url, request: Request) -> Url:
    suffix = store.get_shortened_url(url_obj.url)
    return Url(url=f"{_get_base_url(request.url_for('shorten'))}/{suffix}")

# -- snip --

Альтернативный рефакторинг класса KVStore, если вы не верите, что детали хеширования принадлежат классу KVStore базового класса:

# kvstore_base.py

import hashlib
from abc import ABC, abstractmethod
from collections.abc import MutableMapping
from functools import cache

@MutableMapping.register
class KVStoreBase(ABC):
    def __init__(self, store):
        self.store = store

    @abstractmethod
    def __getitem__(self, key: str) -> str: ...

    @abstractmethod
    def __setitem__(self, key: str, value: str) -> None: ...

    @abstractmethod
    def __contains__(self, key: str) -> bool: ...


class URLStoreMixin:
    def get_shortened_url(long_url: str) -> str:
        shortened_url = self.shorten_url(long_url)
        self[shortened_url] = long_url
        return shortened_url

    @staticmethod
    @cache
    def shorten_url(url: str) -> str:
        return hashlib.sha256(url.encode("utf-8")).hexdigest()[:8]

Затем пусть ваши объекты MemoryStore и FileStore наследуются исключительно от KVStoreBase, как и раньше, но создайте классы MemoryURLStore и FileURLStore следующим образом:

class MemoryURLStore(MemoryStore, URLStoreMixin):
    pass

class FileURLStore(FileStore, URLStoreMixin):
    pass

  • 1

    Большой! Спасибо за подробный обзор. Мне очень понравились предложения по обработке исключений. Я не понимаю, почему вы храните длинные URL-адреса как ключевые, а короткие как значения? Когда пользователь вызывает API с использованием короткого URL-адреса, поиск длинного URL-адреса будет O (n) вместо O (1).

    — Каушал28

  • Да, хороший момент — не думал об этом. Отредактировал мой ответ, чтобы исправить это!

    — Алекс Вэйгуд

  • Спасибо. Вы правы в том, что хеширование — это деталь реализации / бизнес-логика приложения и может быть в другом месте. Но я не думаю, что магазин KV — подходящее место, потому что он должен знать только ключи и значения (развязку), чтобы его можно было использовать для других целей, кроме хранения URL-адресов. Но это только мои мысли.

    — Каушал28

  • Конечно, я это вижу — возможно, мой get_shortened_url и shorten_url методы были бы лучше как функции в глобальном пространстве имен, либо в routes / urls.py, либо в третьем файле. Я думаю, это зависит от того, как вы концептуализируете объекты магазина KV — видите ли вы их как объекты отображения. для конкретной цели, или как объекты обобщенного отображения это просто случайно используется для определенной цели.

    — Алекс Вэйгуд


  • К моему вопросу добавили альтернативный рефакторинг KVStore — было бы интересно услышать ваши мысли!

    — Алекс Вэйгуд

Похожие записи:

  1. От колибри до орнитоптеров: моделирование аэродинамики машущих крыльев
  2. Простая симуляция движения врага на Tkinter
  3. Объектно-ориентированная игра в покер
  4. Создание проводника файлов с помощью Python tkinter
  5. Симуляция простого и двойного маятника с помощью Python Tkinter

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *