Comments

Hello everybody, my name is CCP Prism X and I am a Libra!

This summer we saw a welcome influx of players with the release of EVE Online: Odyssey. On occasions as such we usually celebrate our great success by pulling out the champagne and our $1000 Japanese pants, and having ourselves a great big pillow fight. However, this time around the influx of people was so dramatic that it worried us; Empire Space was burning. There were so many people in New Eden, doing so many things, that the actual CPU cores (reffered to as "nodes" hereafter) running the Empire Space systems were under extreme load. This was causing Time Dilation to affect the various, and disparate, portions of Empire Space. Time Dilation is all well and good when you‘re blobbing with your space-friends in Nullsec. But when you‘re just running a mission in some dead-end system, all alone in local, and suddenly everything starts going all bullet-time on you: you get frustrated.

Empire Space should really have such predictable load that Time Dilation should never kick in there. If it happens, our Static Cluster Premapper should at least be able to avoid a reoccurence. That is because we track an estimated load fingerprint of all solar systems and assign systems to different nodes, based on said estimated load, during startup. As long as that estimate is correct-ish and the premapper is functioning as it should, things should run fairly smoothly. But the same systems were consistently starting up on nodes with too many other systems assigned to them. Things were not running very smoothly at all and we weren‘t quite sure why.

† Assuming that no social engineering takes place that diverts load to new, unexpected, places.
Example: Announcing an upcoming LP offer from a corporation that only has a single good agent in high-security space will result in a lot of new load in that agents system which the premapper cannot in any way anticipate.

Step 1: Identify the problem

Above I omitted a fairly important fact about this premapping of solar systems: systems within the same constellation want to stay on the same node. They want it so bad that they‘ll do so at the expense of balanced load distribution as they‘ll ignore the, load wise, most optimal node assignment if their preferred node is only 20% more loaded than the optimal one. This behavior causes a huge deviation between the load of different nodes whereas we‘d rather want the premapper to spread the load as evenly as possible over all the nodes available to it. Furthermore this behavior doesn‘t extend above the constellation level so effectively a node can run two whole constellations, but one is located in the Deep North and the other in the Deep South. So a fleet fight in the Deep  South could enforce Time Dilation on the other constellation located in the Deep North. That‘s frustrating for the Deep North pilots!

Here is visualization of the clustering of systems to nodes in the old systems (Note, this is 3D data badly projected on a 2D plane so there‘s some skew). Systems of the same colour reside on the same nodes. You‘ll quickly notice that this is just a jumble of colours with little consistency. I‘ve drawn red circles around two clusters which all belong to the same node to show the distance between the two:

 

And to top it off this isn‘t even a good load distribution. The difference between node load is fairly staggering as you can see on the standard deviation values here:

But why were  we clustering systems on the constellation level? Because a long time ago it was theorized that inter-node stargate jumps were more expensive than intra-node jumps. Presumably, that is due to the assumed overhead introduced by network latency. Now we know that this assumption is completely wrong and inter-node jumps are actually cheaper than their counterpart. A stargate jump requires the removal of the player from one system, and his introduction into another one. Splitting that work between two nodes spreads load better than doing it all on the same node.

Realizing this, we just decided to remove any such node affinity behavior from the premapping logic as a first step. Systems would just be assigned to nodes on the basis of the most loaded, unassigned, system being assigned to the least loaded node. That resulted in an amazingly well balanced cluster and the load problem was solved! But even though we‘d made a very balanced cluster the Time Dilation problem was now even more pronounced. Systems had just been semi-randomly assigned to nodes with no respect to locality and so we still had people in the Deep North affected by fleet fights in the Deep South. Revert the changes and put the thinking cap back on!

Step 2: Solve the problem

