53

I'd like to use Youtube as an example: they use IDs in the form of PEckzwggd78.

Why don't they use simple integers?

Or imgur.com - they also use IDs such as 9b6tMZS for images and galleries. Not sequential integers.

  • Why don't they use integers (particularly sequential ones)?

  • In what cases is it a wise decision to use such string IDs instead of integers?

closed as too broad by gnat, 8bittree, Bart van Ingen Schenau, BobDalgleish, amon Dec 2 '17 at 17:47

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

10 Answers 10

100

Youtube can't use sequentional IDs for two reasons:

  1. Its databases are almost certainly distributed, making sequential numbering complicated.

  2. It has a privacy option "Unlisted videos": those that don't show up in the search results, but are available if you know the ID.

Therefore, the video IDs should be reasonably random and unpredictable. Whether the ID is represented by digits only, or by a combination of letters and digits, is irrelevant: there is a trivial mapping from one representation to another.

  • 11
    Numeric ids dont have to be sequential – Sopel Nov 28 '17 at 10:02
  • 28
    @Sopel I think IMil's point is that Youtube needs to generate IDs that are sparse. In other words, if it is estimated that you will only ever need to store 2^40 items, in some architectures there are legitimate reasons for choosing a space of 2^80 or 2^120 bits. Examples of reasons are: reducing collision without technically checking for collision; using the sparseness of keys as part of making secrets hard to find (the "unlisted video"), etc. – rwong Nov 28 '17 at 10:33
  • 13
    @Sopel the question was "Why don't they use integers (particularly sequential ones)?" I explain that: 1) sequential IDs are undesired; 2) integers and strings are basically the same thing – IMil Nov 28 '17 at 11:01
  • 3
    The "therefore" clause doesn't logically follow but the two numbered points are correct. As an example of why randomness is not a necessary consequent: sequential numbering with uniform gaps will work to provide unique ids in multiple independent databases such that the results can be combined in a datawarehouse - this is a form of sharding. That is, suppose you anticipate no more than 10000 regional databases (perhaps you have only 10 right now so 10000 is sufficient). Then each db can have an identity column counting by 10000 with unique last 4 digits, there will be no collision on merge. – davidbak Nov 29 '17 at 2:09
  • 2
    @davidbak the requirement for randomness follows from (2). Uniqueness may indeed be obtained by assigning non-overlapping ranges to different database instances, but this would leave the IDs predictable. – IMil Nov 29 '17 at 12:24
75
  • On the form of the IDs: They're using Base64 (using the characters a-z, A-Z, 0-9, -, and _). This allows them to have 6 bits of information per character. YouTube uses 11-character video IDs, which means they can generate 26*11, or more than 7*1019 IDs. As Tom Scott put it, that's "enough for every single human on planet Earth to upload a video every minute for around 18,000 years." Base64 is also easy to work with, because 64 is a power of 2, which means every character represents an exact number of bits. We use hexadecimal (base 16) for the same reason.

  • On the non-sequential nature of the IDs: it means they don't need a synchronized counter between all the servers that assign IDs to videos. They can just generate a random number, check if it's already in use, and go from there. They could even assign each server a block of IDs to pick from and eliminate the duplication checking. I don't know if they're doing that, but they could.

  • Another reason for the non-sequential IDs is that it is what makes "unlisted" videos work. These are videos that won't show up in search results or as suggestions, but that are accessible if you've got the link. If you're using sequential counting, you can just go to a video, increase the ID by one, and the idea of unlisted videos is now broken.

  • Non-sequential IDs also help hide information from competitors, such as the total amount of videos, or the number of videos uploaded per timeframe.

I can highly recommend Tom Scott's video. His information is almost always both interesting and accurate.

  • 6
    Let's also point out that 11 characters of a base64 encoding store 66 bits of information, which means that they can easily map a 64bit integer into such a string. I.e. internally, they could use a 64bit int anyway (but need not do so). – Bernhard Hiller Nov 28 '17 at 11:29
  • 1
    For comparison, the conventional decimal representation could require as many as 20 characters, “wasting” up to 9 characters compared with Base64. – dan04 Nov 28 '17 at 22:30
  • The Tom Scott video explains this perfectly. – AGB Nov 29 '17 at 10:46
13
  • Integers do not scale that well, a "normal" 32-bit unsigned integer will max out just over 4 billion.

  • They may not want you to know how many items they have on line or keep track of the rate they are growing.

  • Letters can hold more information than digits, you need fewer letters to express the same "number". For a big indexer database this could add up.

  • 7
    1) one can use int 64 – Rakori Nov 28 '17 at 7:13
  • 4
    2) why? ........... they're all public anyway. those that aren't public -- aren't accessible. that's it – Rakori Nov 28 '17 at 7:14
  • 3
    3) can you elaborate? express what information ? – Rakori Nov 28 '17 at 7:14
  • 2
    For 1: same goes for int32 and int64. While int64 is potentially way larger, it could be not large enough. – Nepho Nov 28 '17 at 10:28
  • 3
    In the database you would store a number as a number. So a 32 bit int would take 32 bits. Text would have less density (how much poorer text is would depend on encoding) – Taemyr Nov 28 '17 at 11:27
