15 February 2012

Netgames 2004

Implementation of a service platform for online games, by Shaikh et al.

  • How to provision a cloud infrastructure hosting games
  • Each bot sleeps periodically to reduce CPU load and instantiate more bots. Bots connect to the game server according to a Poisson process with mean inter-arrival time of 1/λ=1s
  • TIO polls game servers at regular intervals for their CPU load using SNMP. Using the raw CPU leads to occasional over-provisioning and higher costs, but using a moving average to smooth the CPU estimate misses CPU peaks and may result in inefficient QoS for some players.
  • Since player load follows daily and weekly patterns, it's possible to anticipate the peaks; in that case, provision slightly ahead of the peak and keep a smoothed metric.
  • Relevant metrics other than CPU: "slack time" = unused time during an iteration of the server loop

Zoned federation of game servers: a peer-to-peer approach, by Iimura et al.

  • DHT implementation is Pastry. It uses SHA1 to map a game zone to its owner and runner.
  • Experimentation with 296 P3 1Ghz 512MB, all connected to a single 100Mbps switch. 295 machines run from 100 to 1,000 members, and a single machine runs the zone owner. Time taken to update the state of everybody is exponential with the number of zone members (average of 50ms for 500 members, 100ms for 700, 200ms for 1,000).
  • Spreading users uniformly on multiple zones, each with a single zone owner, reduces the load.

Scalable Peer-to-Peer Networked Virtual Environment, by Hu and Liao

  • Scalability implies that nodes can be added or removed on the fly while keeping the whole system functional. Ultimate P2P goal: adding a node should increase overall system resources without consuming centralized resources.
  • Cut the virtual space in Voronoi cells, where each user is at the center of his cell (deterministic algorithm). Each user connects with at least all his Vornoi neighbors (min 3, average 6, max n-1), and with more users if they are in his area of interest. Each time a user joins, moves, or leaves the game, his neighbors have to recompute their Voronoi diagram.

11 February 2012

Graphics cards on Ubuntu

Problem

My configuration: Lenovo T410, Ubuntu 11.10, Nvidia GT218.

OpenGL does not seem supported by default. Running nvidia-settings in a console says You do not appear to be using the NVIDIA X driver. Please edit your X configuration file (just run `nvidia-xconfig` as root), and restart the X server..

After following these steps, the environment does not show up anymore when rebooted - only a console-like frozen screen. An actual command-line console can be found using ctrl+alt+F1 to ctrl+alt+F6. Ctrl+alt+F7 goes back to the console-like frozen screen. The screen is frozen most likely because the x server did not start.

It turns out the actual problem is the hybrid graphic card configuration. Hybrid cards configurations for laptops have 2 cards: one for performance (e.g. Nvidia GT218), and one for battery life (usually integrated graphics, e.g. from Intel). The switching is supposed to be done automatically by Nvidia's Optimus software. But Ubuntu 11.10 does not support, by default, the switching between integrated graphics and Nvidia graphics.

Quick fix: to discard permanently the integrated graphics, in the BiOS (F1 at computer startup), pick Config > Graphics > Discrete. Problem: heavier battery consumption, and Windows, which is has no problem using Optimus, will now be forced to use only Nvidia. Not good.

Fixing the problem: Bumblebee

Bumblebee is a solution for Optimus on Ubuntu, and they have a tutorial to set it up. But in case it one day disappears, here are the steps.

1) Check hybrid config and support

Determine graphics card(s): lspci | grep VGA

00:02.0 VGA compatible controller: Intel Corporation Core Processor Integrated Graphics Controller (rev 02)
01:00.0 VGA compatible controller: nVidia Corporation GT218 [NVS 3100M] (rev ff)

So there's an Intel integrated card and an Nvidia GT218 card: that's a hybrid configuration. Check Nouveau's supported cards to see if the opensource driver supports your card. If it does not, maybe the proprietary Nvidia driver supports it?
Anyway, the next step is to check that the Nvidia card is not doing its part; run glxspheres. This outputs:

Polygons in scene: 62464
Visual ID of window: 0x97
Context is Direct
OpenGL Renderer: Mesa DRI Intel(R) Ironlake Mobile
21.494593 frames/sec - 23.987966 Mpixels/sec

21 frames/sec is quite lame, so Nvidia is most likely not picked.

2) Installing Bumblebee 3.0 (as of February 2012)

sudo add-apt-repository ppa:bumblebee/stable
sudo apt-get update
sudo apt-get install bumblebee bumblebee-nvidia
sudo usermod -a -G bumblebee $USER
sudo reboot