So we needed a way to split load between nodes whilst ensuring that all systems on a node belong to the same space-neighborhood. As a secondary concern we really did not want to increase the time premapping took, and we used the opportunity to completely nuke the old T-SQL code and recreate it as a Python module. That last decision, unsurprisingly, turned out to be the most important one as a procedural language with a large supporting ecosystem of available tools is much better geared to solve a procedural problem than a highly limited relational language.

With Python at our side we initially arrived at a fairly simple and approachable solution. As we‘re attempting to split up a cluster of stars with defined coordinates so that both halves are adjacent and equally weighted; why don‘t we just do that? If you split any coordinate system in half with a plane, both halves will be adjacent to each other and that solves the problem of proximity. That leaves us with a way of ensuring that both halves are close to equal in their load. As we keep track of each systems load this just becomes a matter of tweaking the split line iteratively in some sensible manner. That‘s not more complex than using the properties of Binary Search! We just have to move the split line a given distance towards the more heavy of the two halves, and then half the distance we‘ll move it on the next iteration. Theoretically we should bounce between both sides of the optimal split line for a while until we hit it. I say theoretically because we‘re not trying to find the optimal solution here, only a good enough solution in the least amount of time.

Here is a graph to help you visualize this process. Imagine the circle stands for the entire cluster of stars we want to split up. The stars themselves are not shown because they're not important, all that matters is that the split will not mix stars from the two distinct halves between them and that the load is as equal as possible.

Once we’re done splitting the initial universe into two clusters, we’ll pick the heavier of those two and split it again. Then we’ll pick the heaviest of those three and split it again and repeat the process on the four resulting clusters of stars. We’ll repeat this until we have as many clusters as we have nodes at which point we commit the mapping to the database and continue on with startup.

To visualize this properly I’ve provided some visualization, using this method, run against the same dataset as the graph above. However, the first three steps are the split of Empire Space only due to the inner workings of the new method and only serve to describe the method better. The last picture is the final allocation of the entire universe (on the same data) and can thus be compared to the similar graph above.

Initial Empire Space step:

 

First Empire Space split. Note the size difference of the two halves due to the fact that not all systems are equally loaded:

 

Seventh Empire Space split (that grey blob is two hues of gray):

 

End result of entire universe. Note how much more uniform the color distribution is:

Step 3: Actually Solve the Problem

That’s how we initially pushed out the new cluster premapper a few weeks before Rubicon was released. We did so understanding what the more Computer Sciency types out there might already have realized from the above; this results in a balanced load spread if, and only if, the number of nodes available for allocation are a whole power of two. Anything else will result in a fairly unbalanced load spread as we’re always splitting load into two halves, creating a sort of a Binary Tree. For a perfectly equal split we must have enough nodes to fill the leaf level of that imaginary tree or we’ll have nodes on level leaf-1 with double the amount of load on the nodes on the leaf level.

Here is a very simple picture displaying the whole power of two issue with 3 nodes as opposed to 2^2=4 nodes. Please keep in mind that this is a perfect world example. We do not actually expect all load splits to be perfectly equal.

This resulted in a too uneven of a split. The statistics below do look better for Nullsec but in Empire we’re still looking at a fairly large standard deviation between nodes. But at least the CPU Minimum isn’t zero here. Sadly the memory stats just got plain worse, but we’re really balancing primarily for CPU.

Obviously the optimal split here is 33% of the load allocated to each node but you can see how the nice and simple algorithm outlined above completely fails here. But since we know this works optimally if we divide the load by a number of nodes that is a whole level of two we just need to force that behavior! We could of course constrain ourselves to always have a whole power of two number of nodes for solar systems but that feels like a rather silly artificial constraint. Especially if you know that any number in base 10 (decimal number system) can be represented in base 2 (binary number system), then this just becomes a matter of rearranging the binary tree above into branches of whole number of two nodes and running the algorithm detailed above on those branches.

Using a bit more complex example than the three nodes above, we can visualize this in action as thus:

This is easy enough to achieve with minimal alterations to the code used in the initial solution. That solution already relies on a method of splitting coordinate systems in two equally loaded parts. Altering it to split it into two X/Y parts is no big deal.