8

1) Why do some websites use letters in their IDs? Are they strings?

We don't know if those websites store IDs in their database as strings. Numbers and strings are really the same to computers. A string is just a number, just shown with a different base. 'A' = 0x41 = 65 = 0b1000001, to the computer it's all the same. But if you display it, the larger the base, the shorter the representation, and shorter URLs are easier to read and share for humans. Sites like YouTube and Imgur use base 62 (letters, upper and lower case, plus digits) or larger (add a dash or other valid URL characters), which is relatively short for big numbers. What would you prefer to use, youtu.be/23489234892348234933 or youtu.be/B9k6KMrv8vh?

2) Why are non-sequential IDs used?

The answer by IMil explains it well:

Youtube can't use sequentional IDs for two reasons:

  • Its databases are almost certainly distributed, making sequential numbering complicated.

  • It has a privacy option "Unlisted videos": those that don't show up in the search results, but are available if you know the ID.

These also explain why the IDs are so large: (YouTube doesn't host 23,489,234,892,348,234,933 different videos, obviously)

  • When generating IDs, it's a problem if you accidentally generate the same ID twice, so you need a big ID space to prevent the birthday problem

  • People can just guess the URL of unlisted videos if the chance of any given valid ID being used for a video isn't very, very small.

  • 3
    > "YouTube doesn't host 23,489,234,892,348,234,933 different videos, obviously" I'm not so sure if this is obvious or not ;) – souser12345 Nov 28 '17 at 11:42
  • People can just guess the URL of unlisted videos if the chance of any given valid ID being used for a video isn't very, very small. -- how do you know if an unlisted video isn't accessible for everyone except its author? even if someone else has guessed its ID – Rakori Nov 28 '17 at 21:26
  • 1
    @Rakori because that is how Youtube works. – Josef Nov 29 '17 at 11:35
  • 2
    @progo I mean if every single person in the world has uploaded 3.3 billion videos to YouTube on average... ;) – Robin Nov 29 '17 at 18:03
5

why not just integers, particularly sequential ones? And when, in what cases is it a wise decision to such string ID instead of integers?

  • Better UTF-8 space - when you turn a number into a string you get at most 10 combinations per character (0-9), but when you allow any alpha numberic characters you get 62 combinations per character (a-z, A-Z, 0-9), so by using alphanumeric strings you can produce shorter urls than if you used numeric strings. This is important for sites where users are sharing urls -- like Youtube and Imgur.
  • Sequential integers are more difficult to produce. To produce a sequential increasing integer you must either have a single thread produce the numbers, or coordinate many hosts in a distributed system, and when you run a high volume application like Youtube or Imgur that doesn't scale as nicely as a randomly generated string (not to say that they are randomly generating)

As an aside, it's not necessarily the case that the internal representation is a string. They could very likely be encoding a numeric identifier as a alphanumeric string for the shorter url.

  • 1
    2) in case of a string ID, but you'll need to verify that a string ID has been generated already before inserting a new record into a db. what's the difference with an int ID then? – Rakori Nov 28 '17 at 7:16
  • @Rakorin Even when using something as simple as UUIDv4 the chance of collison is miniscule. Use enough randomness and the chance is pretty non-existent, so that the duplicity does not really need to be validated. – Andy Nov 28 '17 at 7:48
  • 1
    @davidpacker and how is that different from generating a longer integer? – Sopel Nov 28 '17 at 9:57
  • @Sopel As Samuel has pointed out, the integers would take up more space, i.e. be longer, than the strings. Otherwise, there really is not any difference. – Andy Nov 28 '17 at 13:07
  • 1
    @davidpacker only when printed – Sopel Nov 28 '17 at 13:14
2

As you've pointed out that it would be easy to use a universally unique ID just using numbers because under the hood everything is just 0 and 1 and you could expand the number to more precision going up to 128 bit or more.

I think the main reason is that, assuming some arbitrary fixed range like uint32 (just for the sake of an example), if you use letters as well you can have a shorter ID in total.

I imagine that it's an esthetics reason for the URL. Instead of having 4,129,873,773 with letters it's much shorter Fu837t (just fictious made up by me). A user might even be able to remember the URL for giving it to a friend. Platforms like Youtube usually have longer UUIDs than 32 bit because they would run out of space quickly.

  • 3
    This i think is the answer. Using strings is neither more efficient nor easier to maintain uniqueness. The reason is that its easier to represent as a url – Sopel Nov 28 '17 at 10:01
  • if a user is able to remember Fu837t, but can't he remember 2390? – Rakori Nov 28 '17 at 21:23
  • 4
    @Rakori: Fu837t would compare to 2223955238, so yes. The 2390 would be encoded as "Vg", so: also yes. – Mooing Duck Nov 29 '17 at 1:28
  • @MooingDuck, no. How do you know what the algorithm for generating that string ID is? – Rakori Nov 29 '17 at 4:49
  • 3
    @Rakori it is not an algorithm, it is an encoding. There are algorithms to transfer numbers between different encodings, but which one is used does't matter as long as the encoding is well defined. Url safe base64 encoding is well known and standardized. – Josef Nov 29 '17 at 11:39
