Designing a global knowledge base (by alaric)
Continuing from my previous posts on HYDROGEN and IRON, I suppose the next thing I can talk about is CARBON.
One thing that users expect out of a system is some form of navigational structure. All but the simplest embedded computer systems have some kind of menu structure; while workstations often have several somewhat confusingly overlaid structures (menus in applications, a "My Documents" hierarchy full of personal stuff, a "Start Menu" or "Applications Folder" full of system-wide resources, and a "My Computer" hierarchy with things like removable drives and their contents, printers, access to the internals of the system, mounted network drives, and the like; then, via a Web browser, a hierarchy of bookmarks and then whatever navigational structures different Web sites out in the world present to you.
So, I clearly needed some concept of "large-scale organisation of resources" in ARGON. After much deliberation, I came up with CARBON. But, as usual, I like to kill several birds with one stone.
Entities
The "resources" in question in ARGON are entities. These are the objects users will see, and that sysadmins will manage. But the actual implementation of an entity occurs at various layers in the ARGON stack; the lowest layer being MERCURY - the protocol for accessing network resources - as entities are the targets of MERCURY invocations. The interface an ARGON cluster has to the outside world is a set of entities; and even non-ARGON clients will be accessing entities, albeit through a FLUORINE adapter that wraps the MERCURY interface to the entity in protocols such as HTTP.
A entity is identified by an "entity ID", or EID, which is an identifier consisting of a cluster identifier (containing information about how to contact that cluster over the network, and either the cluster's public key or a hash thereof) combined with an opaque binary string identifying the entity within the cluster.
So, from the perspective of MERCURY, an ARGON entity is a kind of distributed object, and MERCURY lets you remotely invoke methods on that object; but the details of MERCURY can wait for another blog post, as they rather recursively depend on CARBON somewhat (with some magic to bootstrap the two!). CARBON sits on top of MERCURY, as a standard set of methods for entities to provide information. The act of providing information is idempotent, at least from the perspective of the user; any side-effects of a CARBON request are the responsibility of the entity that handles them, just like with an HTTP GET request. Because of this, by convention, ARGON applications do not directly query the CARBON interfaces of entities; instead, they'll go through a CARBON resolution service provided by their cluster, which provides various important services such as caching (like a DNS resolver or a caching HTTP proxy server), and also local rewriting, which we'll cover later.
Caching can happen at the server end as well as the client; I expect to special-case CARBON activity in MERCURY.
Normally, sending a MERCURY invocation to an entity would involve the server that handles the request handing the request over to LITHIUM, which loads entity code (which CHROME, the high-level language system, compiles) and data from the TUNGSTEN database in order to handle the request, then asking HELIUM to run it in a sandbox, then sending the results back.
But for CARBON requests, the responses always contain caching information, similar to the cache control headers in HTTP. As well as being used for caching at the client end, the serving cluster may cache the results of CARBON requests directly into TUNGSTEN (or even into a memcached-like distributed memory cache that WOLFRAM might provide in a future version), so that future requests can be serviced directly from the cache, without having to fire up LITHIUM.
Also, a future version of the CARBON protocol could even support the BitTorrent protocol, allowing large numbers of clients to co-operatively distribute the same object without overburdening the server.
So CARBON is quite similar to HTTP GET requests in some ways. But while the response to an HTTP request is a byte string with a content type, which might be HTML or something else, the contents of a CARBON response are always the same thing: a series of CARBON clauses. Which brings us on to the CARBON data model.
Knowledge bases
CARBON represents information as a series of clauses stating facts about objects. Those familiar with Prolog (programming language), RDF, or formal logic will recognise this approach. When you ask a given entity for its CARBON information, rather than returning a data structure of the form "Type: Image. Name: Me on the beach. Creation date: 2009/07/12. Size: 1024x798px", as might be expected, we instead return a series of statements (encoded in IRON, of course), more like this:
[c:OverallTypeOf: [c:eid "...ID of entity..."] is: i:Image]
[c:TitleOf: [c:eid "...ID of entity..."] is: "Me on the beach"]
[c:CreationDateOf: [c:eid "...ID of entity..."] is: [fe:date 2009 07 12]]
[i:ImagePixelDimensionsOf: [c:eid "...ID of entity..."] width: 1024 height: 768]
Clearly, this means that a given CARBON response need not only contain information about that entity - it can return information about other entities, too. This is particularly useful, as it makes it possible to merge information from multiple sources: one might ask an entity what it has to say about itself, while merging in your own notes upon it, as well as merging in information about that entity from a public review database.
The navigational structure of CARBON is provided by two mechanisms working together. The statement [c:Entity: <eid> hasChild: <eid> called: <string>] states that one entity is a child of another, forming a tree structure (an entity should also contain a statement that it is the child of some other entity, so the parent of any entity can be found easily). For non-tree-like relationships, we also provide a "symlink" in the form of [c:Entity: <eid> linksTo: <eid> called: <string>], which works much like hasChild except that it does not imply containment. CARBON provides a mechanism for naming entities by following these links; There's a global CARBON root entity hardcoded in from which resolution begins, which I'll run as a public service if I get this off the ground; but private local subtrees can be set up, visible only within a given cluster, by placing statements into a knowledge base within the cluster that gets merged into every CARBON resolution operation, which can add local information to the global tree.
As well as plain statements, as given above, CARBON also allows rules. Rules themselves are a kind of statement, but a statement stating that a certain pattern of statement can be deduced if other statements are true. A rule might look like:
[c:Rule: [Individual: $X DescendsFrom: $Y]
If: [c:Or
[Individual: $X IsChildOf: $Y]
[c:And
[Individual: $X IsChildOf: $Z]
[Individual: $Z DescendsFrom: $y]]]]
That rule states that $X descends from $Y, for any $X and $Y, if either $X is the child of $Y or $X is the child of some $Z who descends from $Y. Symbols starting with $ in CARBON represent placeholder variables in rules.
What CARBON is used for
The list of services available in MERCURY is listed in CARBON, assigning numeric endpoint identifiers (reminiscent of port numbers) to each logical interface; the fact that CARBON itself is a MERCURY service is bootstrapped by reserving a well-known endpoint identifier for it, specified in a common set of rules hard-coded into the CARBON resolving engine:
[c:Rule [c:Entity: $X ProvidesInterface: </argon/carbon> OnEndpoint: 0]]
As this is a rule with no If: part, it always matches - meaning that it states that any entity provides the CARBON interface on endpoint zero.
It's also possible to expose dynamic services of the entity via CARBON. One can embed callback rules, that do not contain an If: part that would allow the client to deduce the rule themselves; instead, the query must be forwarded back to the entity via the CARBON protocol, which will then return an additional CARBON response with the answer(s). This allows you to write an entity that dynamically provides information from a database, temperature sensor, or alien protocol (such as HTTP) into CARBON.
As well as browsing metadata (names, summary information, hierarchical relationships and links), contact information for available services, and other forms of information, CARBON is also used to specify a user interface for an entity (although that's the topic of NEON); this user interface can range from simple static presentation (like HTML), up to embedded CHROME source code for an interactive 'applet' to be run on the client, connecting back to the entity via MERCURY and CARBON for access to its state. CARBON is also used to distribute software - CHROME libraries are entities, identified by their entity ID or their CARBON name, stored as source code in CARBON.
Efficiency
But all of these more specialist uses will bulk up the size of the CARBON knowledge-base for a given entity. Sometimes you'll only be wanting to know the name of the entity and whether it has any children, to resolve a path. Because of this, the protocol used to request "callbacks" for callback rules is generalised; in every CARBON request it's possible to list the partial rules you're trying to resolve, in which case the entity just responds with what seems pertinent (which may be more than what you ask for). So doing a request with no filters makes it return every rule inside it that doesn't need to be calculated dynamically (but returns the callback rule specifying that the rule is available if it's wanted), while a request referring to a dynamic rule causes it to be processed within the entity and the result returned, while a request referring to static rules just returns those rules (and a request referring to both dynamic and static rules returns both). In other words, it's up to the CARBON implementation on the server to decide when to "trigger" dynamic rules, and when to just specify that they exist and are available as callbacks; and it's up to the client to send specific requests to avoid getting lumped with a lot of information it doesn't want.
Gateways
There's explicit support in CARBON for encapsulating alien systems (SQL databases, the Internet, POSIX filesystems, and the like) - the dynamic callback rules help, as they allow the gateway entity to convert requests into requests into the alien system, but a little more is needed. So I've added the notion of a persona. It's possible for code within an entity to ask for its own Entity ID, so that it knows who it is, and can craft CARBON responses with statements about itself; but it's also possible for it to ask to create "virtual entity IDs" by specifying a persona, an arbitrary IRON object that is combined with the entity's real ID to create a different entity ID. MERCURY requests (including CARBON) for that virtual entity ID therefore go to the same physical entity, but have the persona embedded in the request header, allowing the entity to provide a different interface.
In effect, this is exactly like query strings in HTTP URLs; one might have a URL that denotes a gateway to an LDAP database, say http://www.example.com/ldap. Visiting that URL might give you a search interface to find the LDAP name of an object, rendered as a clickable link of the form http://www.example.com/ldap?dc=com,dc=example,ou=Sales,cn=Bob Jones, or even http://www.example.com/ldap/dc=com,dc=example,ou=Sales,cn=Bob Jones. The web server will still pass that request to the same server-side resource (a CGI script or whatever), but it'll make the URL available to it, so it can see the embedded LDAP name and know what LDAP object to fetch and display as HTML.
Security
CARBON builds upon the MERCURY security model; a MERCURY request or response can carry cryptographic authentication of the sending cluster, which then states the ID of the entity making the request (which must be an entity whose ID is actually within that cluster, of course); and a request can be encrypted so that only the intended recipient cluster can decode it. This allows the entity to make decisions about what information it exposes in the response to any given CARBON request, and to protect confidential information in transit. Encrypted CARBON responses are never cached.
We only need to authenticate and encrypt at the cluster level; if we trust the cluster, we can trust it to tell us which entity within the cluster is initiating a request, or to route the request to the correct destination entity; if we don't trust the cluster, then we can't trust any entity within it anyway. In other words, we can't trust an entity any more than we can trust its cluster, so any trust assigned to an entity requires us to trust the cluster at least that much.
Conclusion
As is usual with ARGON, I've looked at how things are currently done, and tried to simplify them by merging common requirements. The Internet has myriad ways of requesting information, both static and dynamic - DNS, HTTP, and BitTorrent provide protocols, while the number of standards for representing information is just too vast to list. By having the IRON system for mapping instances of a standard data model into strings of bytes along with the MERCURY protocol for accessing services provided by entities, and then building CARBON on top of both, I've designed a unified infrastructure for the basic operation of publishing information, encompassing the tiniest DNS-like naming requests up to the distribution of software and access to dynamic information sources, all using a common data model that is extensible, expressive, and easy to do complex things with.
Thu 20th Aug 2009 10:50 am 
Subscribe