6 ms·
Database “sharding” came from Ultima Online? (2009)
- tetrisgm 2y agoFor 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.
- deleted 2y ago[deleted]
- tgtweak 2y agoI 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.
- strken 2y agoThe article contains the literal quote "It means database partitioning — of worlds." I don't think it is claiming that UO invented partitioning.
- deleted 2y ago[deleted]
- prepend 2y agoThe technique has existed forever. I think UO called is sharding and the name stuck from them.
- deleted 2y ago[deleted]
- nilsherzig 2y agoI 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.
- deleted 2y ago[deleted]
- gregw2 2y agoAgreed. 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.
- nemo44x 2y agoKey-based partitioning has existed since card catalogs at libraries and I’m sure there’s examples from before then.
- runevault 2y agoRaph's practical creativity talk is still one of my favorite I've watched from GDC. https://www.youtube.com/watch?v=zyVTxGpEO30&pp=ygUPcmFwaCBrb3N0ZXIgZ2Rj https://www.youtube.com/watch?v=zyVTxGpEO30&pp=ygUPcmFwaCBrb...
- pchristensen 2y agoI'll put in a plug for his book Theory of Fun for Game Design (https://www.amazon.com/Theory-Game-Design-Raph-Koster/dp/1449363210 https://www.amazon.com/Theory-Game-Design-Raph-Koster/dp/144...). It's a great read that's accessible but also deep and thorough.
- Sakos 2y ago> 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.
- mintplant 2y agoAnd Slack came from their second attempt at an MMO, Glitch.
- egypturnash 2y agoEventually 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.
- Sakos 2y agoDidn't realize it was the exact same people who made Slack. Geez, I wish I could be that accidentally successful, much less twice in a row.
- meiraleal 2y agoThey are the best at creating anything besides games. Are they working on Game Neverending 3 already?
- thegabriele 2y agoYes, in which they needed a new AI for the NPCs and spawned LLMs
- TeMPOraL 2y ago
- refulgentis 2y agoI 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. https://books.google.com/ngrams/graph?content=database+shard%2Cdatabase+sharding&year_start=1800&year_end=2022&corpus=en&smoothing=3 https://books.google.com/ngrams/graph?content=database+shard...
- hooby 2y ago"Shards" are the inlore explanation in Ultima, for why there would be multiple copies of the game world existing in parallel (the different servers). Some sort of world-crystal being shattered into small pieces, or something...
- dboreham 2y agoIt 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.
- layer8 2y agoSharding is a specific type of partitioning, it’s not a synonym.
- bigiain 2y agoDo 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".
- Ozzie_osman 2y agoSo 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.
- da-holland 2y agosemi-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. [0]: https://www.amazon.com/dp/1133776574 https://www.amazon.com/dp/1133776574
- other_herbert 2y agoHa 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
- da-holland 2y agoAbsolutely! 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
- samstave 2y agoAS 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 is one of the golden eras of my gaming DNA.
- westurner 2y agoWikipedia has: Shard (database architecture) > Etymology: https://en.wikipedia.org/wiki/Shard_(database_architecture)#Etymology https://en.wikipedia.org/wiki/Shard_(database_architecture)#... Partition > Horizontal partitioning --> Sharding: https://en.wikipedia.org/wiki/Partition_(database) https://en.wikipedia.org/wiki/Partition_(database) Database scalability > Techniques > Partitioning: https://en.wikipedia.org/wiki/Database_scalability https://en.wikipedia.org/wiki/Database_scalability Network partition: https://en.wikipedia.org/wiki/Network_partition https://en.wikipedia.org/wiki/Network_partition
- distantsounds 2y agowhy is every social media network now just "post something with varying levels of correctness because it farms engagement" it's so exhausting needing to just read comments to get the actual, real truth
- SatvikBeri 2y agoDo you realize that the linked Wikipedia post agrees with the article? It lists Ultima Online as one of two likely sources for the term "sharding."
- westurner 2y agoYup, I realize that the post could have originated from that section of the wikipedia article; or they are relying upon common sources.
- westurner 2y agoNone of this is incorrect. Why are people so disrespectful about others doing the work?
- WaitWaitWha 2y agoHmmm... 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.
- brandall10 2y agoThe 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 https://en.wikipedia.org/wiki/Shard_(database_architecture)#Etymology https://en.wikipedia.org/wiki/Shard_(database_architecture)#...
- codethief 2y agoI 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.
- mindcrime 2y agoYes, that was this discussion: https://news.ycombinator.com/item?id=36848605 https://news.ycombinator.com/item?id=36848605
- renewiltord 2y agoActual paper did exist but no one has a copy anymore according to the contacted author. It was an internal Xerox memo.
- edent 2y agoFWIW, I do now have a copy. I'm unsure of the copyright status so I'm a bit reluctant to share it.
- mindcrime 2y agoPreviously on HN: https://news.ycombinator.com/item?id=35479553 https://news.ycombinator.com/item?id=35479553 (90 comments) https://news.ycombinator.com/item?id=23438399 https://news.ycombinator.com/item?id=23438399 (172 comments) https://news.ycombinator.com/item?id=425765 https://news.ycombinator.com/item?id=425765 (3 comments) https://news.ycombinator.com/item?id=17926566 https://news.ycombinator.com/item?id=17926566 (1 comment) https://news.ycombinator.com/item?id=16343939 https://news.ycombinator.com/item?id=16343939 (1 comment) And related: https://news.ycombinator.com/item?id=36848605 https://news.ycombinator.com/item?id=36848605
- dang 2y agoThanks! Macroexpanded: Database “sharding” came from Ultima Online? - https://news.ycombinator.com/item?id=35479553 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 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 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 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 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 https://news.ycombinator.com/item?id=425765 - Jan 2009 (3 comments) As for https://news.ycombinator.com/item?id=36848605 https://news.ycombinator.com/item?id=36848605 - I've added it to https://news.ycombinator.com/highlights https://news.ycombinator.com/highlights. Thanks!
- mysterydip 2y agoDan, 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?
- deleted 2y ago[deleted]
- ksec 2y agoClassic 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. [1] https://www.youtube.com/watch?v=lnnsDi7Sxq0 https://www.youtube.com/watch?v=lnnsDi7Sxq0
- hackermeows 2y agoThis 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
- DaoShen 2y agoFunny 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".
- dools 2y agoI 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.
- tgtweak 2y agoUltima 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.
- lnxg33k1 2y agoFor 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
- crawfishphase 2y agosince 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)
- night862 2y agoUltima 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.
- jszymborski 2y agoI 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'm a huge fan.
- wdr1 2y agoThat 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.
- genter 2y ago> Ticketmaster was founded in Phoenix, Arizona in 1976 (Wikipedia)
- greentext 2y agoYes. A lot of tech history has its roots in gaming. And Trammel is for carebears.
- bigiain 2y agoA lot of the rest has it's roots in porn. 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...
- hintymad 2y agoCurious 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.
- deleted 2y ago[deleted]
- oceanplexian 2y agoI 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.
- jerf 2y agoTotal 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.
- benreesman 2y agoI had the pleasure and privilege of working briefly with some guys who worked on Ultima Online, real OGs. 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.
- mentos 2y agoIf there are any anecdotes you can share I'd love to hear before they get lost to time.
- crawfishphase 2y agoI 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.
- _huza 2y ago[dead]
- BryantD 2y agoMarvel'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.
- kagakuninja 2y agoAnd it was probably heavily influenced by DC Comics alternate earths. Earth-2 was introduced in 1961.
- kagakuninja 2y agoMaybe 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.
- 2y ago
- kristianp 2y agoPerhaps they learnt the word "shard", like I did, from the movie The Dark Crystal (1982), which is also in the Fantasy genre. https://www.imdb.com/title/tt0083791/ https://www.imdb.com/title/tt0083791/
- gokaygurcan 2y agoHey 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.
- crabbone 2y agoUO 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.
- scott_s 2y agoPotentially. I was also skeptical of this four years ago, and said as much on here (https://news.ycombinator.com/item?id=22972538 https://news.ycombinator.com/item?id=22972538). However, I then dug into it a bit. From my digging 4 years ago (https://news.ycombinator.com/item?id=23460200 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 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.
- MichaelZuo 2y agoA 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.
- jjice 2y agoOne 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.
- mrsilencedogood 2y ago"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?)
- hi-v-rocknroll 2y agoOfftopic: 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?
- sroussey 2y agoI was doing db sharding in the 90s, not sure what the news of this was in 2009.