Database “sharding” came from Ultima Online? (2009)
raphkoster.com
raphkoster.com
https://www.youtube.com/watch?v=zyVTxGpEO30&pp=ygUPcmFwaCBrb...
However, I then dug into it a bit. From my digging 4 years ago (https://news.ycombinator.com/item?id=23460200):
> I spent some time crawling through the proceedings of Very Large Databases (VLDB) and the ACM Digital Library, and I could find no instances of "shard" used to mean the partitioning of a database prior to 2001. (That paper is "Minerva: An automated resource provisioning tool for large-scale storage systems" in Transactions on Computer Systems, free-to-read at https://dl.acm.org/doi/abs/10.1145/502912.502915.)
> Other the other hand, I found many papers citing the SHARD paper - more than the official count. That's a difficulty with citation counts of old papers: a lot of the papers citing it are also old papers, and we're not consistent at tracking the citations of old papers. Personally, I don't have a conclusion. The SHARD paper is decently cited, and its usage is close to the modern one. On the other hand, I can't find any smoking gun pre-1997 usage of "shard" in the modern meaning.
I started my digging thinking I would quickly find a paper using "shard" in the modern database context that predated Ultima Online. I could not find it, so now I think it's plausible.
This still sounds like a really hard problem, I can't imagine trying to do it 20 years ago. (WoW turns 20 in Nov, and it wasn't the first, though perhaps the first to reach such supercilious scale?)
You'd be surprised what's possible with efficient in-memory client-server code.
Half the cluster for Planetside was edge servers whose entire job was to handle inbound packets and distribute them to the relevant other clients. One copy of each update was sent to the zone server, and it was then responsible for updating adjacency lists so the edge could do its job. This gave us much closer to linear rather than quadratic scaling. Even then the packet forwarding code in the edge servers didn’t do full packet decode, it just dug into the header deep enough to determine packet type, which allowed it to know how to forward.
I think we launched on ~20 servers per world, each of which was a dual core 300 MHz P3. That could handle 5000 players in a world. Including raytracing their projectiles against an 8km x 8km mesh ;)
I can’t even find processor benchmarks that far back, but I’d guess we ran the entire cluster on less CPU than most cell phones have today.
Also, remember that the server cannot afford to trust the clients about anything, not can it let them have too much information about the world.
[1] https://pages.cs.wisc.edu/~dewitt/includes/paralleldb/ieee90...
https://en.m.wikipedia.org/wiki/IBM_1401
That was the best seller in history, at the time, but there are mechanical computers that played similar tricks going back to the early days of punch cards.
The Hollerith Tabulator won a competition in 1888.
https://www.census.gov/history/www/innovations/technology/th...
Anyway, yahoo probably sharded by the mid to late 1990s.
https://news.ycombinator.com/item?id=35479553 (90 comments)
https://news.ycombinator.com/item?id=23438399 (172 comments)
https://news.ycombinator.com/item?id=425765 (3 comments)
https://news.ycombinator.com/item?id=17926566 (1 comment)
https://news.ycombinator.com/item?id=16343939 (1 comment)
And related:
Database “sharding” came from Ultima Online? - https://news.ycombinator.com/item?id=35479553 - April 2023 (89 comments)
Database “sharding” came from Ultima Online? (2009) - https://news.ycombinator.com/item?id=34694397 - Feb 2023 (1 comment)
Database “sharding” came from Ultima Online? (2009) - https://news.ycombinator.com/item?id=23438399 - June 2020 (172 comments)
Database “sharding” came from Ultima Online? (2009) - https://news.ycombinator.com/item?id=17926566 - Sept 2018 (1 comment)
Database “sharding” came from Ultima Online? (2009) - https://news.ycombinator.com/item?id=16343939 - Feb 2018 (1 comment)
Did the term 'sharding' start with Ultima Online? - https://news.ycombinator.com/item?id=425765 - Jan 2009 (3 comments)
As for https://news.ycombinator.com/item?id=36848605 - I've added it to https://news.ycombinator.com/highlights. Thanks!
So I just rode around not knowing what was going on but hoping to find two coins so I could rub them together and negate time.
Runescape is the only other game from that era (and which shares a lot of gameplay similarities) that has that much staying power.
Its a sandbox game just like Arcage, Neverwinter Nights, Albion Online, Everquest, Star Wars Galaxy, Eve Online, Black Desert Online, etc in which the game's goals tacitly produce a local society, typically from players' in-game avatar "Characters" just playing the game. PvP is emphasized on many of the servers.
Right now there is a very good UO Freeshard server called "UO Outlands" with hybrid rules that are quite satisfying and with updated maps/dungeons/landscapes designed to encourage the classic vibes you've heard about and aren't really available in other, modern games.
If you just want to take a look, there is a Youtuber named "Trammie", he prefers to play a pure-thief character and he semi-regularly records streams of live play. Its a good look at one high-level play style that is nearly unique to UO and still available.
Easing into the mechanics, minutiae, and overall obscurity of the game is a different beast entirely, but a lot of things in there, while worn out over time, have a handworn feel like none other, which itch just the right niche.
Oh, yes. A greenfield game can just decide on mechanics, but UO is of course a continuous title with evolving technology and capabilities over decades! I never played the classic OSI (Official) server in the 90's or early 2000's and was introduced to freeshards directly nearly 15 years after the original launch. It feels a bit like digital archeology or anthropology from that perspective.
I was interesting in the scriptable clients, and endlessly tunable character development, as well as the idea of risk vs reward gameplay. To my great surprise, there seemed to be a vibrant and thriving social community in this thing that I and everyone else would have pointed to as a Dead World. Recommended.
For sure. Significant strides to be had with Razor, the accompanying script utility.
> as well as the idea of risk vs reward gameplay.
Be wary of the old heads that happen to stick with their solo thieves and PKs. For all intents and purposes, see where the biggest clans are raiding.
> To my great surprise, there seemed to be a vibrant and thriving social community in this thing that I and everyone else would have pointed to as a Dead World. Recommended
Many a legend even poured over from back in the day, with guys like Funeral, a player killer. Though, deco people are less notorious.
Interestingly enough, this new game is NOT going to have any shards or sharding at all - not even instancing - but just many (procedurally generated) planets, that are all part of the same shared universe and economy.
Thus, some of the very unique ambitions behind UO and SWG might actually become part of a new, more modern game:
https://starsreach.com/ (Fair warning: the graphics are still very early...)
Reading the manual would probably have helped but being 6, I understand how you didn't (or maybe didn't even have access to it). I had similar experiences with other games when I was a similar age :)
It wasn't until much later (maybe mid-teens) that I saw/heard the expression "not having two coins to rub together" as being used as a euphamism for being poor and it clicked into place.
in the "Game Coding Complete, Fourth Edition" book by two programmers who worked on Ultima and Sims (and other Origin/EA games of the time) back in the day, they share some war stories of programming, and if memory serves there is a portion where they talk about the original design, and the realization that lead to the sharding and how the login and shard system worked in the game.
Also, unrelated, a really neat war story about a guy who put in debug code to generate certain audio cues while a game was running to catch a bug.
The book all in all was a fun read if only for all these stories, and generally remember good coding guidelines as well but it is using older C++ that may not stand up to modern critique.
I ended up digging the book out and finding the passage; hopefully it's ok to share because it's an amazing story and helps illustrate what makes that book so great to me:
"The best caveman debugging solution I ever saw was one that used the PC speaker. Herman was a programmer who worked on Ultima V through Ultima IX, and one of his talents was perfect pitch. He could tell you the difference between a B and a B flat and get it right every time. He used this to his advantage when he was searching for the nastiest crasher bugs of them all - they didn't even allow the debugger window to pop up. He wrote a special checker program that output specific tones through the PC speaker and peppered the code with these checks. If you walked into his office while his spiced-up version of the game was running, it sounded a little like raw modem noise, until the game crashed. Because the PC speaker wasn't dependent on the CPU, it would remain emitting the tone of his last check. "Hmm...that's a D," he would say, and zero in on the line of code that caused the crash."
- Game Coding Complete, Fourth Edition
Gamedev people came up with creative devices, like using pedal to debug-break into the game.
At guru level, of course, you no longer need the radio.
Old gamedev books really have some wild stuff.
Sarin, DeWitt & Rosenberg, Overview of SHARD: A System for Highly Available Replicated Data, Technical Report CCA-88-01, Computer Corporation of America, May 1988
https://en.wikipedia.org/wiki/Shard_(database_architecture)#...
Also, maybe university libraries and/or Archive.org could help you with the copyright question?
I can totally understand that, but at the same time I'd really love to have a look at that as well. Maybe you could reach out to archive.org and see if they'd be interested in hosting a copy?
Following this link here: https://shkspr.mobi/blog/2021/06/where-is-the-original-overv...
In a comment at the bottom it references a paper published by a few people working jointly with Computer Corporation of America, MIT & Boston University.
If you view that referenced paper "Correctness Conditions for Highly Available Databases" by N. Lynch, B. Blaustein & M. Siegel (https://apps.dtic.mil/sti/pdfs/ADA171427.pdf), and look at section 1.2 it clearly describes "SHARD: (System for Highly Available Replicated Data)" as being underdevelopment at CCA. It also says if you want to learn more about Shard, see the paper's reference [SBK]. Checking out the references section of that paper it lists the following for [SBK]:
Sarin, S. K., Blaustein, B. T., and Kaufman, C. W., "System Architecture for Partition Tolerant Distributed Databases," IEEE Transactions on Computers C-34, 12 (December 1985). pp. 1158-1163.
Which means there was a paper published in 1985, describing the in development Shard system.
It is possible that in 1985 they hadn't yet named the system "Shard", and it only got that name by 1988 - but it'd be interesting to check out that 1985 paper and see if they used the term Shard at all.
And the concept as described in how he brought it from the Sosarian Lore is laser etched into my head, because along the same fantastical lines we also have the infamous The Dark Crystal - and so having that be a strong element in the SciFi-Fantasy DNA of anyone of my generation into gaming, sci-fi etc - it was completely grokked immediately and understood.
UO is one of the golden eras of my gaming DNA.
Let me cut through the hype: they’re better than you think. Real legends.
I was early in the distributed database game, these guys were earlier.
Legends.
Another thing that kind of got me into automation was UOPilot. I think, this kind of automation wasn't welcomed (esp. on official servers), but I never played the game on an official server :) UOPilot scripts were sometimes a good source of game gold too. Which was another interesting aspect of games like UO, and sort of a dream of a lot of game developers: to get players to do something that's challenging them to learn more about practical subjects (programming being one such subject).
It's kind of a shame that this path wasn't really more explored. Somehow the games that try to have practical application always end up being boring and poorly designed in general. Successful games tend to cater to the leisure aspect of human nature and try to stress players as little as possible, so it's hard to squeeze any real-world challenges into the game.
Wait, what? Never knew about this, that's a fun little fact.
The wiki says this:
> Flickr was launched on February 10, 2004, by Ludicorp, a Vancouver-based company founded by Stewart Butterfield and Caterina Fake. The service emerged from tools originally created for Ludicorp's Game Neverending, a web-based massively multiplayer online game. Flickr proved a more feasible project, and ultimately Game Neverending was shelved.
Glitch got pretty much exactly as traction as Game Neverending, which is to say "nowhere near enough to be economically viable". This time they spun off their internal chat tool to create Slack.
So I had to do some googling for what seemed like a pretty obscure thing that morphed into a huge thing that takes up way too much of my brainpower these days, and found this story about the shutdown of Glitch and the start of Slack https://johnnyrodgers.is/The-death-of-Glitch-the-birth-of-Sl...
And if you do a search on HN you will see plenty of other links about UO and sharding.
Shard (database architecture) > Etymology: https://en.wikipedia.org/wiki/Shard_(database_architecture)#...
Partition > Horizontal partitioning --> Sharding: https://en.wikipedia.org/wiki/Partition_(database)
Database scalability > Techniques > Partitioning: https://en.wikipedia.org/wiki/Database_scalability
Network partition: https://en.wikipedia.org/wiki/Network_partition
it's so exhausting needing to just read comments to get the actual, real truth
I'd always assumed they were the same thing, and the choice just gave you a hint of the speakers background. Old school DBAs are way more likely o say "partitioning", game devs or young FE devs will almost always use "sharding".
With this, sharding and horizontal partitioning are essentially the same, and the term partitioning by itself just means splitting up the data in some way (could be horizontal, vertical, or other).
That said, I've also heard people use shard and partition interchangeably in the general form, in which case, you get "horizontal sharding" and "vertical sharding".
I'd start by googling horizontal vs vertical partitioning.
That's not correct: https://en.wikipedia.org/wiki/Shard_(database_architecture)#... al_partitioning
For example, horizontal partitioning is often used within the same schema on the same instance in order to have separate indexes for (say) current vs. historical data. That's not what is meant by sharding, however; shards are separate instances.
> Sharding goes beyond this. It partitions the problematic table(s) in the same way, but it does this across potentially multiple instances of the schema.
"Beyond this" but still "potentially across multiple instances". Anyway, with your framing sharding kind of becomes "distributed horizontal partitioning".
I remember hanging out with the Suicide Girls tech team at The Perl Conference or The Open Source Conference in maybe '99 or 2000, the one (first one?) in San Jose. So many cool stories about unbelievable (to me) scale networking and storage and bandwidth use and their website user behaviour monitoring and adaptive bandwidth limiting...
Even with early 00s tech you could store more rows in a DB than the population of the USA. When indexed the lookup can be done in milliseconds. If a user database got too hot we would move half the users off it and cut a new user DB, and update their references. Held together with a lot of Perl scripts and duct tape, a far simpler time.
For instance, there's a lot of situations out in the world where you don't really need all your customer data piled into one database. You can easily shard out one database per customer. But a characteristic pitfall of that approach is the generally pathological distribution of customer size. You'll often end up with That One Customer that is your biggest customer and therefore blows out your database size in their own shard. While it's nice that you can at least isolate the rest of your customers from the blast radius, a system that you wrote from top to bottom otherwise to be in a single database per customer can be very, very difficult to fix for That One Customer... and guess what, they're also your biggest customer so management is going to come down on you like a sack of bricks to keep them running.
This is a lot more viable in 2024 than it was in 2004. You can scale that single database up to a lot more power nowadays, between all the CPU improvements and those glorious, glorious SSDs. But as is the way of things in engineering, where every benefit comes with corresponding risks and costs, that means that if you do hit the DB barrier with That One Customer, you'll hit it all the harder, because now you're entrenched with a 64-core DB on terabytes of RAM, and all the corresponding code complexity behind it, that you're going to try to redesign on the fly to work with within-customer sharding, which involves a lot more code than when someone blew out DBs in 2004.
This comes with its own issues when you have to update the DB schema too, although, so does the One Big Database.
Lovely font, isn't as cramped as you usually come to expect from older websites but also has great information density, pleasing palette (although the menu text colour could use some love imho), etc...
I'm a huge fan.
The answer to the question in the title, and at the end, seems to be yes! Google n-gram viewer has the first references to database shard/sharding in 2005, and Ultima Online came out in 1997.
https://books.google.com/ngrams/graph?content=database+shard...
Some sort of world-crystal being shattered into small pieces, or something...
(Wikipedia)