2

A short URL is desirable since it makes linking and sharing simpler (e.g you can share a link in a SMS, it is faster to type and so on). Services like Youtube or Imgurl want you to share URLs casually, so this is an important consideration.

Using alphanumerical ID's rather than numerical means you need fewer characters to express an ID of the same bit-size. For example 6 digits give you a million unique id's but 6 alphanumeric characters (using the base64 set) gives you 68 billion unique identifiers.

For all we know, the alphanumerical identifiers could be sequential numbers, just encoded in an alphanumeric format like base64. But often commercial services eschew sequential codes to prevent people from guessing ID's and to avoid disclosing business information like the amount of customers.

1

There's several reasons why you would use non-numeric ids, but also understand that not all values with alphabetic characters are really strings. YouTube has the reputation of an incredible number of videos, on the order of 300 hours of video uploaded every minute (ref). The unique integers representing those videos can get quite long, so the use something like Base64 URL encoded numbers (ref).

Types of Identifier Representations:

  • Simple integers: (12345, 981027489382493)
  • Base 16 integers: 123456789abcdef -- also known as Hex
  • Base 64 integers: 9b6tMZS
  • Readable strings: 12032017-Read-my-awesome-article-01

They all have their strengths and weaknesses. The more unique characters you can use for your identifiers the fewer characters you need to represent a number. Base 64 numbers are a pretty good compromise because there is an established variant that works for URLs and compresses the number of characters needed to represent a number 6 to 8 (i.e. 3/4th the size).

Readable strings work for blogs because they can raise the searchability, and it's a lot easier to generate unique titles when the number of records is small.

1

Content hashes

The word "hash" is not found in the existing, nice, answers, so here we go:

Often, data can be identified by its content hash instead of an independent, artificial ID. This is particularly evident in software like git or file systems like ZFS where this particular property of using content hashes not only makes stuff easier (for example de-duplication), but also has other nice properties like trivial caching, a secure history, detecting bit rot etc.

Hashes usually come as hex numbers (or an even larger letter space), so that's why you don't see integer IDs. There simply are no integers (in those cases).

Hashes are good if your data objects are immutable (like in ZFS or git); they would be great to store images, for example, on large CDNs. I do not know whether those particular IDs actually are hashes, but it would certainly make sense (and as Michael Kjörling commented, short IDs are probably not hashes for obvious reasons - as comparison, git uses SHA-1 values which are 20 bytes or 40 hex digits).

  • 1
    At least Youtube video IDs are too short to be hashes. The birthday paradox applies; in short, on average, with a hash space of n bits, you will start seeing collisions after seeing 2^(n/2) input blobs. With ~60-70 bits in the ID, that's 30-35 bits of uniqueness, or a few billion entries. I'm pretty sure they host more videos than that by now. And, of course, most hashes are integers just fine; that they aren't normally printed in decimal form has no bearing on whether or not they are integers. Admittedly, the same data could probably be interpreted as floating-point binary data... – a CVn Nov 28 '17 at 13:58
  • 3
    @MichaelKjörling: Well, YouTube video IDs are too short to be cryptographic hashes, but there are plenty of hash functions that have 64 bits of output or less — CRC-16/32/64, Java hashCode(), etc. Of course, the shorter the hash, the more likely random collisions are. – dan04 Nov 28 '17 at 22:38
  • If you wanted people to remember the URL, you wouldn't have made it case-significant. And having to say "upper" or "lower" in front of every letter is much less efficient than just saying numbers. – Lenne Nov 30 '17 at 13:19
0

Ok one of the reasons is that the characters are sent as characters and not as integers anyhow. This is because of how an HTTP Get works.

When you say, "why not use an integer?" Well, the integer is then chopped up and every digit is sent as a character and you end up with a string of characters anyhow. So why not use all the options for a character?

There is also the human factor:

Take imgur for instance : https://imgur.com/*****/s6UqP

s6UqP,

The range for every character is: a through z capital, a through z sub-capital, and 0 to 9= 26+ 26+ 10 = 62 options for every position in the string. With five positions that's 916132832 possible combinations. If you would only use numbers, you would need 9 digits.

People can hold roughly 7 objects in memory, 9 digits is too much, 5 characters is doable.

Magical number 7

  • It remembers Gfycat: they use three words, two adjectives and an animal name. Because there are many possibilities (1502 adjetives and 1751 animals) they have more than 3 billion combinations using just three objects. – Gustavo Rodrigues Nov 30 '17 at 14:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.