4 ms·

Retric said if I provide data that's accurate +/- .2 seconds that's close enough, but he's wrong (sorry Retric, it's not your fault). The fact is, I must provi

by owkaye 18y ago

Retric said if I provide data that's accurate +/- .2 seconds that's close enough, but he's wrong (sorry Retric, it's not your fault). The fact is, I must provide each member with the relative position of his post each time he makes one, and the only way I know to do this is to append the new record first, and then do a search and sort to determine where his new post appears in the sorted list. Retric, you said I'm not going to be able to sort things that fast for every new post. Do you know this to be true? Is this an absolute fact or are you theorizing? I'm not suggesting that you wrong when you say this, but I certainly do not want to assume you're right just because you say so -- because unless there's another way to determine the position of the new post in a sorted list I may have no other choice but to abandon the existing approach, re-work the entire business plan, and try something else from a completely different angle. I prefer to NOT do this when the current concept is the best I've come up with. What abut other people's experiences? Do any of you know about data systems that can do an append, followed by a search and sort on one field, at the rate of 16,000 times a second? Or is there another way to determine the position of a record in a sorted list without sorting the db to rceate that sorted list? How about if the database is kept entirely in RAM? I know this will speed things up a lot, but will sorts be fast enough for 16,000 a second without bogigng down? mseebach, you asked "What exactly is the output?" and I'm not sure if your question was directed to me but if it was, and if you're asking about the data that needs to be sent from the server back to the browser, then I think I might need to send only "one character" back to the Javascript. Previously I was going to send an entire HTML page but it seems the Javascript solution could be orders of magnitude more efficient. By using the Javascript approach I can send only 10 chars to the server and receive only one char back from the server. The Javascript can then convert that one char to the proper "relative position" value for display in the browser -- or so I hope. bd, you said I might do better to build my own custom in-memory data structure rather than use a classical ready-made database solution. Maybe you're right. It would certainly reduce the costs over a super-expensive high-speed database solution, wouldn't it? I've never done such a thing before but maybe I can find someone who has. Any suggestions? bd, you also said I do not want to sort the whole dataset after each new piece of data comes in, and you're right about that too. What I really need is to insert each piece of data in the proper pre-sorted position as it comes in. Then I never have to sort the data later because it's being sorted before or as it enters the db. spinonethird, you said that from my description I'm not really using the db and maybe I can roll my own specialized data structure. You and bd seem to think alike, and with two of you in consensus I'm becoming more attracted to this idea, especially if it has the potential for faster performance than an off-the-shelf database program. AS far as the business details are concerned, I know some people (gsiener, rbanffy and perhaps others) are curious but I'm not at liberty to discuss the details at this time. When I eventually spill the beans it will probably be after the business launches so we can gain traction and market share before the competition invades our turf ... :) One question before I end this post: Is C the fastest language or the best language to "roll your own" databse solution, or are other languages just as good or better? I'm not up-to-date on the advantages of many programming languages so your thoughts and opinions on this issue might help me to pick the best language for a project like this. Thanks.

owkaye 18y ago
In my last long post I said Retric was wrong about providing data that's accurate only to +/- .2 seconds, but maybe I'm the one who is wrong. It is possible that I completely misinterpreted his meaning. I became aware of this possibility when I read lacker's post that said I can probably batch up data since I'm going to have latency issues anyways. He's right, I never thought of it this way. The issue I'm imagining with batching is that I cannot send any data back to visitors until the next batch is processed -- because if I do they won't see how their last post has changed their positions in the hierarchy, and they will interpret this as a system error. In other words, every time a member receives a response from the server, that response must indicate his last post's position in the hierarchy. Theoretically I could run a batch every second, and although this means holding up all the responses to requests that come in during the previous second, one second is also short enough that they will not interpret it as a problem with the system. On the other hand, 5 seconds in between batches would certainly be seen as a server problem especially by folks on high speed connections.
- mseebach 18y ago
  So you problem is not processing 1.000.000 requests pr. minutes, but rather how to sort up to 60.000.000 items 1.000.000 times pr. minute? Now that could prove to be quite problematic. If your sorting algorithm only requires one processing instruction pr. stored item, and is perfectly parallelizable, and there's zero overhead in the map-reduce, you'll need 300 3 ghz cores to do it.
  - lallysingh 18y ago
    Hmm, nlogn(60,000,000) ~= 1,560,000,000 ops per sort, before your coefficient. If you want that done at 16.67 KHz (1 million times/min), you'll need some work. You can do it, in certain cases, with certain hardware & good skills, but it's tricky. I'm still not buying that the requirements are really that high.