Using this new approach on the exact same dataset as the examples above we end up with this pretty picture of a balanced universe within which space-friends shoot other space-friends in their respective faces:

 

And now the CPU standard deviation has dropped drastically! We're hoping to have this code out by tomorrow Wednesday, December 4th.

Step 4: Write a Dev Blog

Then do it again. This is the second version of this Dev Blog. I’m pretty sure nobody would have enjoyed reading the first one. Sadly I couldn’t reuse a lot of stuff from that first attempt, like I could with the code. It simply had too many mentions of water carriers, aqueducts and Beyonce Knowles. Probably wouldn’t have made a lot of sense to anybody!

So there you have it; our recipe for a Balanced Universe. Perhaps you can find some way of applying it to your own lives! I’m thinking those fancy colored dot charts could probably substitute for a Rorschach test. But in case you just read through my entire blog and do not feel like you’ve gained much from it I’d like to present you with this cool island song as a peace offering (Don’t browse at work kids!).

That’s it folks! If you’ve got some further questions I’ll be looking at the comment thread regularly.

145 Comments

  1. What blog sites for political discourse would certainly you advise me to review?

    September 10, 2019 at 08:54 Reply
  2. Thanks again for the blog post.Much thanks again.

    September 10, 2019 at 17:03 Reply
  3. Great ¡V I should definitely pronounce, impressed with your site. I had no trouble navigating through all the tabs as well as related information ended up being truly easy to do to access. I recently found what I hoped for before you know it in the least. Reasonably unusual. Is likely to appreciate it for those who add forums or anything, web site theme . a tones way for your client to communicate. Excellent task..

    September 10, 2019 at 18:44 Reply
  4. Heya i am for the first time here. I came across this board and I find It really useful & it helped me out much. I hope to give something back and aid others like you helped me.

    September 10, 2019 at 18:44 Reply
  5. Thanks for every other informative site. Where else may just I get that kind of info written in such a perfect means? I’ve a venture that I am simply now working on, and I have been on the glance out for such info.

    September 10, 2019 at 18:44 Reply
  6. You could definitely see your skills within the paintings you write. The arena hopes for more passionate writers like you who aren’t afraid to say how they believe. All the time follow your heart.

    September 10, 2019 at 18:45 Reply
  7. Hey, I think your site might be having browser
    compatibility issues. When I look at your blog in Chrome, it looks fine but when opening in Internet Explorer, it has
    some overlapping. I just wanted to give you a quick heads up!
    Other then that, awesome blog!

    September 10, 2019 at 19:12 Reply
  8. I’m impressedamazed, I must sayI have to admit. RarelySeldom do I encountercome across a blog that’s bothequallyboth equally educative and entertainingengaginginterestingamusing, and let me tell youwithout a doubt, you haveyou’ve hit the nail on the head. The issue isThe problem is something thatsomething whichsomethingan issue that not enoughtoo few people arefolks aremen and women are speaking intelligently about. I amI’mNow i’m very happy that II stumbled acrossfoundcame across this in myduring my search forhunt for something relating to thisconcerning thisregarding this.

    September 10, 2019 at 21:11 Reply
  9. Thank youThanks for any otheranothersome otherevery other greatwonderfulfantasticmagnificentexcellent articlepost. WhereThe place else may justmaycould anyoneanybody get that kind oftype of informationinfo in such a perfectan ideal waymethodmeansapproachmanner of writing? I haveI’ve a presentation nextsubsequent week, and I amI’m at theon the look forsearch for such informationinfo.

    September 11, 2019 at 07:39 Reply
  10. What hosting websites will allow my blog site to make money off includes being placed on my blog?

    September 11, 2019 at 08:42 Reply
  11. Hello.This article was extremely fascinating, especially because I was searching for thoughts on this topic last week.

    September 11, 2019 at 15:23 Reply
  12. You made some clear points there. I looked on the internet for the topic and found most persons will consent with your site.

    September 11, 2019 at 15:30 Reply
  13. Very neat blog article.Much thanks again.

    September 11, 2019 at 18:25 Reply
  14. I’m amazed, I must say. Rarely do I come across a blog that’s equally educative and amusing, and let me tell you,
    you’ve hit the nail on the head. The issue is something which not enough men and women are speaking intelligently about.
    I’m very happy that I came across this in my search for something concerning this.

    September 11, 2019 at 20:48 Reply
  15. I think this is one of the most vital information for me.

    And i am glad reading your article. But should
    remark on few general things, The site style is great, the articles is really excellent : D.
    Good job, cheers

    September 12, 2019 at 02:00 Reply
  16. I have three blogs on tumblr under the exact same e-mail address. How do I remove one of those blog sites without erasing the other 2?. Ideally, I ‘d like somebody to address whom has experienced this trouble prior to and fixed it without deleting their other blog sites. Many thanks!.

    September 12, 2019 at 02:25 Reply
  17. When someone writes an articlepostpiece of writingparagraph he/she keepsmaintainsretains the ideathoughtplanimage of a user in his/her mindbrain that how a user can understandknowbe aware of it. SoThusTherefore that’s why this articlepostpiece of writingparagraph is amazinggreatperfectoutstdanding. Thanks!

    September 12, 2019 at 07:15 Reply
  18. Oh my goodness! a wonderful write-up dude. Thank you However I will be experiencing trouble with ur rss . Do not know why Cannot subscribe to it. Can there be everyone acquiring identical rss problem? Anybody who knows kindly respond. Thnkx

    September 12, 2019 at 15:09 Reply
  19. This articlepostpiece of writingparagraph will helpassist the internet userspeopleviewersvisitors for creatingbuilding upsetting up new blogweblogwebpagewebsiteweb site or even a blogweblog from start to end.

    September 12, 2019 at 15:27 Reply
  20. Nice weblog right here! Also your website so much up very fast! What web host are you the usage of? Can I am getting your affiliate hyperlink to your host? I want my site loaded up as quickly as yours lol

    September 13, 2019 at 06:27 Reply
  21. Of course, what a great website and educative posts, I will bookmark your website.Best Regards!

    September 13, 2019 at 06:27 Reply
  22. I truly appreciate this post. I¡¦ve been looking everywhere for this! Thank goodness I found it on Bing. You’ve made my day! Thank you again

    September 13, 2019 at 06:27 Reply
  23. HighlyVery energeticdescriptive blogarticlepost, I enjoyedlikedloved that a lotbit. Will there be a part 2?

    September 14, 2019 at 07:23 Reply
  24. I carry on listening to the newscast lecture about getting boundless online grant applications so I have been looking around for the most excellent site to get one. Could you tell me please, where could i acquire some?

    September 14, 2019 at 14:37 Reply
  25. I have to voice my gratitude for your generosity supporting people who absolutely need help with this particular study. Your very own commitment to getting the solution all through turned out to be extraordinarily useful and has in most cases enabled guys and women just like me to realize their ambitions. The warm and helpful information signifies a lot a person like me and further more to my mates. Best wishes; from each one of us.

    September 14, 2019 at 14:54 Reply
  26. Hello, i think that i saw you visited my website so i came to “return the favor”.I’m attempting to find things to improve my website!I suppose its ok to use some of your ideas!!

    September 14, 2019 at 14:54 Reply
  27. I don’t even know how I ended up here, but I thought this post was great. I don’t know who you are but certainly you’re going to a famous blogger if you aren’t already 😉 Cheers!

    September 14, 2019 at 14:55 Reply
  28. Very well written post. It will be beneficial to anyone who utilizes it, as well as yours truly :). Keep doing what you are doing – i will definitely read more posts.

    September 14, 2019 at 14:55 Reply
  29. I have 3 blog sites on tumblr under the exact same email address. Exactly how do I erase one of those blogs without removing the various other 2?. Ideally, I would certainly such as somebody to answer whom has encountered this problem prior to as well as resolved it without deleting their various other blog sites. Thanks!.

    September 15, 2019 at 02:37 Reply
  30. I’m aiming to find out as much regarding the on the internet searching neighborhood as I can. Can any person advise their preferred blogs, twitter manages, or websites that you find most thorough? Which ones are most preferred? Thanks!.

    September 15, 2019 at 04:19 Reply
  31. I appreciate you sharing this blog.Really thank you! Will read on…

    September 15, 2019 at 04:57 Reply
  32. Definitely believe that which you stated. Your favorite reason appeared to be on the net the easiest thing to be aware of. I say to you, I certainly get irked while people think about worries that they just don’t know about. You managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people can take a signal. Will probably be back to get more. Thanks

    September 16, 2019 at 14:03 Reply
  33. What i do not understood is actually how you’re now not really much more neatly-appreciated than you may be right now. You are very intelligent. You already know thus considerably in the case of this subject, made me in my opinion imagine it from a lot of varied angles. Its like men and women aren’t interested until it¡¦s one thing to do with Girl gaga! Your individual stuffs outstanding. All the time maintain it up!

    September 16, 2019 at 14:03 Reply
  34. I was suggested this web site by my cousin. I’m not sure whether this post is written by him as nobody else know such detailed about my trouble. You are amazing! Thanks!

    September 16, 2019 at 14:03 Reply
  35. Whats Going down i’m new to this, I stumbled upon this I have found It absolutely useful and it has aided me out loads. I’m hoping to contribute & help different customers like its aided me. Good job.

    September 16, 2019 at 15:11 Reply
  36. I like the valuablehelpful informationinfo you provide in your articles. I willI’ll bookmark your weblogblog and check again here frequentlyregularly. I amI’m quite certainsure I willI’ll learn lots ofmanya lot ofplenty ofmany new stuff right here! Good luckBest of luck for the next!

    September 17, 2019 at 06:29 Reply
  37. As a Newbie, I am always searching online for articles that can aid me. Thank you

    September 17, 2019 at 20:45 Reply
  38. As I web-site possessor I believe the content matter here is rattling magnificent , appreciate it for your hard work. You should keep it up forever! Best of luck.

    September 17, 2019 at 20:45 Reply
  39. Keep working ,great job!

    September 17, 2019 at 20:45 Reply
  40. After study some of the blog articles in your web site now, and I truly appreciate your way of blogging. I bookmarked it to my bookmark website list and will also be checking back soon. Pls consider my web site too and tell me what you believe.

    September 18, 2019 at 01:25 Reply
  41. Thank you for the good writeup. It in fact was a amusement account it. Look advanced to more added agreeable from you! However, how can we communicate?

    September 18, 2019 at 07:11 Reply
  42. You are a very intelligent person!

    September 18, 2019 at 07:11 Reply
  43. Just wish to say your article is as surprising. The clarity in your post is just excellent and i can assume you’re an expert on this subject. Well with your permission allow me to grab your RSS feed to keep updated with forthcoming post. Thanks a million and please continue the enjoyable work.

    September 18, 2019 at 07:32 Reply
  44. NiceGoodFastidious repliesrespondanswersanswer backresponse in return of this questionquerydifficultyissuematter with solidfirmrealgenuine arguments and describingexplainingtelling everythingallthe whole thing regardingconcerningabouton the topic of that.

    September 19, 2019 at 06:42 Reply
  45. you’re truly a just right webmaster. The site loading pace is incredible. It seems that you’re doing any unique trick. Also, The contents are masterpiece. you have performed a fantastic activity in this topic!

    September 19, 2019 at 16:42 Reply

Leave a Reply to Bathroom Renovations Click here to cancel reply.