Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What is the optimal way to update the subscriber's local model on changes C on a central model M? ( M + C -> M_c)

The update can be done by the following methods:

  1. Publish the updated model M_c to all subscribers. Drawback: if the model is big in contrast to the change it results in much more data to be communicated.

  2. Publish change C to all subscribes. The subscribers will then update their local model in the same way as the server does. Drawback: The client needs to know the business logic to update the model in the same way as the server. It must be assured that the subscribed model stays equal to the central model.

  3. Calculate the delta (or patch) of the change (M_c - M = D_c) and transfer the delta. Drawback: This requires that calculating and applying the delta (M + D_c = M_c) is an cheap/easy operation.

If a client newly subscribes it must be initialized. This involves sending the current model M. So method 1 is always required.

Think of playing chess as a concrete example: Subscribers send moves and want to see the latest chess board state. The server checks validity of the move and applies it to the chess board. The server can then send the updated chessboard (method 1) or just send the move (method 2) or send the delta (method 3): remove piece on field D4, put tower on field D8.

share|improve this question
    
What do you mean by optimal? Could be with respect to minimizing network traffic or computational complexity (either on the central host or the subscribers) or software qualities like reusability or maintainability? –  scarfridge Sep 23 '12 at 16:17
    
It sounds like you're thinking in 'math' terms. When you're talking about computer scale think bigger. I mean really really big. –  Evan Plaice May 22 '13 at 1:50
add comment

3 Answers

Your assumptions are a little off

Publish the updated model M_c to all subscribers. Drawback: if the model is big in contrast to the change it results in much more data to be communicated.

What you're describing here is essentially the pub-sub (ie publishers/subscribers) model. Even at scale, it's not very expensive to do because the data being returned is largely the same. Because it's essentially a one-way communication, the response will be essentially the same for all users. Fire-and-forget and create cache points in between if you need to scale larger.

Publish change C to all subscribes. The subscribers will then update their local model in the same way as the server does. Drawback: The client needs to know the business logic to update the model in the same way as the server. It must be assured that the subscribed model stays equal to the central model.

Now we have a problem. Every client maintains it's own state independent of the server. That means, every response needs to be specifically tailored to the request that's received. Ideally, you'll want to minimize the amount of state that's shared between the clients and the servers.

In games, they do this by only passing along the most basic state information. Even then it's usually done over a UDP connection so that packets that get dropped aren't re-requested. That's why, when games lag they'll usually continue to work but in strange and un-predictable ways. To the game, the simulation is still going on even if everybody else is frozen in time. In a lot of cases it'll even lag the player locally because their own actions need to be received and verified on the server before the action is taken locally.

Ever wonder why most fast paced games can't scale to hundreds/thousands of players. Here's your reason.

Calculate the delta (or patch) of the change (M_c - M = D_c) and transfer the delta. Drawback: This requires that calculating and applying the delta (M + D_c = M_c) is an cheap/easy operation.

Works good in theory but synchronization is a tricky business. For example, lets say 15 users are editing a document collaboratively. Edits are organized as transactions much like a database and updates are applied chronologically.

Edits can just be synchronized using time right? Wrong, because there's no guarantee that everybody's clock is in perfect sync. So the only option is to employ a central server to handle transaction management. It's somewhat optimal but when you throw in a hundred hosts that all require two-way communication with the central server, things may grind to a halt.


Hybrid-Models

There are a few cases of hybrid communications models that can push the limits by limiting or shifting accessibility to the central server.

Case 1: Infinite Lists

Lets take your first and second models and mix them into a new one. You want each user to maintain individual state but also want to decrease the load on the main server. Simple, organize the data in reverse-chronological order and only allow your users to access it in that order.

For example, in the original model lets say you have two users. One who is constantly updating to the latest and one who updates twice a year. The response to the person who constantly syncs is pretty small because their state is pretty consistent with the master data set. OTOH. the other user needs to update a massive amount of data after each request to maintain a consistent state with the server.

In the hybrid model, who cares if users have consistent state with the host. Just give them the most recent, if they want more give them the most recent after that, and so on. Worst case, everybody keeps requesting data until eventually their dataset is 100% consistent with the server. In the usual case, they'll only care about the most recent changes which means that the data being made available to the public is essentially a subset of the whole.

A smaller footprint means warm caches, quicker lookups, and lighter weight responses. This is the basic model that most news organizations and social media use today. You have a blog archive that stretches back to 1992, who cares... 99% of your users only want to read the stuff you've written in the past month. Reddit likes to hug 5 of your articles while the internet as a whole ignores the rest, then add frequency analysis to your cache expiration model. Warm caches mean faster lookups which is where your bottleneck will be if you manage to reach scales large enough to care about this sort of stuff.

