; ; "Virtuso Data Space Bot" . , ; ; "vdb's BLOG [136] description" . ; . , , ; "Architectures for Infinity" ; ; "Architectures for Infinity" ; "2008-04-14T05:41:42.000-04:00"^^ ; "2008-04-14T13:19:56.5000-04:00"^^ ; ; "09e4514dc1aa447a4d04e3c9ab6e899d" ; ; "<div><div style="display:none;">Architectures for Infinity</div><p>A while back, a friend suggested he and I go check out the <a href="http://www.kurzweilai.net/" id="link-idfed3e58">Singularity\nSummit</a>, a conference where they talk of strong AI. Well, I am not a\nsingularist. But since singularists are so brazenly provocative, I\nlooked a little to see if there is anything there, engineering-wise.</p>\n<p>So, for a change, we&#39;ll be visionary. Read on, I also mention <a href="http://dbpedia.org/resource/RDF" id="link-id109a58e8">RDF</a> at the end.</p>\n<p>I will not even begin with arguments about indefinitely continuing a\ntrend. I will just say that nature has continuous and discontinuous\nfeatures. Computing is at a qualitative bend and things are not as\nsimple as they are blithely cracked up to be. Read HEC, the high end\ncrusader; he has good commentary on architecture. Having absorbed and\nunderstood this, you can talk again about a billion-fold increase in\ncomputing price/performance.</p>\n<p>When I looked further, about uploading, i.e., the sci-fi process of\nscanning a brain and having it continue its function inside a\ncomputer simulation, I actually found some serious work. <a href="http://p9.hostingprod.com/@modha.org/" id="link-id10bf26d0">Dharmendra\nModha</a> at IBM had made a rat-scale cortical simulator running on a 32K\nnode IBM BlueGene, with a 9x slowdown from real time. This is real\nstuff and in no way meant to be associated with singularism by being\nmentioned in the same paragraph. Anyway, I was intrigued.</p>\n<p>So I asked myself if I could do better. I gave it a fair try, as fair\nas can be without an actual experiment. The end result is that\nlatency rules. To have deterministic semantics, one must sync across\ntens of thousands of processors and one cannot entirely eliminate\nmulti-hop messages on the interconnect fabric. If one optimistically\nprecalculates and spreads optimistic results over the cluster, rolling\nthem back will be expensive. Local optimistic computation may have\nlittle point since most data points will directly depend on non local\ndata. One needs two sets of wiring, a 3D torus for predominantly\nclose range bulk and a tree for sync, just like the BlueGene has.\nMaking the same from newer hardware makes it more economical but\nthere&#39;s another 8 or so orders of magnitude to go before energy\nefficiency parity with biology. Anyway, a many-times-over\nqualitative gap. Human scale in real time might be just there\nsomewhere in reach with the stuff now in pre-release if there were no\nbounds on cost or power consumption. We&#39;d be talking billions at\nleast and even then it is iffy. But this is of little relevance as\nlong as the rat scale is at the level of a systems test for the\nplatform and not actually simulating a plausible organism in some sort\nof virtual environment. Anyway, of biology I cannot judge and for the\ncomputer science, Modha et al have it figured out about as well as can.</p>\n<p>Simulation workloads are not the same as database. Database is easier\nin a way since any global sync is very rare. 2PC seldom touches every\npartition and if it does, the time to update was anyway greater than\nthe time to commit. Databases are generally multi-user, with a low\nlevel of sync between users and a lot of asynchrony. On the\nother hand, the general case of database does not have predictable\ncluster locality. Well, if one has an OLTP app with a controlled set\nof transactions and reports, then one can partition just for that and\nhave almost 100% affinity between the host serving the connection and\nthe data. With <a href="http://dbpedia.org/resource/RDF" id="link-id10c92378">RDF</a> for example, such is not generally possible or\nwould require such acrobatics of data layout that a DBA would not even\nbegin.</p>\n<p>So, for database, there is a pretty much even probability for any\nconnection between the node running the query and any other. True,\nfunction shipping can make the messages large and fairly async and\nlatency tolerant.</p>\n<p>On the simulation side, it would seem that the wiring can mimic\nlocality of the simulated process. Messages to neighbors are more\nlikely than messages to remote nodes. So a 3D torus works well there,\ncomplemented by a tree for control messages, like sending all nodes\nthe count of messages to expect. Of course, the control wiring\n(reduce tree) must have far less latency than a long path through the\ntorus wiring and steps with long message deliveries on the torus must\nbe rare for this to bring any profit. Also, long distance messages\ncan go through the tree wiring if the volume is not excessive, else\nthe tree top gets congested.</p>\n<p>So, looking past the multicore/multithread and a single level switched\ninterconnect, what would the architecture of the total knowledge\nmachine be? For the neural simulation, the above-described is the\nbest I can come up with and IBM already has come up with it anyway.\nBut here I am more concerned with a database/symbol processing\nworkload than about physical simulation. For the record, I&#39;ll say\nthat I expect no strong AI to emerge from these pursuits but that they\nwill still be useful, basically as a support for a linked data\n&quot;planetary datasphere.&quot; Like Google, except it supports arbitrary\nqueries joining arbitrary data at web scale. This would be a couple\nof orders of magnitude above the text index of same. Now, in\npractice, most queries will be rather trivial, so it is not that the 2\norders of magnitude are always realized. This would also involve a\nbit more updating than the equivalent text index since reports would\nnow and then include private materialized inference results. As a\ngeneral rule, backward chaining would be nicer, since this is read\nonly but some private workspaces for distilling data cannot be\navoided.</p>\n<p>So, given this general spec, where should architecture go? We can talk of processors, networks and software in turn.</p>\n<h3>Processors </h3>\n<p>For evaluating processors, the archetypal task is doing a single\nrandom lookup out of a big index. Whether it is a B tree or hash is not\nreally essential since both will have to be built of fixed size pages\nand will have more than one level. Both need some serialization for\nchecking if things are in memory and for pinning them in cache for the\nduration of processing. This is eternally true as long as updates are\npermitted, even if RAM were the bottom of the hierarchy. And if not,\nthen there is the checking of whether a page is in memory and the\nlogic for pinning it.</p>\n<p>This means critical sections on shared data structures with small memory writes inside. This is\nanathema, yet true. So, what the processor needs is shared memory for\nthreads and if possible an instruction for entry into a read-write\nlock. If the lock is busy, there should be a settable interval before\nthe thread is removed from the core. With a multithread core, this\nshould be just like a memory cache miss. Only if this were really\nprolonged would there be an interrupt to run the OS scheduler to\nvacate the thread and load something else, and not even this if the\nnumber of executable threads were less or equal the number of threads\non the cores. </p>\n<p>For thread sync structures, the transactional memory ideas on the SPARC ROC\nmight be going in this direction. For on-core threading, I have not\ntried how well SPARC T2 does but with the right OS support, it might\nbe in the ballpark. The X86_64 chips have nice thread speed but the\nOS, whether Solaris or Linux, is a disaster if a mutex is busy. Don&#39;t\nknow why but so it is.</p>\n<p>Things like IBM Cell, with multiple integrated distributed memory\nprocessors on a chip might be workable if they had hardware for global\ncritical sections and if sub-microsecond tasks could be profitably\ndispatched to the specialized cores (synergistic unit in Cell\nterminology). If an index lookup, about 2-4 microseconds of real\ntime, could be profitably carried out on a synergistic core without\nsinking it all in sync delays on the main core, there might be some\ngain to this. Still, operations like cache lookups tend to be pointer\nchasing and latency of small memory reads and sometimes writes is a\nbig factor. I have not measured Cell for this but it is not\nadvertised for this sort of workload. It might do nicely for the\nneuron simulator but not for generic database, I would\nguess.</p>\n<h3>Networks and Data Center </h3>\n<p>The point at which distributed memory wins over shared determines the\nsize of the single compute node. Problems of threads and critical\nsections fall off but are replaced by network and the troubles of\nscheduling and serializing and de-serializing messages. There are\nreally huge shared memory systems (by Cray, for example) but even there,\nhitting the wrong address sends a high latency message over an\ninternal switched fabric, a bit like a network page fault. Well, if\none has millions of threads runnable for catching the slack of memory access over interconnect,\nthis might not be so bad, but this is not really the\narchitecture for a general purpose database. So, at some point, we\nhave clearly demarcated distributed memory with affinity of data to processor, simple as that.</p>\n<p>For now, the high end clustered database benchmarks run off 1 Gbit\nethernet fabrics with some 30 compute nodes on a single switch. This\nis for shared nothing systems. For shared disk, cache fusion systems\nlike Oracle RAC, we have more heavy duty networking like Infiniband,\nas one would expect. I have discussed the merits of cache fusion vs\nshared nothing partitioning on in a previous post.</p>\n<p>As long as we are at a scale that fits on a single switch with even\nport to port latency, we are set. For an <a href="http://dbpedia.org/resource/RDF">RDF</a> workload, throughput is\nnot really the issue but latency can be. With today&#39;s technology,\nnodes with 4-8 cores and 16G RAM are practical and their number is\nmost often not really large. Adding two orders of magnitude, we get\nmore questions. Let&#39;s say that 2 billion triples fit with relative\ncomfort but not without disk on a 16G RAM node. This would make 500 nodes for a trillion triples. </p>\n<p>This is an entirely relevant and reasonable scale, considering that\nloading all public biomedical sets plus a pharma company&#39;s in house\ndata could approach this ballpark. Let alone anything on the scale of\nthe social web, i.e., the online conversation space.</p>\n<p>So how to manage clusters like this? The current cluster gear is\noriented toward switch trees and is fairly expensive, about $1000 per\nnode. To make this easy, we would need a wiring free, modular\narchitecture. Picture a shelf with SATA drive size bays, each would\nget a compute node of 8 cores and 16G plus interconnect. To simplify\nthe network, the module would have a laser on each side, for a cube\nnetwork topology, the enclosure could connect the edges with fiber\noptics for the 3D torus. Mass storage would be in the same form\nfactor, as disks or flashes to be interspersed in the proper ratio\nwith compute nodes. All would have the same communication chip,\nsomething like a Cray SeaStar with 6 or 7 external ports. A seventh\nport could be used for a reduce tree. The rack would provide cooling\non the shelves by circulating a coolant fluid. Reconfiguring and\nscaling would be a matter of adding shelves to the cabinet and laying\nout Lego bricks, blue for compute and red for storage. The network\ncould achieve a latency for an arbitrary point to point message of no more than 10-20\nmicroseconds by the right mix of cube and tree. This in a box of\nthousands of nodes.</p>\n<p>This type of layout would accommodate web scale without needing rows and rows of rack cabinets.</p>\n<p>The external interfaces for web requests and replies are no big deal\nafter this, since the intra-cluster traffic is orders of magnitude\nhigher than the result set traffic. After all, the end user does not\nwant dumps of the database but highly refined and ranked results.</p>\n<h3>Software </h3>\n<p>We have previously talked about dynamic partitions a la Google\nBigtable or Amazon Dynamo. These techniques are entirely fine and\nwill serve for the universal knowledge store. </p>\n<p>But what about query logic? OK, having a consistent map of partitions\nshared over tens of thousands of nodes is entirely possible. So is\nreplication and logic for using a spatially closer partition when\nmultiple copies are know to exist. These things take some programming\nbut there is nothing really new about them. These are a direct straightforward extension of what we do for clustering right now. </p>\n<p>But look to windward. How to run complex queries and inference on the\nplatform outlined above? There are some features of RDF querying like\nsame-as that can be easily parallelized, backward-chaining style: Just\nproceed with the value at hand and initiate the lookup of synonyms and\nlet them get processed when they become available. Same for subclass\nand sub-property. We already do this, but could do it with more\nparallelism.</p>\n<p>No matter what advances in architecture take place, I do not see a\nworld where every user materializes the entailment of their own\nsame-as-es and rules over a web scale data set. So, backward chaining\napproaches to inference must develop. Luckily, what most queries need\nis simple. A rule-oriented language, like Prolog without cut will\nparallelize well enough. Some degree of memoization may be\nappropriate for cutting down on re-proving the same thing over and\nover. Memoization over a cluster is a problem though, since this\ninvolves messages. I should say that one should not go looking for\npre-proven things beyond the node at hand and that computation should\nnot spread too quickly or too promiscuously so as not to make long\nmessage paths. We must remember that a totally even round trip time\non a large cluster just will not happen.</p>\n<p>Query planning on any system critically depends on correct ballpark\nguesses on cardinality. If predicates are amplified with transitivity\nand same-as at run time, the cardinality guessing becomes harder.\nThis can kill any plan no matter the hardware. Probably, an executing\nquery must be annotated with the underlying cardinality assumptions.\nIf these prove radically false, the execution may abort and a new plan\nbe made to better match what was found out. This bears some looking into. </p>\n<p>There are some network algorithms like shortest path, traveling\nsalesman and similar that probably deserve a special operator in the\nquery language. These can benefit from parallelization and a\nsequential implementation running on a cluster with latency will be a\ndisaster. Expressing the message flow in a rule language is not\nreally simple and pretty much no programmer will either appreciate the necessity\nor go to the trouble. Therefore such things should likely be offered by the platform and made by the few people who understand such matters.</p>\n<p>For forward chaining, it seems that any results should generally go\ninto their own graph so as not to pollute the base data. This graph,\nsupposing it is small enough, can have different partitioning from\nthe large base data set. If the data comes from far and wide but\nresults are local, there is better usage of a RETE like algorithm for\ntriggering inference when data comes in. RETE will parallelize well\nenough, also for clusters,results just have to be broadcast to the\nnodes that may have a use for them.</p>\n<p>The programming model will typically be using a set of local overlays\non a large shared data set. Queries will most often not be against a\nsingle graph. Strict transactionality will be the exception rather\nthan the rule. At the database node level, there must be\nreal transactionality even if the whole system most often did not run with\nstrict ACID semantics. This is due to ACID requirements of some\ninternal ops, e.g., some bitmap index operations, log checkpoints, DDL changes, etc.</p>\n<p>For procedural tasks, map-reduce is OK. We have it even\n<a href="http://www.openlinksw.com/dataspace/oerling/weblog/Orri%20Erling%27s%20Blog/1270" id="link-id10b7ac00">in our SQL</a>. Map-reduce is not the basis for making a\nDBMS but it is a nice feature for some parts of query evaluation and application logic.</p>\n<p>We have not talked about linking the data itself, but there is a whole workshop on this next week in <a href="http://www2008.org/" id="link-id14a5aa00">Beijing</a>; I will write about it separately. \nLet this just serve to state that we are serious about the platform for this, present and future.</p>\n<h3>Conclusion </h3>\n<p>The web scale database, the Google with arbitrary joining and\ninference, is one generation away, talking of economical\nimplementation. Today, a price tag of $100K will buy some 50-100\nbillion triples worth with reasonable query response. Unlimited\nbudget will take this a bit further, like one order of magnitude. and\nthen, returns might be decreasing.</p>\n<p>Of course, this is worth nothing if the software isn&#39;t there.\n<a href="http://data.openlinksw.com/oplweb/product_family/virtuoso#this" id="link-idfdcf058">Virtuoso</a> with its cluster edition will allow one to use unlimited RAM and\nprocessors. The frontier is now at getting just the right parallelism for\neach task, including inference ones.</p>\n<a href="index.vspx?tag=database" rel="tag" style="display:none;">database</a><a href="index.vspx?tag=databases" rel="tag" style="display:none;">databases</a><a href="index.vspx?tag=architecture" rel="tag" style="display:none;">architecture</a><a href="index.vspx?tag=hpc" rel="tag" style="display:none;">hpc</a><a href="index.vspx?tag=semanticweb" rel="tag" style="display:none;">semanticweb</a></div>" ; "Architectures for Infinity" ; ; ; , , , , ; ; ; "2008-04-14T09:41:42Z" ; "2008-04-14T17:19:56Z" ; ; "http://www.openlinksw.com/dataspace/vdb/weblog/vdb%27s%20BLOG%20%5B136%5D/1339" ; "alternate" . ; ; "Virtuso Data Space Bot" ; . , ; ; "vdb's BLOG [136] description" ; ; ; . ; ; . ; .