3) Testing

Any program to be run with the Nvidia card should be prefixed by optirun; for instance, optirun glxspheres outputs:

Polygons in scene: 62464
Visual ID of window: 0x21
Context is Direct
OpenGL Renderer: NVS 3100M/PCI/SSE2
101.341234 frames/sec - 113.096817 Mpixels/sec

Although it takes a tiny bit of delay for the program to start, it's much better than the 21 fps of earlier. Running optirun -c yuv glxspheres shows even better performance (145 FPS). But the CPU consumption remains high: Bumblebee only has the Nvidia card compute 60 frames per sec and send those frames to the Intel card anyway.

References

07 February 2012

Influence - Cialdini, 1993

Weapons of influence

Fixed-action patterns: the response behavior always happens in the same way. We're interested in the trigger of that response. Most of the time, the trigger is valid, but sometimes it's misleading. This response is triggered because the load of information in our society is too big for our lazy brains, and we need shortcuts.

Give a reason/explanation when asking a favor; it increases its chances of being accepted. "Let me pass you because I'm in a hurry."

Expensive = good. Make the customer think "it's a bargain!". Pretend to discount an item from $100 to $50 while the actual price really is $40.

Contrast principle: When buying a $30k car, a $1k radio does not seem like much. Show a $500 suit first, then a $50 shirt to make the shirt look cheap. Also works the other way: clients won't buy if you first show the cheap item and then the expensive item.

Reciprocation

Reciprocity rule: We feel obliged to return favors because society looks down on ingrates. You can increase compliance by providing ... a small favor prior to a request. Benefactor-before-beggar strategy.

Why it works: The reciprocity rule promotes the initiation of trade without fear of loss. It is too socially beneficial for us to want to violate it. It's also hard to reject gifts, even unwanted ones. Since society looks down on ingrates, feeling obliged is disagreeable, and that makes us ready to give a lot to get out of such a disagreeable situation. Examples: political favors, "you don't bite the hand that feeds you".

Concessions: the basis of trade and negotiations. Example: Boy scout in the street sells expensive lottery tickets for $10 apiece. When we tell him no, he asks "what about a $1 lemonade then?". We're likely to say yes because we think he did a concession to us. Add the effect of the contrast principle: $1 is nothing compared to $10.

Commitment and consistency

Once we make a choice (e.g. bet on a horse, or pick one of two lovers), we stubbornly stick to it and back it up ("despite all his flaws, he has lots of qualities").

Why it works: Lazy brains use consistency so that they don't have to re-evaluate a decision all the time. We are under pressure to bring our self-image into line with our past actions. Hence, any request that goes in that direction will be accepted. Example: Phone call and ask people how they're doing. They answer "Great!". They just made a commitment. Continue with "Glad to hear it, because I'm calling in support of a charity for Orphans in Hospitals during Christmas ...".

Foot-in-the-door strategy: sell an undervalued item to transform prospects into customers. When they realize that they are customers of yours, they will come back to buy any item, even overpriced ones, by self-commitment.

Active, public, and effortful commitment is the most effective at changing the self-image. We accept responsibility for a behavior when we think we've chosen to perform it in the absence of strong outside pressures (ie rewards or threats did not justify the participation, yet you participated). Examples: Customers who write the sales contract down themselves are less likely to cancel orders or ask for refunds. Undergrads who choose to endure a fraternity hazing convince themselves it was worth it.

Low-balling: Promise people a reward (e.g. money or fame) if they do something repeatedly (e.g. save energy, take out the trash), and cancel that reward after a while. They are likely to keep doing it because in the meantime, they have built other reasons to support their new image (e.g. "I am the kind of person who saves the planet or helps someone").

Social proof

We find correct what people similar to us find correct (social evidence). Example: canned laughter in TV shows to signal that it's funny, or herd behavior.

Pluralistic ignorance: Lots of people, none of them knowing what's going on, are all looking at each other for clues of what to do. Since they can't find any, nobody does anything because everyone wants to stay poised in public. Even more efficient when people are in unfamiliar contexts (e.g. abroad or in fancy receptions).

Liking

Tupperware parties and obligation of friendship: people twice more likely to buy because from a friend than because the item is useful. Door-to-door marketing: simply mentioning "your friend X recommended you to us" is enough: turning the sales person away ... is almost like rejecting the friend.

We like and are more likely to favor good-looking people and people similar to us. We generally believe compliments and those who give them.

Cooperation: when cooperation is required to achieve common goals, and each party has a part of the solution, it can turn enemies into collaborators, and then friends. For example, Bad Cop puts pressure on the interviewee, so that Good Cop looks like he's cooperating with the interviewee, and makes him comply with his requests.