- anamax 18y ago
  > The issue I'm imagining with batching is that I cannot send any data back to visitors until the next batch is processed -- because if I do they won't see how their last post has changed their positions in the hierarchy, and they will interpret this as a system error. In other words, every time a member receives a response from the server, that response must indicate his last post's position in the hierarchy. You're making this much harder than it has to be because you're assuming that users can see things that they can't. Suppose that the system had two users, A and B, and they each issued two commands, A1 and A2 in that order from A and B1 and B2 from B. Suppose further that system responds to each command with something that it says is the global state. To keep things simple, I'll use the command, such as A2, to refer to the response as well. (In other words, A2 is the response that A gets to command A2.) A knows that she issued A1 and A2 in that order, so the A2 response must reflect commands A1 and A2. However, the A2 response need not reflect B1 or B2 unless A has some way to know that B issued them before A2, regardless of when B1 and B2 were issued in relation to A2. In fact, it's probably okay for the A2 response to reflect command B2 and not command B1. Now let's throw C into the mix, issuing C1 and C2 in that order. As with B, the A2 response need not reflect C1 or C2 even if they actually occurred before the A2 command. Moreover, even if the C1 and C2 commands both occurred before B1, the A2 response can reflect B2 and not C1 or C2. The easist thing to do is to periodically produce consistent views of the data. This process will take a while so while it is happening, you'll have to use a past consistent view. Three views, call them X, Y, and Z that the system updates should be adequate. At all times, one view will be "current", one will be being generated, and the third will be a source for stragglers. Here's how the update process works. While X is being generated, from Z and all data received since Z's generation started, Y will be used to produce results to send to users. While Y is being generated, from X and all data received since X's generation started, X will be used to produce results to send to users. And similarly for Z (using Y). Suppose that user A sends a command while Y is being generated from X. The response to A need only reflect X and commands that A sent since X was generated. As long as that can be finished before the system finishes generating Y and Z, everything is copacetic.

by owkaye 18y ago

owkaye 18y ago

In my last long post I said Retric was wrong about providing data that's accurate only to +/- .2 seconds, but maybe I'm the one who is wrong. It is possible that I completely misinterpreted his meaning. I became aware of this possibility when I read lacker's post that said I can probably batch up data since I'm going to have latency issues anyways. He's right, I never thought of it this way. The issue I'm imagining with batching is that I cannot send any data back to visitors until the next batch is processed -- because if I do they won't see how their last post has changed their positions in the hierarchy, and they will interpret this as a system error. In other words, every time a member receives a response from the server, that response must indicate his last post's position in the hierarchy. Theoretically I could run a batch every second, and although this means holding up all the responses to requests that come in during the previous second, one second is also short enough that they will not interpret it as a problem with the system. On the other hand, 5 seconds in between batches would certainly be seen as a server problem especially by folks on high speed connections.

mseebach 18y ago
So you problem is not processing 1.000.000 requests pr. minutes, but rather how to sort up to 60.000.000 items 1.000.000 times pr. minute? Now that could prove to be quite problematic. If your sorting algorithm only requires one processing instruction pr. stored item, and is perfectly parallelizable, and there's zero overhead in the map-reduce, you'll need 300 3 ghz cores to do it.
- lallysingh 18y ago
  Hmm, nlogn(60,000,000) ~= 1,560,000,000 ops per sort, before your coefficient. If you want that done at 16.67 KHz (1 million times/min), you'll need some work. You can do it, in certain cases, with certain hardware & good skills, but it's tricky. I'm still not buying that the requirements are really that high.
anamax 18y ago
> The issue I'm imagining with batching is that I cannot send any data back to visitors until the next batch is processed -- because if I do they won't see how their last post has changed their positions in the hierarchy, and they will interpret this as a system error. In other words, every time a member receives a response from the server, that response must indicate his last post's position in the hierarchy. You're making this much harder than it has to be because you're assuming that users can see things that they can't. Suppose that the system had two users, A and B, and they each issued two commands, A1 and A2 in that order from A and B1 and B2 from B. Suppose further that system responds to each command with something that it says is the global state. To keep things simple, I'll use the command, such as A2, to refer to the response as well. (In other words, A2 is the response that A gets to command A2.) A knows that she issued A1 and A2 in that order, so the A2 response must reflect commands A1 and A2. However, the A2 response need not reflect B1 or B2 unless A has some way to know that B issued them before A2, regardless of when B1 and B2 were issued in relation to A2. In fact, it's probably okay for the A2 response to reflect command B2 and not command B1. Now let's throw C into the mix, issuing C1 and C2 in that order. As with B, the A2 response need not reflect C1 or C2 even if they actually occurred before the A2 command. Moreover, even if the C1 and C2 commands both occurred before B1, the A2 response can reflect B2 and not C1 or C2. The easist thing to do is to periodically produce consistent views of the data. This process will take a while so while it is happening, you'll have to use a past consistent view. Three views, call them X, Y, and Z that the system updates should be adequate. At all times, one view will be "current", one will be being generated, and the third will be a source for stragglers. Here's how the update process works. While X is being generated, from Z and all data received since Z's generation started, Y will be used to produce results to send to users. While Y is being generated, from X and all data received since X's generation started, X will be used to produce results to send to users. And similarly for Z (using Y). Suppose that user A sends a command while Y is being generated from X. The response to A need only reflect X and commands that A sent since X was generated. As long as that can be finished before the system finishes generating Y and Z, everything is copacetic.