[HN Gopher] Database "sharding" came from Ultima Online? (2009)
___________________________________________________________________
Database "sharding" came from Ultima Online? (2009)
Author : fanf2
Score : 279 points
Date : 2024-08-25 20:42 UTC (1 days ago)
(HTM) web link (www.raphkoster.com)
(TXT) w3m dump (www.raphkoster.com)
| leshokunin wrote:
| 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.
| tgtweak wrote:
| 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.
| strken wrote:
| The article contains the literal quote "It means database
| partitioning -- of worlds." I don't think it is claiming that
| UO invented partitioning.
| prepend wrote:
| The technique has existed forever. I think UO called is
| sharding and the name stuck from them.
| nilsherzig wrote:
| 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.
| gregw2 wrote:
| 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.
| nemo44x wrote:
| Key-based partitioning has existed since card catalogs at
| libraries and I'm sure there's examples from before then.
| runevault wrote:
| Raph's practical creativity talk is still one of my favorite
| I've watched from GDC.
|
| https://www.youtube.com/watch?v=zyVTxGpEO30&pp=ygUPcmFwaCBrb...
| pchristensen wrote:
| I'll put in a plug for his book Theory of Fun for Game Design
| (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 wrote:
| > 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 wrote:
| And Slack came from their second attempt at an MMO, Glitch.
| egypturnash wrote:
| 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.
| Sakos wrote:
| Didn'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 wrote:
| They are the best at creating anything besides games. Are
| they working on Game Neverending 3 already?
| thegabriele wrote:
| Yes, in which they needed a new AI for the NPCs and spawned
| LLMs
| TeMPOraL wrote:
| Hopefully the increased energy needs for advanced AI in
| Game Neverending 4 will lead to a major breakthrough in
| fusion power.
| bigiain wrote:
| I'd love to be "that guy" who fails at all my game
| attempts, but accidentally creates businesses like Flickr
| and Slack along the way...
| mygrant wrote:
| Caterina had nothing to do with Glitch or Slack. Stewart
| obviously did, but so did a lot of other GNE and Flickr
| founders and employees.
| cdchn wrote:
| 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...
| BlueTemplar wrote:
| Heh, this reminds me of how Discord was created.
| refulgentis wrote:
| 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.
|
| https://books.google.com/ngrams/graph?content=database+shard...
| hooby wrote:
| "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 wrote:
| 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.
| layer8 wrote:
| Sharding is a specific type of partitioning, it's not a
| synonym.
| bigiain wrote:
| 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".
| Ozzie_osman wrote:
| 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.
| bigiain wrote:
| Thanks!
| mnahkies wrote:
| I generally think of partitioning being on a single host,
| and sharding being the same but across multiple machines
| layer8 wrote:
| > sharding and horizontal partitioning are essentially
| the same
|
| 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.
| Ozzie_osman wrote:
| 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".
| layer8 wrote:
| The keywords are "sharding" and "partitioning". (seriously)
| itisit wrote:
| Yes, the recency illusion. Often exacerbated by those thinking
| prior generations were stupid for not knowing things they
| couldn't rightly have known.
| stavros wrote:
| The article is about the origin of the name.
| CodeMage wrote:
| 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.
| IggleSniggle wrote:
| 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.
| dehrmann wrote:
| My first thought was that sharding is a natural step once you
| know about hash tables. Or a rolodex.
| da-holland wrote:
| 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.
|
| [0]: https://www.amazon.com/dp/1133776574
| other_herbert wrote:
| 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
| da-holland wrote:
| Absolutely!
|
| 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
| krispyfi wrote:
| Cubicles aren't enough. Developers need their own sound-
| proof offices.
| malkia wrote:
| heh, like the Malloc Geiger Counter -
| https://news.ycombinator.com/item?id=24303832
|
| Gamedev people came up with creative devices, like using pedal
| to debug-break into the game.
| CamperBob2 wrote:
| Real programmers just hold an AM radio next to the
| motherboard.
|
| At guru level, of course, you no longer need the radio.
| taberiand wrote:
| Of course, true gurus can smell use after free.
| bregma wrote:
| Of course, there's an emacs command to do that.
| runevault wrote:
| 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.
|
| Old gamedev books really have some wild stuff.
| samstave wrote:
| 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 is one of the golden eras of my gaming DNA.
| westurner wrote:
| Wikipedia has:
|
| 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
| distantsounds wrote:
| why 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 wrote:
| Do 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 wrote:
| Yup, I realize that the post could have originated from
| that section of the wikipedia article; or they are relying
| upon common sources.
| westurner wrote:
| None of this is incorrect. Why are people so disrespectful
| about others doing the work?
| WaitWaitWha wrote:
| 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.
| brandall10 wrote:
| 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
|
| https://en.wikipedia.org/wiki/Shard_(database_architecture)#...
| codethief wrote:
| 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.
| mindcrime wrote:
| Yes, that was this discussion:
|
| https://news.ycombinator.com/item?id=36848605
| renewiltord wrote:
| Actual paper did exist but no one has a copy anymore
| according to the contacted author. It was an internal
| Xerox memo.
| edent wrote:
| FWIW, I do now have a copy. I'm unsure of the copyright
| status so I'm a bit reluctant to share it.
| codethief wrote:
| Congratulations! How did you end up getting the copy?
|
| Also, maybe university libraries and/or Archive.org could
| help you with the copyright question?
| edent wrote:
| A commenter on my blog made contact with someone who had
| a copy.
| mindcrime wrote:
| > 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?
| BoiledCabbage wrote:
| 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.
|
| 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.
| brandall10 wrote:
| Great work. It's esp. interesting that this is an acronym.
| You should submit a correction.
| roberttod wrote:
| HN post here claims this paper may not exist
| https://news.ycombinator.com/item?id=36848605
| scott_s wrote:
| 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.
| crawfishphase wrote:
| 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.
| mindcrime wrote:
| Previously on HN:
|
| 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:
|
| https://news.ycombinator.com/item?id=36848605
| dang wrote:
| Thanks! Macroexpanded:
|
| _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!
| mysterydip wrote:
| 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?
| TMWNN wrote:
| It's definitely possible clientside; Refind Hacker News
| browser extension does it at the bottom of the page.
| ksec wrote:
| 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.
|
| [1] https://www.youtube.com/watch?v=lnnsDi7Sxq0
| hackermeows wrote:
| 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
| DaoShen wrote:
| 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".
| dools wrote:
| 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.
| tgtweak wrote:
| 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.
| lnxg33k1 wrote:
| 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
| crawfishphase wrote:
| 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)
| night862 wrote:
| 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.
| ratlrrr wrote:
| 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.
| hooby wrote:
| 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:
|
| https://starsreach.com/ (Fair warning: the graphics are still
| very early...)
| tunnuz wrote:
| 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.
| crawfishphase wrote:
| sometimes I dream I am in the game, and its pretty awesome to
| taste the food and smell the air
| Al-Khwarizmi wrote:
| 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 :)
| dools wrote:
| 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.
| jszymborski wrote:
| 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'm a huge fan.
| wdr1 wrote:
| 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.
| genter wrote:
| > Ticketmaster was founded in Phoenix, Arizona in 1976
|
| (Wikipedia)
| greentext wrote:
| Yes. A lot of tech history has its roots in gaming. And Trammel
| is for carebears.
| bigiain wrote:
| A 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 wrote:
| 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.
| oceanplexian wrote:
| 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.
| jerf wrote:
| 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.
| hintymad wrote:
| 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.
| benreesman wrote:
| I 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 wrote:
| If there are any anecdotes you can share I'd love to hear
| before they get lost to time.
| crawfishphase wrote:
| 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.
| ratlrrr wrote:
| The nostalgia is spilling to HN today!
|
| > I bet you can narrow down what city I was in from that but oh
| well.
|
| We used to run by or to each other's houses locally to round
| everyone up for play sessions, but this was commonplace with
| the introduction of LAN gatherings and the likes. :-D.
|
| > Btw did you know Time Bandits movie was a heavy influence on
| Ultima? And is Marvel's multiverse concept inspired by Ultima
| sharding also?
|
| Richard Garriott, a known D&D head, possibly grabbed or was
| exposed to something like crystal spheres[0] from Spelljammer
| (1989) or the Planescape (1994) campaign setting in all its
| glory, with the latter having its own computer game adaptation
| made by Chris Avellone.
|
| The computer games should always bear the guilt for some of the
| fondest memories.
|
| [0]
| https://spelljammer.fandom.com/wiki/List_of_Spelljammer_crys...
| BryantD wrote:
| 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.
| kagakuninja wrote:
| And it was probably heavily influenced by DC Comics alternate
| earths. Earth-2 was introduced in 1961.
| kagakuninja wrote:
| 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.
| kristianp wrote:
| Perhaps 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/
| gokaygurcan wrote:
| 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.
| Cthulhu_ wrote:
| That comes across as a bit rude tbh. Doesn't wine work? At this
| point they can probably make a web-based client too.
| endemic wrote:
| https://www.classicuo.eu/ ?
| crabbone wrote:
| 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.
| scott_s wrote:
| Potentially. I was also skeptical of this four years ago, and
| said as much on here
| (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):
|
| > 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.
| MichaelZuo wrote:
| 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.
| jjice wrote:
| 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.
| mrsilencedogood wrote:
| "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?)
| pjc50 wrote:
| 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.
| don_neufeld wrote:
| 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.
| astrobe_ wrote:
| 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 ?
| pjc50 wrote:
| 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.
| dhosek wrote:
| I loved the casual comment that Flickr came out of a failed MMO
| (worth noting that the same team had another failed MMO that
| ended up spawning Slack!)
| selectodude wrote:
| You gotta feel for a guy who just really wants to make an
| awesome MMO but keeps fucking up and making shit like Flickr
| and Slack.
| otterley wrote:
| Yeah, the poor fella is crying all the way to the bank.
| andirk wrote:
| And maybe the opposite where the do-everything dream app of
| Twitter will eventually become an MMO.
| throwup238 wrote:
| I think the Gamma Database Machine Project [1] demonstrated the
| technique in 1990, though it predates the word "shard."
|
| [1]
| https://pages.cs.wisc.edu/~dewitt/includes/paralleldb/ieee90...
| Suppafly wrote:
| 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.
| hi-v-rocknroll wrote:
| 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?
| sroussey wrote:
| I was doing db sharding in the 90s, not sure what the news of
| this was in 2009.
___________________________________________________________________
(page generated 2024-08-26 23:01 UTC)