Case 2: Peer-to-Peer Win

Lets say you actually want your data to be 100% consistent with the host and we're talking about a lot of data. Even if you manage to implement delta updates, if your local copy is far out of sync (or starting fresh) you'll still have a long ways to go.

The answer is simple. Divide and conquer. All you need to do is find a way to break up the data into logical chunks (ex split the data into 10MB chunks), create a map of the hashes of that data for quick/easy lookup/comparison.

OK, now you can request the data from the server in chunks but what if you wanted to go even faster. The answer is simple, separate the hashmap and the actual data into different pieces, de-centralize the host to make every connected node a host, and allow every node to download chunks from every other node.

It's very difficult to scale data transfers when you have a bunch of nodes pulling data from a central point but if everybody is fetching data from everybody, scalability becomes a non-issue.

Want to super-charge downloads. Simple. Request random chunks and for every time a chunk is requested but not available, it's priority increases. That ensures maximum diversity across hosts so there will be no bottleneck on any specific chunk of data.

Sound familiar? It should, what I described is the basis for the BitTorrent protocol. That's why 5 thousand people all downloading the same 2GB movie can still manage to do so at very data transfer rates. It's also why taking down one, or five, or 10 hosts still doesn't kill the swarm. All nodes in the swarm are constantly in communication with other nodes of the swarm but not necessarily every other node, just enough of them to keep the download going. Network communications don't get much more de-centralized or fault-tolerant than that.


As for your 'Chess' example. I know a lot of people like to romanticize about the compexity of chess by talking about the large number of possible combinations. In reality the number of variables involved is so small that the problem domain is practically insignificant.

You're talking about 64 possible spaces on a board and 32 possible pieces for each space. If you compress the pieces down into a bitmap where every piece represents a single bit. That means it takes 64 32-bit words or 256 bytes of data. To put the scale into perspective, there is more data contained in this sentence than there are possible combinations on a chess board.

Even if you make all of the clients 'dumb' (which isn't necessary considering the simple rule set) and isolate all business logic to a central server, the problem doesn't become any more difficult.

Here's the process flow for a 'dumb client' model:

  • Client sends move to host
  • Host updates global state
  • Host published new global state to players
  • Players update their board to match
  • Rinse & Repeat

As with most things in programming, if you choose an appropriate data structure the code will practically write itself.

Now, consider what it takes to represent than something like a first person shooter where 3-dimensional body positions and bullet trajectories are being calculated and propagated to multiple players in real-time. Ever wonder why you die a lot more when you're lagging? It's because those calculations need to take place on the host server to be accurately synchronized with the game time. A slow connection to the game host will always be a disadvantage, no matter how skilled a player is.

Aside: You could further compress the digital word format used to represent board pieces. By limiting it to only one bit for each piece type. 6 different types of pieces plus a sign bit to mark a piece as either black or white. That means a piece can be effectively represented by a 8-bit (ie rounded up, to the closest byte boundary) word. Which means the data being communicated literally takes up less space than the following ASCII art.

8 ║♜♞♝♛♚♝♞♜
7 ║♟♟♟♟♟♟♟♟
6 ║… … … … … … … …
5 ║… … … … … … … …
4 ║… … … … … … … …
3 ║… … ♘… … … … …
2 ║♙♙♙♙♙♙♙♙
1 ║♖… ♗♕♔♗♘♖
  ╚═══════════════
   a b c d e f g h

Source: http://recessiondodgetovictory.wordpress.com/2011/01/12/ascii-chessboard/

In fact, you could literally just use a 2-D array of UTF-8 chess characters to track the game state.

share|improve this answer
add comment

You've forgotten about conflict handling. Is there only one place where the model is changed? What if two subjects are trying to change the model at the same time? What if one of the subscribers did not get one message because of an error?

For method 2 and 3 you'll need some kind of versioning and resync mechaism in case of errors or missed messages. In method 1 you're just overwriting local model with incoming one.

What is more, when new client subsribes it has no model. It'll need to ask for a full model in approach 2 and 3. That will fore you to have two-way communication.

What I'am saying is that approach 2 and 3 are way more complicated than 1. On the other hand this is a common pattern: colaborative document editing, version control systems (I mean Git, SVN), multiplayer online games. Look for standard solutions of such problems.

share|improve this answer
add comment

Consider following scenarios: 1) client subscribes to changes and needs initial snapshot, 2) client subscribes to changes and does not need initial snapshot and 3) client needs only initial snapshot and not interested in changes.

For initial subscription, you can send a model snapshot (M) or its schema if snapshot is not required.

For updates, you need to calculate the delta to send to client. If the M is small, then D_c will be calculated easily. You could send the whole model to client, but what will happen when the model will grow? And you don't want to client to be aware of the business logic to send only C

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.