A URL Shortener is a service that creates short aliases for URLs. It generates a short code for a URL and then redirects the user to the URL when that code is accessed. One example of such service is https://bitly.com/.
This problem can be solved by generating a hash for each url that is requested. Store the hash with the original url and when the hash is requested, search the database for the original url and redirect to it.
Some of the algorithms that we can use are MD5, SHA1, SHA256, SHA512. However, there are two main problems with this approach:
1.- The hash is not unique. Assuming that it is necessary to register unique users who enter the system through a shared link, with this approach we would have problems in tracking the origin of registered users. Since the hash generated for the same url is the same. Example: https://fondeadora.com/signup MD5 -> B89E925D953A726EA244D436D976D50F. When registering each user with their reference hash, it would be the same.
2.- The hash size of at least 40 characters. In the previous example, there are more characters in the hash than the url. (https://fnd2r.com/B89E925D953A726EA244D436D976D50F).
From a simpler approach, the url can have letters and numbers. Considering uppercase, lowercase and number we would have the following corpus:
'abcdefghijklmnopqrstuvwxyz' + 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' + '0123456789'
Each character can then be represented in a single digit within a base number 62 (26 + 26 + 10). With 62 characters and a length of 6 characters for each string, we can generate 56,800,235,584 different urls.
To generate the hash in base 62, we require a number in base 10. So we could use a table with the following structure:
- id
- url
- short_url
- created_at
- expire_at
- user
In this case, the ID would be a self-incrementing and we would use it to generate the hash in base 62. However, this approach would cause conflicts if the database needs to be partitioned. We cannot handle autoincrementables for the simple reason that we have different tables where we insert data. In addition to that it is not a guarantee that it will be sequential in case of a roll back and we would be doing 2 operations in the database, one to make the insert and generate the ID, to later update the sort_url generated from that ID.
One option is to have a centralized service that generates the seed to generate the hash, for example using the auto-incrementing feature in Redis or changing the focus to a key-value storage.
Based on the KISS principle and as part of the decision for which database to use. Postgres has an object called "sequences", which creates an independent sequence number generator to the table, which solves the partitioning problem when the project scales and provides us with a unique ID to generate our hash. With what we would have the following structure:
- id
- url
- short_url
- created_at
- expire_at
- user
Where the ID is the hash generated by the sequence number in postgres in base62, "expire" which is consulted in each request to know if the shorten url is still valid. And it helps us to use a partition strategy based on the date on which the urls (Range-based partitioning) expire.
- Create virtual env
python3 -m venv venv(First time) - Activate venv
source venv/bin/activate - Change dir to backend/
- Install dependencies
pip install -r requirements.txt python manage.py migrate(to run migrations)- Create super user
python manage.py createsuperuser - Add django secret environment variable in manage.py
os.environ.setdefault('DJANGO_SECRET_KEY', 'bioa83o2y^0*x@rlw@#r^tk@i_n!hduu8s&ukx(i05!f!@%dkj')
- Run server
python manage.py runserver
- Run server
pytest
Run npm install and then ng serve for a dev server. Navigate to http://localhost:4200/. The app will automatically reload if you change any of the source files.
Run ng build to build the project. The build artifacts will be stored in the dist/ directory. Use the --prod flag for a production build.
- [https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR] (https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR)
- [https://docs.djangoproject.com/en/2.2/ref/databases/#manually-specifying-values-of-auto-incrementing-primary-keys] (https://docs.djangoproject.com/en/2.2/ref/databases/#manually-specifying-values-of-auto-incrementing-primary-keys)
- [https://www.postgresql.org/docs/current/datatype-numeric.html#DATATYPE-SERIAL] (https://www.postgresql.org/docs/current/datatype-numeric.html#DATATYPE-SERIAL)
- [https://www.postgresql.org/docs/9.5/sql-createsequence.html] (https://www.postgresql.org/docs/9.5/sql-createsequence.html)
- [https://www.qwertee.io/blog/postgres-data-partitioning-and-django/] (https://www.qwertee.io/blog/postgres-data-partitioning-and-django/)
- [https://hackr.io/blog/postgresql-vs-mysql] (https://hackr.io/blog/postgresql-vs-mysql)
- [https://www.oreilly.com/library/view/architecting-data-intensive-applications/9781786465092/132886d4-3507-4cb4-97fe-c3661cdffc3f.xhtml] (https://www.oreilly.com/library/view/architecting-data-intensive-applications/9781786465092/132886d4-3507-4cb4-97fe-c3661cdffc3f.xhtml)
- [https://redis4you.com/code.php?id=015&name=Using+Redis+for+MySQL+autoincrement] (https://redis4you.com/code.php?id=015&name=Using+Redis+for+MySQL+autoincrement)
- [https://pypi.org/project/django-sequences/] (https://pypi.org/project/django-sequences/)