For context, Raph Koster is not only the person who designed Ultima Online, but generally considered one of the top theoricians in game design. This isnt some guy who has a small blog and came up with a neat explanation for how some word came about in the early days of the web. Its the guy who did it.
I find it incredibly hard to believe that ultima online was the first application of database sharding, but it may very well be the source of the name. "key-based partitioning" doesn't have the same ring to it, but has existed since the early 90's and possibly late 80's.
I can't seem to find it right now, but I read an article, shared in the "awesome-scalability" GitHub repo, which referenced a 1978 paper, written by a couple of IBM researchers, about sharding and a lot of seemingly modern database things.
Agreed. I have worked at a Fortune 100 firm where its business ran (still runs) off of an ERP sharded into 100 instances, each representing one key facility since the mid-90s. It took extra work in the early days to centralize analytics and manage deployments and data, but it has been very resilient (low blast radius in today's terminology) and natural for low risk deployments, rolling out of upgrades to one site, then the rest in batches.
> 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.
A lot of innovations came from MMOs, so it shouldn’t be that surprising. Especially the big ones push the cutting edge in a way that no other applications do.
One MMO tech I always got a kick out of was WoW using Bit Torrent for updates at a time when it was massive and that bandwidth would have been brutal to output.
"serve [seemingly] <50ms latency N:N coordination between thousands of clients, sometimes who are all literally in the same place (events, cities etc) expecting to observe their and other users actions ~immediately"
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?)
It only really works because it isn't N:N, it's N:1:N, and it's aggressively sharded (you have to have a separate EU and US shard if you don't want one to have transatlantic latency, which is 50ms all on its own). While you can have a few thousand people in one place, the interactions are limited in ways which avoid N^2 blowups.
You'd be surprised what's possible with efficient in-memory client-server code.
Yup, and there are some non- obvious ways to offload compute that were necessary back in those days.
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.
I've heard of tricks like player position prediction/interpolation by the clients, in particular for the FPS/Sim genres, which I guess is mainly aiming at mitigating "lag spikes" more than optimizing the network traffic, but it looks like it could give some leeway to servers as well ?
Prediction lets you see through time but doesn't reduce the overall amount of work you have to do - the update confirming the prediction has to be sent eventually.
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.
Interesting, I had always assumed shard came from a specific company's technology and never gave it much thought. Kinda like how we talk about blade servers because of ibm's marketing.
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.
Yes, the technique is obviously predated by Ultima Online. The question we're trying to answer is specifically about the etymology of sharding in the database context.
Dan, is there a way to automatically add related older discussions to the top of a new item, in a similar way to submitting the same URL within a certain time will take you to the existing discussion rather than create a new one?
HN does that if the URLs are identical (or nearly identical) and a submission has had significant attention in the last year or so. But for related stories that have different URLs, it's a harder problem. Our intention is to build support for this that will be community-curated. Someday!
I have never played modern Ultima. I played a very early version on the Mac SE when I was about 6 and I didn’t understand anything that was going on. I just rode around aimlessly. The one thing I remember is that the menu had a “negate time” option and when I selected it a message came up that said “you don’t have two coins to rub together”.
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.
Ultima Online in the age of dialup and early DSL was a history-altering game for MMO's. I still log on to UO Forever servers every once in a while (a modified game server with accelerated skill learning) to level up a character and scrabble together enough gold to build and furnish a house. It was such a vast game and the sheet depth of it for a game of that time was unprecedented. I still think to this day it is one of the best "just go do what you want to do" MMOs out there, something that New World didn't even get right 20 years after with considerably more resources and advances behind it.
Runescape is the only other game from that era (and which shares a lot of gameplay similarities) that has that much staying power.
For me, the best part of UO was the ability to extend it, for me OSI was never pleasant to play on, but I was on an unofficial shard with Dragonlance saga background and it was the best time of my life, I don't think any other MMO could've been so extendible to fully implement that saga at those level of details
since Ultima deals with time travel, I accept your "history altering" claim. Long live Lord British! (RG has been to the deepest sea and the space station, so who can say he doesnt also have a time machine. He is a real adventurer who made Ultima- one of the best adventure rpg lines ever)
Ultima Online is a very unique social experience compared to today's landscape of multiplayer games, and there are different "Eras" of the game which can impart a particular flavor to the experience, eras like: UO: Renassaince, UO: Lost Lands (aka T2A mechanics), and others.
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.
Raph Koster is also currently working on a new game, that aims to take this ideas of social experience and player-driven virtual society and push it beyond what they were able to do with UO. (Also with less PK-ing, griefing, etc. - things he regretted about UO, but many people today consider synonymous with sandbox)
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:
Trammie Surprise, as he was formerly known, also runs the SQZD clan, who are often spotted in the wilds and around their homes, PvPing, thieving, and whatnot. They're one portal for easing into the local communities in Outlands.
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.
>Easing into the mechanics, minutiae, and overall obscurity of the game is a different beast entirely, but a lot of things in there [...] have a handworn feel like none other
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.
You played Ultima II (1982). It had a "negate time" command to stop time for enemies in combat, but it used "strange coins". I think it only used one, the "two coins to rub together" was just a figure of speech.
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 :)
Haha yeah I don't think there was a manual. I'm pretty sure it was pirated on a floppy disk or something with a label written in biro in my step father's desk.
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.
I played Renaissance and the following one on unofficial servers for about 6 years between 2003 and 2010. My offline and online friends would easily play 6-8 hours per day, and when we were offline we were talking about it. It was like a second life and an incredible escape, but looking back at it we were all addicted to it pretty badly. I get flashbacks and cravings to this day.
semi-related, but also helps me to believe that this is the case (and not only because the different regional servers were called "shards" in Ultima Online):
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.
Ha re: audio cues for debugging… your pc speaker is truly an underused tool when debugging something infrequent… for example our system processes a lot of xml data and usually it’s fine but for our test suite hearing beeps and knowing there are server side issues immediately is a great thing
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."
I bought a copy of Game Coding Complete a long time ago, but couldn't remember which edition and your comment made me curious. Turns out I have the first edition from 2003.
Hmmm... I vaguely recall the term "shards" when referring to DB/2 running on S36, S38, and later newfangled AS/400 across the world. When presenting the data in a single pane, some "shards" would come in late, or be broken, and require reconnecting.
The wikipedia entry for this confirms two sources depending on context, and in your case it came from a late 80s paper:
Sarin, DeWitt & Rosenberg, Overview of SHARD: A System for Highly Available Replicated Data, Technical Report CCA-88-01, Computer Corporation of America, May 1988
From a quick search right now, the term seems to have come from that same system, but the first reference appears to be older than 1988. It looks to be possibly 1985.
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.
I seem to remember a conversation here on HN not too long ago where people tried to reconstruct the history behind "sharding" and, in particular, tried to find that 1980s paper you mentioned – without success. I believe they even contacted one of the authors.
> I'm unsure of the copyright status so I'm a bit reluctant to share it.
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?
I found that paper title as well when looking into this exact question. That paper does not have the number of citations I would expect if it is the source of the term. It's possibly the source, but it's not obviously the source.
I worked with db2 people back in 98 and they talked about shards. They worked down in some cave in the basement that smelled like folgers coffee, feet, and camel filter bbq sauce. I would offer them a roll of TP each and every time they said the word. Their office chairs had seat-cushions that looked like they were pulled out of a dumpster fire, worn out and melty looking. With all the red meat, nicotine, and caffeine, Im assuming someone sharded there at least once. Maybe that is what got those seat cushions all worn out.
AS one of the early big players of UO (In that it consumed an entire wall of machines in the Intel Game 'DRG' Lab in the late 90s - Shards came from UO.
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 has pioneered many things. One that really occupied me for years is the ethics of online communities. Stuff like PK behavior, in-game organization of players motivated by very simplified but still human-like wants and needs. But, I think, they invented the term "sharding" rather than the technique itself.
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.
> Flickr, of course, was born as an MMO called Game Neverending
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.
Eventually Butterfield and Fake got bored with Flickr and created Game Neverending 2: Glitch.
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.
Glitch the game never even showed up on my radar. Too bad (or maybe, for the best) it was never something I heard about.
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...
Classic Game Postmortem: Ultima Online [1], I think that goes into the origin of Shard. ( Sorry I didn't save down the time like but it is an interesting video for those into UO )
And if you do a search on HN you will see plenty of other links about UO and sharding.
I signed up for beta testing of UO and beta of roadrunner cable modem and I still have the Beta cd and cable modem. I bet you can narrow down what city I was in from that but oh well. I might still even have that old acer pentium 75 in the attic that was delivered damaged to my employer and was comped by ups insurance and taken to my personal dumpster and fixed by yours truly. my first very own computer. I learned to program on that thing and got a bank job just a few months later. gradually this has taken me around the world in 8 different countries for long on-site implementations. I even have dual citizenship now and live by the sea in a nice hot place. I was 19 years old when it kicked off. I blame the video games for all this. Btw did you know Time Bandits movie was a heavy influence on Ultima? And is Marvel's multiverse concept inspired by Ultima sharding also? I would bet a dollar. Well everytime I think about portability and scalability problems I am sure UO is back there somewhere influencing my work.
Marvel's multiverse goes way further back -- in 1970, Avengers #85 introduced the alternate universe Squadron Supreme, for example. There's a ton of classic SF along these lines as well. H. Beam Piper's Paratime stories come to mind.
Maybe you are talking about Ultima Online, because the original Ultima games predate Time Bandits. Also, Marvel multiverse would have been mostly influenced by DC Comics alternate Earths, with Earth-2 introduced in 1961.
Richard G was HEAVY into time bandits (1981) and Ultima 2 (1982) on were heavily influenced and easter eggs for the movie are spread all over. The airplane in New San Antonio for example...
Hey Broadsword, I know you're reading this. All those players from early days of UO grew up and some of them are now using non-windows machines. Don't be a tool, and create proper macos and linux clients already. Sincerely, players.
It was called partitioning and existed long before. The syndrome of "new" people believing they have invented something, naming it without realizing it already had been invented long ago and already had a name, is quite common.
Right, and it says that right there in the article that "database partitioning" had long been around but they needed a word to explain it within the fiction that would make sense in the game. So I'm not sure how this observation you that you're making about some "syndrome" is at all relevant, unless you're trying to make the case that UO was a counter-example of the phenomenon.
The blog post is about the name "sharding", as opposed to the concept of partitioning. True, this is not obvious from the title alone, but the post is pretty clear.
Do you have some hints or keywords I can Google to learn what the differences are?
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".
So some people will refer to "vertical partitioning" (ie splitting up by table or column) and "horizontal partitioning" (ie splitting up a table by rows, via some shard scheme or key).
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.
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.
I think people just use the terms slightly differently. Even the Wikipedia article you linked contradicts itself.
> 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...
Curious if there is a sharding scheme that can scale indefinitely for both the total size of data and total number of data objects? S3 apparently can do it, but I’ve never seen any publication talking about it. I’m aware of popular techniques, but they all have practical limits. For instance, consistency hashing seems good, but in reality too big a cluster will lead to increasingly severe membership flapping. Placement lookup seems flexible and flexible, but will eventually lead to the challenge of scaling up the placement driver for its too large index or metadata.
I worked at LiveJournal and we were sharding there since the late 90s. We ended up with 50 +/- Database pairs and 1 Global Master DB pair serving millions of users in the US (They all started on MySQL and my team moved them over to Percona) We would cut the shards manually when a database would fill up with too many users. We only had to do it once or twice a year, since the only data on the global master was a reference to the user id and the database where your data was stored, it scaled well enough to run the #1 or #2 largest social media site in the US.
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.
Total separation between individual smaller DBs scales indefinitely. If you can define domains that need no real-time cross-referencing at all, then this works. This isn't a snarky answer because that defines a fairly specific situation, and has its own specific pitfalls, but it is a viable answer.
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.
Would this help designing an object store, though? Case in point, S3 has unlimited bucket size, and they achieved that adding new servers will always increase the performance and reliability of the S3 cluster (they call it taking the advantage of the scale). I'd imagine that the key to achieve such is the sharding strategy, or the strategy of data placement in general. In contrast, MinIO makes it O(1) operation to find the node to write, but it has to ask all the participating nodes, at least a subset of them, to figure out which node to read from for a given object. To that end, MinIO's salability will hit a wall at some point.
I know commenting on website design is off-topic, but this is praise rather than the typical grousing.
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 find this hard to parse: link bit rot due to its age, there's some likely tongue-in-cheek references to himself, the layers of people and companies, UO mythology...
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.
Offtopic: One of my college roommates made ~$5k USD from macroing the creation of items like gold in UO for resale. Maybe that's another kind of sharding?
That seems quite late. Ticketmaster was effectively doing sharing in the late 60s. It was one of the reasons they could scale early on when others couldn't.
This was my interview question out of college when i got hired , remember coming up with sharding as a solution , there is nothing novel with sharding , its just common sense . It was prbably invented and reinvented multiple times
Funny thing about time. Trace back long enough and find folk that think what you are doing is magic. Trace forward far enough and it becomes "common sense".