Association: we hate people who bring bad news, and we tend to prefer products who are advertised by good-looking people. The association does not have to be logical, just positive. See also Pavlov's dog. Similarly, when our national team the soccer world cup, we feel associated with their success: "we won!". But when the team loses, "they lost!". We are particularly eager to bask in reflected glory when our image has been recently diminished.

Authority

Milgram experiment and its addition: instead of a single authority figure asking to give shocks, have two authority figures giving conflicting orders (shock vs don't shock). The subject tries to see who is the boss of who.

Clothes and titles: an actor disguised as a doctor in a TV ad gives more credibility to the medicine. Security guard uniform doubles the rate of people who give a dime to another person for parking. When jaywalker in business suit, people are more likely to mimic him.

Important things and people are seen as taller. Yet the more a category of people is concerned by a mark of authority (e.g. students by teachers, or males by cars), the more that category underestimates the authority's impact on them.

Scarcity

We are more motivated by not loosing something, than by gaining something of equal value.

Reactance: as we're losing opportunities, we feel like we're losing freedoms. Since we hate losing freedoms, especially those most recently acquired, we'll fight to keep them. We'll also give those freedoms more importance or qualities than before. Example: 2-year-old kids discover they have a body of their own (a form of freedom newly acquired). They'll say no to everything to check their new boundaries. Same with teens realizing they can be independent of their parents: they fight parental authority.

Scarcity works on objects: ban phosphate use and people start finding it more useful. It also works on persons: cf the Romeo and Juliet effect: because their parents forbid it, their love is bigger. It also works on information: tell supermarkets that beef is scarce and that it's rare to know that beef is scarce increases sales by 6x. It also works on rights and ideas: forbid a book to minors and 1) they want to read it more, and 2) more of them think they're going to like it.

Temporal scarcity: examples include "available only this week" or pausing a face-to-face conversation to take a phone call because "he may not call again!". Being put in competition with other people (e.g. auctions) is even more efficient.

Scarcity creates a desire that has little to do with the merit of the commodity. The joy is not in experiencing a scarce commodity, but in possessing it.

03 February 2012

Scaling League of Legends

Notes from a 2011 Qcon talk about scaling the non-gaming server side of League of Legends. They are not worried about persistence during a game, but rather in the match-making, lobby, or store. They have soft real-time requirements: not the order of 10ms, more the order of a few seconds. [Twitter and Facebook are soft RT too]

Scaling

Scalability: it's easier to constrain what the logic developers are allowed to do, than to define what they are not allowed to do. Examples: Map/Reduce is a whole paradigm (you have to make your logic fit into a map() and a reduce()), NoSQL's unstructured data is a double-edge sword (you lose the ability to join, but queries come back faster), and when you're partitioned, you pick to be either atomic/consistent or available

46:50: Scaling should be dynamic/elastic; you need cluster recomposition and stateless growth patterns. Hence the system should be dynamically configurable. On the fly, you should be able to adjust the thread pool size, add/remove roles to machines, and switch logic or system algorithms.

Food for thought: list all the benefits/tricks a load balancer can provide to your system.

Caching

Caching provides flexibility: failovers, distribution of workload (hot code updates or restarts). Coherence is a distributed cache used between Hibernate and the DAO layer as "cache-through". If the DAO asks Coherence and there's a cache miss, then Coherence asks Hibernate (itself using a Coherence cache, or calling MySQL over the network if cache miss).

24:00: How to be sure that cache and DB are consistent? Do not cache! Query the DB directly, latency of few sec is OK for soft RT.

11:30: Serialize the work, not the data. It's faster to serialize the work to the data, than to unserialize the data, work on it, then serialize the result. Avoid moving the data all over the network towards where the process is. It's also easier to distribute the work to all the DB nodes than to send to/receive from all the nodes.
The objects sent on network between server and DB should be small: if you have to edit only one field, you should not have to send a big object of 1MB.

Logging and Testing

42:30: They log each function call with how long it took; overhead of 1% performance, but huge value if able to graph/plot the logs. Compare the average call duration in the last few minutes to the usual average to detect problems.

17:15: Keep in mind that the code will be used/executed in a data center, not on your laptop. 51:25: They use EC2 for load testing. 1000 threads per node, each thread simulating 1 user. Realistic because not all clients (threads) are same speed in real-life, and EC2 network is not always the best/reliable. It's not the most performant, but it looks like a quick-and-dirty way to load test. One of their scale testing environment has more than 50 machines.