Comment by owkaye | Hacker News Reader

Comment by owkaye | Hacker News Reader

Here are my answers / comments to some of the recent posts (more replies to come). Thanks again to everyone for your help and please keep your suggestions coming:

to swombat: The clients will have javascript so short commands rather than entire pages can be passed. Thanks for this suggestion, implementing this alone may totally eliminate my web server issues.

to jwilliams: You said even if my page is tiny that's still 1Gbps sustained, so by implementing swombat's javascript solution I can (hopefully) pass only data, thereby avoiding the potential bandwidth issue.

to swombat: The data cannot be stale, the response MUST include the results of the database search that is performed immediately after the visitor's last post is appended to the database.

to andr and swombat: I don't know what 'sharding' or 'microsharding' is but if the additional details I've recently posted is any help, maybe one or both of you can tell me if you think it is something that's possible, practical and/or appropriate to my needs?

to mseebach: Yes, every single write will affect every single subsequent read in a non-trivial manner. You said the hardware will cost a lot and I'm sure that's true, but I expect the money will become available if the system I've conceived can be built to function as I'm trying to describe it here.

to EVERYONE:

Given the information you all have provided prior to the time I wrote this post, I have further refined my approach to this problem as follows. Please tell me if this is the best approach in your opinions:

1- I will use JavaScript to eliminate page loads and pass only the required 5-10 characters of data from the visitor to the server each time. This should reduce or eliminate the need for multiple web servers and dramatically reduce bandwidth requirements.

2- I will find someone who knows C to write an app that receives the data from each browser, pass it to the database with an append command, pass another command to search/sort the database table, retrieve the results, and pass them back to the JavaScript in the visitor's browser.

If this appears to be the best approach so far, I still need to solve the database issue. If you have any new comments or suggestions that might help me find the database hardware or software I need, please post them here, thanks.

It seems you would be better off using some custom in-memory data structure rather than classical ready-made database solution.

You do not want to sort the whole dataset after each new piece of data comes. You want to insert each new entry right into its place (probably via some hashing).

If, of course, it is possible. Too little details about what you want to do with the aggregate data.

Before you start writing code and making architecture decisions, you need to do some sanity testing. Can you even run 15,000 SQL inserts per second of the format you want on a single machine? If not, you may need to abandon using a database entirely. You can test this with a simple script and the results might invalidate your whole plan.

Also, I'm betting you don't actually need to support this kind of load to do what you want to do. In particular you can probably batch up data, since you are going to have latency issues anyways. You need a specific target for the latency you need, and then do some measurement figuring out how much batching you can do.

Why don't you explain your idea in more detail? The community can probably be more helpful then.

"new record is appended, a search is performed and the post field is sorted, then the relative position of the visitor's new database record is identified in the results (example 49,501 records from the top)."

It might be a good idea to try to twist things so that no sort is necessary - instead of appending and then sorting you should try to insert the data right at the spot it should be. If your constraints allow you to not use a database, you could consider a data structure that inserts data in such a way that it is always sorted.

Also, as an improvement to your point 1, you should put most of the JavaScript itself as well as images, etc somewhere else - with this your bandwidth will be used only for the dynamic data (which will be more than enough).

Finally, the best tool I know for scalability are queues. Try to reorganize what you are doing to arrive at an architecture where you put things on queues that multiple consumers will process.

Yes, eliminating the sorting is a better way to approach the problem I believe. I've always just 'sorted' to determine a new record's position in the list, but it seems there may be other (more efficient) ways to determine the record's position without sorting ...

Do all of the rankings need the same precision? Maybe you can get away with perfect accuracy for the top 1,000 rankings and then provide an approximation for anything >1,000?

You could use a list for the first 1,000 and then store the rest in a tree. Then have another process that walks the tree in-order and updates the ranking of each node.

You could cache or replicate the database for reads. When a post comes in, insert it into the master database, then sleep for a preset amount of time, then have it start checking the local database copy to wait for it to show up, then run the query. Just use timestamp <= posters_timestamp to get the result set you want.

Adjust the sleep time based how frequent the cache updates are.

you really, really don't want to be using a relational database here. hitting disks a million times per minute would be disastrous, if not for performance then for blocking IO, even with only row-level locking.

I'd look into memcached and write state to disk every once in a while to back up, kind of a reverse from what's usually done. Or, if thats really not enough, I'd look up Hadoop riding on GlusterFS. You're going to have synchrony and blocking problems no matter what, though, without really creative keying (bigtable style?). Both Facebook and Google have run up against these kinds of issues and have written and/or released source about it. Facebook has OSS'd Cassandra, their distributed database, and Google hasn't released much code but has papers out on their implementations of MapReduce (open source port->Hadoop, as suggested above) and BigTable (which the Hadoop team are in the process of cloning with HBase).

pass only the required 5-10 characters of data from the visitor to the server each time

It'll still (generally) need to be HTTP, so there will be a lot of other cruft around it. If you were to use Java or Flash you might be able to get around this.

Use a hierarchy of CDN's; play around with TTL's and/or IMS headers.

Reply on news.ycombinator.com