0

I am working on interview questions from Amazon.com Software Development Engineer Intern Interview Questions.

One of the interviewees was asked "give a scalable system design of Amazon.com's order number generation service."

I did some preliminary research Amazon Order Number and found that Amazon generates a 17 digit order number of the form 3-7-7, where the last 14 digits are seemingly pseudo-random with psuedo random meaning generated by an "algorithm that uses mathematical formulas to produce sequences of random numbers" Psuedo-Random Definition

I verified one on my own and saw that one of my order numbers - 112-9036246-9502632 followed this guideline.

How would you give a scalable, as in "ability of a computer application to continue to function as its size is changed to meet user end" Scability system design of this? To me this order number generation service is already pretty scalable cause that 3-7-7 combination should allow for a great range of combinations to accomodate for a great number of users. But if you wanted this service to be more scalable, would you just add more digits to the end to allow for more combinations of order numbers, that way you can accommodate for more orders?

  • 2
    Scalability is not only about the total size, but primarily about the throughput. How do you guarantee order numbers are unique when they are generated on multiple servers, in multiple threads, in parallel? Do you prevent collisions from the start? Doesn't that decrease randomness or leak other information? How do you seed the random number generators? Do you rely on DB transactions to guarantee uniqueness? But doesn't that slow everything down since it's a single global lock? – amon Feb 19 '15 at 19:34
  • @amon Have a universal Amazon database and have a single lock on that database, so one server can insert a order number, and that lock would prevent other servers from checking until insertion is complete. – committedandroider Feb 19 '15 at 19:41
  • 2
    "a single lock on that database" is probably the definition of "not scalable" for this exercice. – AProgrammer Feb 19 '15 at 19:42
  • 2
    per my reading, in current form this is hardly a specific question, because it's poisoned with stuff like "How would you go about this?" and "Are there other factors you have to take into consideration?" If you really have something specific in mind (the rest of the question suggests that this might be the case), consider editing it into a better shape – gnat Feb 19 '15 at 21:19
  • 1
    @gnat you're right, i should have gotten rid of those phrases to make the question more specific. Is it better now? – committedandroider Feb 19 '15 at 22:52
2

The trick is in the first three digits. The last 14 digits are guaranteed to be unique within a certain domain, (say, a server,) so the first 3 digits must uniquely identify each domain. Therefore, every 17-digit number is guaranteed to be unique.

  • But could you scale the order number generation service by adding more digits? Is domain just amazon.com? – committedandroider Feb 20 '15 at 19:42
  • Yes, of course you scale the order number generation service by adding more digits, but that's not the point. Domain in this case is not amazon.com, domain is one of amazon's order-taking servers. So, for an order number to be unique, it needs to consist of a unique order-taking server number and a number that the server promises to be unique on the server. So, it scales as you add more servers. – Mike Nakis Feb 20 '15 at 20:13
  • So they're both ways of scaling the order number generation service? What are the pros/cons of doing it the adding servers way vs adding more digits way? – committedandroider Feb 20 '15 at 20:20
  • The "adding servers" method implies adding digits in the sense that when you have 999 servers and want to add one more to have 1000 of them, a digit will automatically be added. (Obviously.) – Mike Nakis Feb 20 '15 at 20:23
  • Simply adding digits to make the 14-digit random numbers even longer means increasing the storage capacity of each server by a factor of 10, which I am not sure is an option. – Mike Nakis Feb 20 '15 at 20:24

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