Distributed Primitive Database

From Second Life Wiki
Jump to: navigation, search
KBnote.png Note: This project is pending to be extended in an article. So far, the code is functional but at some point it should be cleaned up and revised. It is on our TODO list... Just like everything else.

About

  • Created by Kira Komarov.
  • The memory module contains an ASCII compression algorithm created by Becky Pippen.
  • This project is the database version of the Intercom. If you are looking for the Intercom version of the these scripts, please try that link.

Changelog

30 January 2012

  • As a result of discussions with Benjamin Bowenford, I have fixed the last script and updated the set-up procedures.

28 August 2011

  • Changed GET/PUT to FETCH and REPLACE to be in theme with the database.
  • Fixed data replication.
  • Changed URL replication scheme.
  • Forked the ADDRESS REPLICATOR into two parts; it seems that the compression algorithm takes a long time and makes the primitive unresponsive.
  • Lots of fixes and tests done on the code.

27 August 2011 @ 18:45

  • Updated the database processor because of raptor jumps which messed up replication entirely.

27 August 2011

  • Added scripts.

26 August 2011

  • Started article.

News

At 1am on 30th of August I managed to cross-link the Distributed Primitive Database between the OSGrid and Linden Lab's SecondLife by using an altered version of the scripts. I have also adapted the Intercom and managed to cross-chat between the OSGrid and SecondLife by using the same principle described here. It seems that this technique will not only work cross-region, however it will also work cross-grid.

I run an OpenSim estate, hooked up the the OSGrid. I have altered the code in the Distributed Primitive Database as well as in the Intercom version by knocking out the URL checks in the isValidURL() function that I wrote. For compatibility with OSL, I also had to knock out the jumps, probably a case of raptors again. I followed the same procedure described in both articles, I added the URL of a prim on the OSGrid to a primitive on the SecondLife grid. After a few minutes, replication started amongst the primitives and pretty soon the primitive on the OSGrid already replicated all the data I had on the SecondLife grid. This rocks. :-)

Motivation

These series of scripts will help you set-up a database based on a simple syntax that will allow you to maintain a database within Second Life and without using any external databases. The advantage is that it will cut down on the cost of needing something external to Second Life to maintain parameters which may be reset over a SIM restart or a SIM crash.

Distributed Systems and Databases

Since we cannot achieve true persistent data storage in SL, we cannot rely on a script to hold the same parameters after a sim restart or when the primitive containing it is de-rezzed. By broadcasting and replicating between primitives placed in different regions grid-wide we reduce the likelihood that all the primitives containing the replicated data will all go down because of a SIM restart or a primitive return at the same time.

Theoretically, each primitive containing the data represents a node in a star-shaped network where all the nodes are connected to all other nodes. By doing that we ensure that the distributed system based on the DPD has no single point of failure. That means, that it is unlikely that all the primitives placed in different regions will loose their data simultaneously. Whenever a node, represented by a primitive in the network, goes down, it looses its data. However, every DPD node temporarily commits a few URLs to invisible text storage so that when it resets it kickstarts by reading those URLs and attempts to join the network.

For effectiveness one would need a minimum of 2 (two) primitives placed in different regions. This would ensure that there is at least a two-way fallback replication between the two nodes. Thus, the danger that the stored data will be lost decreases proportionally to the number of DPD primitives on the grid.

Concerning grid-wide rolling restarts, there is a significative delay before the restart shockwave hits all the SIMs. By having a primitive before the restart shockwave and a primitive after the restart shockwave we could ensure that the data is grabbed and replicated to at least a node before the shockwave hits the SIMs containing the other nodes. Given some persistent storage to kickstart a restarted node, the data would replicate back to the restarted node after the restart shockwave decouples it from the DPD network.

One could maintain a database within SL this way. When the data to be distributed is updated, it would have to be replicated to all nodes and depending on a time interval which could be a slow or a fast replication up to the limit of being at most once per second. When the data is to be pulled from the database, only one single reply would be necessary and would not generate an all-star node traffic as data changes would generate. The data can also be pulled off the URLs directly without needing to use the DPD script; for example, an external program accessing one URL of the DPD network.

Here is a list of Pros and Cons I could think about:

Pros:

  • eliminates the need for an off-world database such as mysql which implies server costs, uptime and PHP style languages to fiddle with.
  • could allow entrepreneurs to provide storage by creating intercom farms in different regions.

Cons:

  • would require at least 1 (one) prim per region and preferably as many as possible primitives grid-wide.

How it Works

The script requests an URL whenever it is reset or the region changes. It then listens for messages on that URL. When another DPD node connects to its URL, the scripts will start replicating its own URLs to the newly connected DPD as well as add the newly connected DPD URL to its own pool.

More precisely formulated:

Following the same algorithm, and having several primitives, say N primitives, named for example's sake, PRIMITIVE_1, PRIMITIVE_2 to PRIMITIVE_N in N different regions, even if a PRIMITIVE_X would go down because of a restart, when that primitive restarts comes back up, it would be sufficient to add the new URL, URL_N of PRIMITIVE_N to ANY primitive in the chain PRIMITIVE_1, PRIMITIVE_2 to PRIMITIVE_N-1, so that after a while PRIMITIVE_X will have obtained the full list of primitive URLs of all the other primitives PRIMITIVE_1, PRIMITIVE_2 to PRIMITIVE_N in the list as well as replicating its own URL_X to all other primitives in the chain PRIMITIVE_1, PRIMITIVE_2 to PRIMITIVE_N-1.

For example, given two primitives:

  • Suppose that a primitive PRIMITIVE_1 containing this script has an URL of the form http://URL_1.
  • Suppose that another primitive PRIMITIVE_2 in a different region has an URL of the form http://URL_2.
  • When you add http://URL_2 to PRIMITIVE_1, then the URL http://URL_2 will register with PRIMTIVE_1.
  • After http://URL_2 is registered with PRIMTIVE_1, PRIMITIVE_1 will start sending its list of URLs to PRIMITIVE_2. This will have the effect, that PRIMITIVE_2 will also obtain the URL of PRIMITIVE_1.

Every database primitive (DPD node), maintains two bijective maps between three lists, a key list to a value list and a time stamp list. Every key from the key list maps to exactly one value in the codomain of the values list and exactly one value in the codomain of the timestamp list. Thus, whenever a key is added to the key list, its value is inserted in the list of values along with a timestamp which is placed in the list of timestamps. When the DPD nodes communicate, the key-value mapping is updated based on their corresponding timestamp list by replacing the key-value map by the most recent timestamp.

That is, for example:

  • Suppose that, for a DPD node, the domain of keys contains two values KEY_X and KEY_Y and that the codomain of values contains the corresponding values VALUE_X and VALUE_Y and that the codomain of timestamps contains TIMESTAMP_X and TIMESTAMP_Y.
  • The bijection maps KEY_X to VALUE_X and KEY_X to TIMESTAMP_X. Similarly it maps KEY_Y to VALUE_Y and KEY_Y to TIMESTAMP_Y.
  • Now suppose a new data update is sent to this DPD node which contains a map from KEY_X to VALUE_Z and KEY_X to TIMESTAMP_Z.
  • When this data arrives, the DPD node searches for KEY_X in its data set. If it exists, it compares TIMESTAMP_X with TIMESTAMP_Z. If TIMESTAMP_Z is more recent or equal to TIMESTAMP_X, then VALUE_X is updated to VALUE_Z and TIMESTAMP_X becomes TIMESTAMP_Z. If TIMESTAMP_X is more recent than TIMESTAMP_Z, then it discards the update and keeps the original maps. If KEY_X does not exist this DPDs dataset, it is added by creating a new entry for KEY_X and mapping KEY_X to VALUE_Z and TIMESTAMP_Z.

The database model follows a decentralised peer-to-peer network mode of operation where each client and server are interchangeable and contribute to the network. However, for brevity, the clients only expand the network whereas the servers both extend the network and additionally propagate the data. Synchronisation and data precedence is attained by the exchange of timestamps since it does not vary and does not decrease in time.

Quick Set-Up

For a demonstration, use the following steps to set-up a two-node DPD network with one client:

  1. Create two primitives and change their name to DB1 and DB2 respectively.
  2. Go the the "Server Scripts" section of this article and copy the scripts DATABASE ADDRESS REPLICATOR, DATABASE DATA REPLICATOR, DATABASE KICKSTART MODULE and DATABASE PROCESSOR.
  3. Drop these four scripts in both primitives DB1 and DB2.
  4. Click either primitive DB1 or DB2 and select [ My URL ] from the dialog menu and copy the address it will tell you on the main chat.
  5. Click the other primitive and select [ Add URL ] and follow the instructions on the main chat to add the URL you got at step 4.
  6. Create a third primitive and name it CLIENT.
  7. Go to the "Client Scripts" section of this article and copy the scripts DATABASE CLIENT, DATABASE TEST MODULE as well as the DATABASE PROCESSOR and the DATABASE KICKSTART MODULE from the "Server Scripts" section.
  8. Drop the three scripts from point 7. into the third primitive named CLIENT.
  9. Touch the CLIENT primitive and select [ Add URL ] and follow the instructions on the main chat to add the URL you got at step 4.
  10. Wait for the two databases DB1 and DB2 and the client to hook up. You can watch this happening by clicking either the DB1 primitive or the DB2 primitive and selecting [ List URLs ]. After a while, both DB1 and DB2 should return the same list of URLs: one URL for DB1, one URL for DB2 and one URL for the client you attached in step 9.

If you have reached this far, you can now type some database commands directly on the main chat. For example, here is a transcript of me trying to get the value for the key coffee:

Flax [Kira Komarov]: @db_FETCH=coffee
Client: DB answer: NA

which indicates that there is no such key (NA stands here for not available) called coffee in the database. In that case, we add a new key called coffee to the database; here is the transcript:

Flax [Kira Komarov]: @db_REPLACE=coffee:sorry, i don't drink coffee

and now, we wait a little and query the database again to get the value of the key coffee; here is the transcript:

Flax [Kira Komarov]: @db_FETCH=coffee
Client: DB answer: NA

that does not sound good, what happened here? When we tried to retrieve the value for the key coffee in the database, the database client asked a DPD node which did not yet have the new data replicated to it yet. We give it some more time and then ask again:

Flax [Kira Komarov]: @db_FETCH=coffee
Client: DB answer: sorry, i don't drink coffee

there we go.

Server Configuration

In a typical setup, a DPD server will contain four scripts: DATABASE ADDRESS REPLICATOR, DATABASE DATA REPLICATOR, DATABASE KICKSTART MODULE and DATABASE PROCESSOR. The following is a list of possible settings to be found under the configuration header in these scripts:

DATABASE ADDRESS REPLICATOR

The database address replicator is responsible for relaying URLs to other DPDs in the network. It also specifies the password for the network it will join as well as how frequently the URLs in its list will replicate to other DPD nodes.

integer URL_REPLICATION_TIME = 5;
string DATABASE_PASSWORD = "49c11b5dfa51597b3021578810a1ebd2";

where:

  • The URL_REPLICATION_TIME is the time interval in seconds between URL replications. Periodically, based on this time interval, the primitive will try to send all its URLs to all the other primitives it has in its list. It is usually fairly decent to keep this at 60 seconds since it is unlikely that ALL the regions containing these primitives will go down within a 60 second interval.
  • The DATABASE_PASSWORD is a string containing a password that the current DPD node will accept and send when connecting to any other DPD node. This will allow you to isolate your DPD network from other people's networks. Please change this password to something else. I would personally google for an online md5 hash generator and get a password based on that. Regardless what you choose, the password should NOT contain punctuation marks or spaces.

DATABASE DATA REPLICATOR

The database data replicator periodically tries to send the data contained in the current DPD to all other nodes in the DPD network. This is the part of the DPD that will make sure that all the databases (the other DPD nodes in the network) will contain the most up-to-date data. Whenever new data is entered into the database, a timestamp is also inserted which lets the data replicator judge if the new data is more recent than the one already stored in the database. The script takes only one parameter:

integer DATA_REPLICATION_TIME=10;

where:

  • DATA_REPLICATION_TIME represents the interval in seconds between which the current DPD node will attempt to replicate its own data to all the other nodes in the DPD network.

DATABASE PROCESSOR

The database processor is the centrepiece of the DPD system: it responds to all the commands received by the DPD for entering data, retrieving data and replicating data. The script is autonomous and does not take any configurable parameters.

Client Configuration

A typical client would consist in a primitive containing three scripts: DATABASE CLIENT, DATABASE KICKSTART MODULE and DATABASE TEST MODULE. The DATABASE CLIENT is the script which will listen for link messages and relay them to the DPD network. The DATABASE TEST MODULE script is optional and used here just to explain how developers could couple their own scripts to the database client.

DATABASE CLIENT

The database client hooks up to a DPD network using a password and an initial list of DPD kickstart beacons. It is the one responsible for sending data to the DPD network for entering data and retrieving data from the DPD network. The database client also acts as a DPD URL relay by joining the network however, it does not copy the database to itself. Since the database client also acts as a DPD node for URLs, the configuration parameters are somewhat similar to the server's database address replicator:

integer URL_REPLICATION_TIME = 5;
string DATABASE_PASSWORD = "49c11b5dfa51597b3021578810a1ebd2";

where:

  • The URL_REPLICATION_TIME is the time interval in seconds between URL replications. Periodically, based on this time interval, the primitive will try to send all its URLs to all the other primitives it has in its list. It is usually fairly decent to keep this at 60 seconds since it is unlikely that ALL the regions containing these primitives will go down within a 60 second interval.
  • The DATABASE_PASSWORD is a string containing a password that the current DPD node will accept and send when connecting to any other DPD node. This will allow you to isolate your DPD network from other people's networks. Please change this password to something else. I would personally google for an online md5 hash generator and get a password based on that. Regardless what you choose, the password should NOT contain punctuation marks or spaces.

DATABASE TEST MODULE

The database test module can be placed in the same primitive as the database client script. It provides an easy way of testing the DPD network by listening to the owner of the script and relaying all commands to the database client script and from there onto the DPD network.

Server Scripts

In a typical setup, four scripts will be placed in a primitive which will become a server on the DPD network.

DATABASE ADDRESS REPLICATOR

The address replicator is in charge of replicating the URLs between the DPD nodes. It takes two parameters:
URL_REPLICATION_TIME
which represents the interval between which the DPD will try to propagate its address to other DPD nodes and
DATABASE_PASSWORD
which represents the password for the current DPD network.
//////////////////////////////////////////////////////////
// [K] Kira Komarov - 2011, License: GPLv3              //
// Please see: http://www.gnu.org/licenses/gpl.html     //
// for legal details, rights of fair usage and          //
// the disclaimer and warranty conditions.              //
//////////////////////////////////////////////////////////
 
// DPD: DATABASE ADDRESS REPLICATOR
 
//////////////////////////////////////////////////////////
//------------------- CONFIGURATION --------------------//
//////////////////////////////////////////////////////////
 
// Time in seconds between the Distributed Primitive 
// Database (DPD) URL address replication attempts.
// This determines how fast the current prim/DPD will
// attempt to connect to other prims/DPDs in your 
// network. Keep this at a sensible value, way beyond a 
// setting of 1. Do NOT be greedy and go too low on this
// or you will overclock the script till it breaks.
// Sensible values are well beyond 60s and it should be that
// way for slow to moderate storage.
integer URL_REPLICATION_TIME = 5;
// This is your whole Distributed Primitive Database (DPD) 
// network password. Nobody would be able to hook up to your 
// network unless they know this password. Make sure it is 
// something unique. If you want a good password, google for an 
// md5 hash generator and use that. ALL the prims in your 
// Distributed Primitive Database (DPD) network must have the 
// same password that you enter here. It can be anything you 
// choose but WITHOUT SPACES and without PUNCTUATION MARKS/SYMBOLS. 
string DATABASE_PASSWORD = "49c11b5dfa51597b3021578810a1ebd2";
 
//////////////////////////////////////////////////////////
//--------------------- INTERNALS ----------------------//
//////////////////////////////////////////////////////////
 
// pragma inline
integer isValidURL(string URL) {
    if(~llSubStringIndex(URL, "http://") &&
        ~llSubStringIndex(URL, "lindenlab.com") &&
        ~llSubStringIndex(URL, "cap")) return 1;
    return 0;
}
 
integer dbON = 1;
integer menuHandle = 0;
integer registerHandle = 0;
list urlBeacons = [];
integer urlBeaconsNum = 0;
string selfURL = "";
integer gitra;
integer gitrb;
 
default 
{
    state_entry() {
        llReleaseURL(selfURL);
        selfURL = "";
        llRequestURL();
        llMessageLinked(LINK_THIS, 3, "", "@db_FETCHKICKSTART");
        llSetTimerEvent(URL_REPLICATION_TIME);
    }
 
    changed(integer change) {
        if(change & CHANGED_REGION_START || change & CHANGED_REGION) {
            llReleaseURL(selfURL);
            selfURL = "";
            llRequestURL();
            llMessageLinked(LINK_THIS, 3, "", "@db_FETCHKICKSTART");
            llSetTimerEvent(URL_REPLICATION_TIME);
        }
    }
 
    on_rez(integer pin) {
        llReleaseURL(selfURL);
        selfURL = "";
        llRequestURL();
        llMessageLinked(LINK_THIS, 3, "", "@db_FETCHKICKSTART");
        llSetTimerEvent(URL_REPLICATION_TIME);
    }
 
    timer() {
        llSetTimerEvent(0);
        if(gitrb >= llGetListLength(urlBeacons)) {
            ++gitra;
            gitrb = 0;
        }
        if(gitra >= llGetListLength(urlBeacons)) {
            gitra=0;
        }
        if(isValidURL(llList2String(urlBeacons, gitra)) && isValidURL(llList2String(urlBeacons, gitrb)))
            llHTTPRequest(llList2String(urlBeacons, gitra), [HTTP_METHOD, "POST"], llList2String(urlBeacons, gitrb) + " " + DATABASE_PASSWORD);
        ++gitrb;
        llMessageLinked(LINK_THIS, 3, selfURL, "@db_SETKICKSTART=" + llList2CSV(urlBeacons));
        llMessageLinked(LINK_THIS, 1, llList2CSV(urlBeacons), selfURL + "@db_REPLICATE");
        llSetTimerEvent(URL_REPLICATION_TIME);
    }
 
    touch_start(integer total_number) {
        if(llDetectedKey(0) != llGetOwner()) return;
        integer comChannel = ((integer)("0x"+llGetSubString((string)llGetKey(),-8,-1)) & 0x3FFFFFFF) ^ 0xBFFFFFFF;
        menuHandle = llListen(comChannel, "", llGetOwner(), "");
        llDialog(llGetOwner(), "Welcome to the Distributed Primitive Database (DPD) Server:\n\nAdd URL: Use this to add a new DPD.\n\nMy URL: Use this to get the address of this DPD.\n\List URLs: Use this to list all the linked DPDs.\n\nReset: Use this to permanently reset the current DPD since resettting the script will not unlink it from the network.\n\nOn/Off: This will turn the DPD on and off. It will remain connected to the network but will not receive or broadcast messages.\n\nList URLs: Use this to get a list of linked DPDs.", ["[ Add URL ]", "[ My URL ]", "[ List URLs ]", "[ Reset ]", "[ On ]", "[ Off ]"], comChannel);
    }
 
    listen(integer chan,string name,key id,string mes) {
        if(mes == "[ On ]") {
            dbON = 1;
            llOwnerSay("Distributed Primitive Database (DPD) is now: ON");
            jump close_chans;
        }
        if(mes == "[ Off ]") {
            dbON = 0;
            llOwnerSay("Distributed Primitive Database (DPD) is now: OFF");
            jump close_chans;
        }
        if(mes == "[ Reset ]") {
            llSetTimerEvent(0);
            llSetPrimitiveParams([PRIM_TEXT, "", <0,0,0>, 0.0]);
            llResetScript();
            return;
        }
        if(mes == "[ Add URL ]") {
            llOwnerSay("Please paste an URL on channel " + (string)89 + " in order to register it with the system by typing:\n/" + (string)89 + " URL\nWhere URL is the URL of another Distributed Primitive Database (DPD).");
            registerHandle = llListen(89, "", id, "");
            jump close_menu;
        }
        if(mes == "[ My URL ]") {
            if(selfURL == "") {
                llOwnerSay("I don't have an URL registered yet.");
                jump close_chans;
            }
            llOwnerSay("My URL is: " + selfURL);
            jump close_chans;
        }
        if(mes == "[ List URLs ]") {
            if(!llGetListLength(urlBeacons)) {
                llOwnerSay("No beacons registered.");
                jump close_chans;
            }
            integer itra;
            llOwnerSay("----- REGISTERED DATABASES -----");
            for(itra=0; itra<llGetListLength(urlBeacons); ++itra) {
                llOwnerSay(llList2String(urlBeacons, itra));
            }
            llOwnerSay("----- REGISTERED DATABASES -----");
            jump close_chans;
        }
        if(chan != 89) return;
        mes = llList2String(llParseString2List(mes, [" "], [""]), 0);
        if(!isValidURL(mes)) {
            llOwnerSay("Bad formatted URL");
            return;
        }
        if(~llListFindList(urlBeacons, [ mes ])) {
            llOwnerSay("URL already exists.");
            jump close_chans;
        }
        urlBeacons += mes;
        llOwnerSay("URL: " + mes + " has been registered.");
@close_chans;
        llListenRemove(registerHandle);
@close_menu;
        llListenRemove(menuHandle);
    }
 
    link_message(integer sender_num, integer num, string str, key id) {
        if(num != 0) return;
        if(id != "@db_KICKSTART") return;
        list kickstartBeacons = llCSV2List(str);
        integer itra;
        for(itra=0; itra<llGetListLength(kickstartBeacons); ++itra) {
            if(~llListFindList(urlBeacons, (list)llList2String(kickstartBeacons, itra)) || !isValidURL(llList2String(kickstartBeacons, itra))) jump continue;
            urlBeacons += [ llList2String(kickstartBeacons, itra) ];
@continue;
        }
        return;
 
    }
 
    http_request(key id, string method, string body) {
        if(method == URL_REQUEST_GRANTED) {
            selfURL = body;
            urlBeacons += body;
            return;
        }
        if(method == URL_REQUEST_DENIED) {
            llRequestURL();
            return;
        }
        if(method == "POST") {
            llHTTPResponse(id, 200, "OK");
            list postPayload = llParseString2List(body, [" "], [""]);
            if(!isValidURL(llList2String(postPayload, 0))) return;;
            if(llList2String(postPayload, 1) != DATABASE_PASSWORD) return;
            if(~llListFindList(urlBeacons, [ llList2String(postPayload, 0) ])) return;
            urlBeacons += llList2String(postPayload, 0);
            return;
        }
        if(method == "PUT") {
            if(!dbON) return;
            llHTTPResponse(id, 200, "OK");
            list otherURLs = llDeleteSubList(urlBeacons, llListFindList(urlBeacons, [ selfURL ]), llListFindList(urlBeacons, [ selfURL ]));
            if(llGetListLength(otherURLs)) llMessageLinked(LINK_THIS, 1, llList2CSV(otherURLs), body);
            return;
        }
    }
 
    http_response(key id, integer status, list metadata, string body) {
        if(status == 404) {
            string badBeaconKey = llList2String(llParseString2List(body, [": ", "'"], [""]), 1);
            integer itra;
            for(itra=0; itra<llGetListLength(urlBeacons); ++itra) {
                if(~llSubStringIndex(llList2String(urlBeacons, itra), badBeaconKey))
                    urlBeacons = llDeleteSubList((urlBeacons = []) + urlBeacons, itra, itra);
            }
        }
    }
}

DATABASE DATA REPLICATOR

The data replicator, distributes the data in the database to all the nodes in the DPD network. It takes one configurable parameter, the
DATA_REPLICATION_TIME
parameter which represents the interval of seconds between which the current DPD node will attempt to send its data to all other DPD nodes.
//////////////////////////////////////////////////////////
// [K] Kira Komarov - 2011, License: GPLv3              //
// Please see: http://www.gnu.org/licenses/gpl.html     //
// for legal details, rights of fair usage and          //
// the disclaimer and warranty conditions.              //
//////////////////////////////////////////////////////////
 
// DPD: DATABASE DATA REPLICATOR
 
//////////////////////////////////////////////////////////
//------------------- CONFIGURATION --------------------//
//////////////////////////////////////////////////////////
 
// Time in seconds between the Distributed Primitive 
// Database (DPD) data address replication attempts.
// This determines how fast the current prim/DPD will
// attempt to connect to other prims/DPDs in your 
// network and replicate the data it contains. 
// Keep this at a sensible value, way beyond a setting of 
// 1. Do NOT be greedy and go too low on this or you will 
// overclock the script till it breaks. Sensible values 
// are well beyond 60s and it should be that way for slow 
// to moderate storage.
integer DATA_REPLICATION_TIME=5;
 
//////////////////////////////////////////////////////////
//--------------------- INTERNALS ----------------------//
//////////////////////////////////////////////////////////
 
// pragma inline
integer isValidURL(string URL) {
    if(~llSubStringIndex(URL, "http://") &&
        ~llSubStringIndex(URL, "lindenlab.com") &&
        ~llSubStringIndex(URL, "cap")) return 1;
    return 0;
}
 
list beaconQueue = [];
list messageQueue = [];
integer gitra = 0;
 
default
{
    state_entry() {
        llSetTimerEvent(DATA_REPLICATION_TIME);
    }
 
    link_message(integer sender_num, integer num, string str, key id) {
        if(num != 2) return;
        list dbData = llParseString2List(id, ["@"], [""]);
        string reqData = llList2String(dbData, 0);
        if(!isValidURL(reqData)) return;
        dbData = llParseString2List(llList2String(dbData, 1), ["="], [""]);
        if(llList2String(dbData, 0) != "db_COMMIT") return;
        list newBeacons = llCSV2List(str);
        if(!llGetListLength(newBeacons)) return;
        integer itra;
        string cBeacon;
        for(itra=0, cBeacon = llList2String(newBeacons, itra); itra<llGetListLength(newBeacons); cBeacon = llList2String(newBeacons, ++itra)) {
            if(~llListFindList(beaconQueue, [ cBeacon ])) jump next_beacon; 
            if(isValidURL(llList2String(newBeacons, itra))) beaconQueue += [ cBeacon ];
@next_beacon;
        }
        if(~llListFindList(messageQueue, [ (reqData + "@db_REPLACE=" + llList2String(dbData, 1)) ])) return;
        messageQueue += [ (reqData + "@db_REPLACE=" + llList2String(dbData, 1)) ];
    }
 
    timer() {
        llSetTimerEvent(0);
        if(gitra >= llGetListLength(beaconQueue)) {
            messageQueue = llDeleteSubList((messageQueue = []) + messageQueue, 0, 0);
            gitra = 0;
        }
        if(isValidURL(llList2String(beaconQueue, gitra))) {
            llHTTPRequest(llList2String(beaconQueue, gitra), [HTTP_METHOD, "PUT"], llList2String(messageQueue, 0));
            jump next_beacon;
        }
        beaconQueue = llDeleteSubList((beaconQueue = []) + beaconQueue, gitra, gitra);
@next_beacon;
        ++gitra;
        llSetTimerEvent(DATA_REPLICATION_TIME);    
    }
}

DATABASE PROCESSOR

The database processor accepts queries from clients and takes actions on the DPD network.

//////////////////////////////////////////////////////////
// [K] Kira Komarov - 2011, License: GPLv3              //
// Please see: http://www.gnu.org/licenses/gpl.html     //
// for legal details, rights of fair usage and          //
// the disclaimer and warranty conditions.              //
//////////////////////////////////////////////////////////
 
// DPD: DATABASE PROCESSOR
 
//////////////////////////////////////////////////////////
//--------------------- INTERNALS ----------------------//
//////////////////////////////////////////////////////////
 
// pragma inline
integer isValidURL(string URL) {
    if(~llSubStringIndex(URL, "http://") &&
        ~llSubStringIndex(URL, "lindenlab.com") &&
        ~llSubStringIndex(URL, "cap")) return 1;
    return 0;
}
 
list dbKey = [];
list dbValue = [];
list dbStamp = [];
 
default
{
    link_message(integer sender_num, integer num, string str, key id) {
        if(num != 1) return;
        list dbData = llParseString2List(id, ["@", ""], [""]);
        string reqData = llList2String(dbData, 0); 
        if(!isValidURL(reqData)) return;
        dbData = llParseString2List(llList2String(dbData, 1), ["="], [""]);
        list reQ = llParseString2List(llList2String(dbData, 1), [":"], [""]);
 
        if(llList2String(dbData, 0) == "db_REPLICATE") {
            integer itra;
            for(itra=0; itra<llGetListLength(dbKey); ++itra) {
                string timeStamp = llList2String(dbStamp, itra);
                if(timeStamp == "")
                    timeStamp = "0";
                llMessageLinked(LINK_THIS, 2, str, reqData + "@db_COMMIT=" + llList2String(dbKey, itra) + ":" + llList2String(dbValue, itra) + ":" + timeStamp); 
            }
            return;
        }
 
        if(llList2String(dbData, 0) == "db_REPLACE") {
            integer itra;
            for(itra=0; itra<llGetListLength(dbKey); ++itra) {
                if(llList2String(dbKey, itra) == llList2String(reQ, 0) && llGetListLength(reQ) == 3 && llList2Integer(reQ, 2) > llList2Integer(dbStamp, itra)) {
                    dbValue = llListReplaceList((dbValue = []) + dbValue, [ llList2String(reQ, 1) ], itra, itra);
                    dbStamp = llListReplaceList((dbStamp = []) + dbStamp, [ llList2String(reQ, 2) ], itra, itra);
                    return;
                }
                if(llList2String(dbKey, itra) == llList2String(reQ, 0) && llGetListLength(reQ) == 3 && llList2Integer(reQ, 2) <= llList2Integer(dbStamp, itra)) return;
                if(llList2String(dbKey, itra) == llList2String(reQ, 0) && llGetListLength(reQ) == 2) {
                    dbValue = llListReplaceList((dbValue = []) + dbValue, [ llList2String(reQ, 1) ], itra, itra);
                    dbStamp = llListReplaceList((dbStamp = []) + dbStamp, [ llGetUnixTime() ], itra, itra);
                    return;
                }
            }
            dbKey += llList2String(reQ, 0);
            dbValue += llList2String(reQ, 1);
            dbStamp += llGetUnixTime();
            return;
        }
 
        if(llList2String(dbData, 0) == "db_FETCH") {
            integer itra;
            for(itra=0; itra<llGetListLength(dbKey); ++itra) {
                if(llList2String(dbKey, itra) == llList2String(reQ, 0)) {
                    if(!isValidURL(reqData)) return;
                    llHTTPRequest(reqData, [HTTP_METHOD, "PUT"], llList2String(dbValue, itra));
                    return;
                }
            }
            if(!isValidURL(reqData)) return; 
            llHTTPRequest(reqData, [HTTP_METHOD, "PUT"], "N/A");
            return;
        }
    }
}

DATABASE KICKSTART MODULE

This is a script responsible for kickstarting the primitive in the event that the primitive gets disconnected from the network and looses all its linked DPD nodes. It is fully autonomous and does not require any configuration and should be dropped both in the client primitives and the server primitives.

//////////////////////////////////////////////////////////
// [K] Kira Komarov - 2011, License: GPLv3              //
// Please see: http://www.gnu.org/licenses/gpl.html     //
// for legal details, rights of fair usage and          //
// the disclaimer and warranty conditions.              //
//////////////////////////////////////////////////////////
 
// Cross-region intercom: DATABASE KICKSTART MODULE
 
//////////////////////////////////////////////////////////
/////////////// BEGIN IMPORTED BLOCK /////////////////////
 
// This compression algorithm is created by Becky Pippen and is available @
// https://wiki.secondlife.com/wiki/User:Becky_Pippen/Text_Storage
 
//////////////////////////////////////////////////////////
//   Becky Pippen, 2009, contributed to Public Domain   //
//////////////////////////////////////////////////////////
 
string compressAscii(string s){
    integer len = llStringLength(s);
    if ((len % 2)) {
        (s += " ");
        (++len);
    }
    string encodedChars;
    integer i;
    for ((i = 0); (i < len); (i += 2)) {
        integer cInt = llBase64ToInteger(llStringToBase64(llGetSubString(s,i,i)));
        if ((!(cInt & -2147483648))) {
            (cInt = (cInt >> 24));
        }
        else  {
            if (((cInt & -536870912) == -1073741824)) {
                (cInt = (((cInt & 520093696) >> 18) | ((cInt & 4128768) >> 16)));
            }
            else  {
                (cInt = ((((cInt & 251658240) >> 12) | ((cInt & 4128768) >> 10)) | ((cInt & 16128) >> 8)));
            }
        }
        integer _cInt5 = llBase64ToInteger(llStringToBase64(llGetSubString(s,(i + 1),(i + 1))));
        if ((!(_cInt5 & -2147483648))) {
            (_cInt5 = (_cInt5 >> 24));
        }
        else  {
            if (((_cInt5 & -536870912) == -1073741824)) {
                (_cInt5 = (((_cInt5 & 520093696) >> 18) | ((_cInt5 & 4128768) >> 16)));
            }
            else  {
                (_cInt5 = ((((_cInt5 & 251658240) >> 12) | ((_cInt5 & 4128768) >> 10)) | ((_cInt5 & 16128) >> 8)));
            }
        }
        string _ret6;
        integer num = ((cInt << 7) | _cInt5);
        if (((num < 0) || (num >= 32768))) {
            (_ret6 = "�");
            jump _end7;
        }
        (num += 4096);
        integer n = (224 + (num >> 12));
        string hexChars = "0123456789abcdef";
        integer _n4 = (128 + ((num >> 6) & 63));
        string _hexChars5 = "0123456789abcdef";
        integer _n8 = (128 + (num & 63));
        string _hexChars9 = "0123456789abcdef";
        (_ret6 = llUnescapeURL(((((("%" + (llGetSubString(hexChars,(n >> 4),(n >> 4)) + llGetSubString(hexChars,(n & 15),(n & 15)))) + "%") + (llGetSubString(_hexChars5,(_n4 >> 4),(_n4 >> 4)) + llGetSubString(_hexChars5,(_n4 & 15),(_n4 & 15)))) + "%") + (llGetSubString(_hexChars9,(_n8 >> 4),(_n8 >> 4)) + llGetSubString(_hexChars9,(_n8 & 15),(_n8 & 15))))));
        @_end7;
        (encodedChars += _ret6);
    }
    return encodedChars;
}
 
string uncompressAscii(string s){
    string result;
    integer len = llStringLength(s);
    integer i;
    for ((i = 0); (i < len); (++i)) {
        string utf8 = llEscapeURL(llGetSubString(s,i,i));
        integer cInt15 = (((((((integer)("0x" + llGetSubString(utf8,1,2))) & 31) << 12) + ((((integer)("0x" + llGetSubString(utf8,4,5))) & 63) << 6)) + (((integer)("0x" + llGetSubString(utf8,7,8))) & 63)) - 4096);
        integer n = (cInt15 >> 7);
        string hexChars = "0123456789abcdef";
        integer _n7 = (cInt15 & 127);
        string _hexChars8 = "0123456789abcdef";
        (result += llUnescapeURL(((("%" + (llGetSubString(hexChars,(n >> 4),(n >> 4)) + llGetSubString(hexChars,(n & 15),(n & 15)))) + "%") + (llGetSubString(_hexChars8,(_n7 >> 4),(_n7 >> 4)) + llGetSubString(_hexChars8,(_n7 & 15),(_n7 & 15))))));
    }
    return llStringTrim(result,3);
}
 
//////////////// END IMPORTED BLOCK //////////////////////
//////////////////////////////////////////////////////////
 
list getKickstartURLs() {
    list kickStartURLs = llCSV2List(llList2String(llGetPrimitiveParams([PRIM_TEXT]), 0));
    integer itra;
    list kickstartBeacons = [];
    for(itra=0; itra<llGetListLength(kickStartURLs); ++itra) {
        // Decompression by Becky Pippen, 2009
        string newBeacon = uncompressAscii(llList2String(kickStartURLs, itra));
        if(!isValidURL(newBeacon)) jump continue;
        kickstartBeacons += newBeacon;
@continue;
    }
    return kickstartBeacons;
}
 
setKickstartURLs(list beacons) {
    list rndIndices = [];
    list selectedBeacons = [];
    integer itra;
    for(itra=0; itra<llGetListLength(beacons); ++itra) {
        rndIndices += itra;
    }
    while(llGetListLength(rndIndices) && llGetListLength(selectedBeacons) < 6) {
        integer rndPick = llList2Integer(rndIndices, (integer) llFrand(llGetListLength(rndIndices)));
        rndIndices = llDeleteSubList((rndIndices = []) + rndIndices, llListFindList(rndIndices, [ rndPick ]), llListFindList(rndIndices, [ rndPick ]));
        // Compression by Becky Pippen, 2009
        selectedBeacons += compressAscii(llList2String(beacons, rndPick));
    }
    llSetPrimitiveParams([PRIM_TEXT, llList2CSV(selectedBeacons), <0,0,0>, 0.0]);
}
 
// pragma inline
integer isValidURL(string URL) {
    if(~llSubStringIndex(URL, "http://") &&
        ~llSubStringIndex(URL, "lindenlab.com") &&
        ~llSubStringIndex(URL, "cap")) return 1;
    return 0;
}
 
default {
    link_message(integer sender_num, integer num, string str, key id) {
        if(num != 3) return;
        if(id != "@db_FETCHKICKSTART") jump section_kickstart;
        llMessageLinked(LINK_THIS, 0, llList2CSV(getKickstartURLs()), "@db_KICKSTART");
        return;
@section_kickstart;
        list msg = llParseString2List(id, ["="], [""]);
        if(llList2String(msg, 0) != "@db_SETKICKSTART") return;
        setKickstartURLs(llDeleteSubList(llCSV2List(llList2String(msg, 1)), llListFindList(llCSV2List(llList2String(msg, 1)), (list) str), llListFindList(llCSV2List(llList2String(msg, 1)), (list) str)));
    }
}

Client Scripts

In a typical setup, these scripts will be placed in a primitive which will become a client on the DPD network.

DATABASE CLIENT

The database client is the script used to query the database. It takes two configurable parameters:
URL_REPLICATION_TIME
which represents the interval between which the client will try to propagate its address to other DPD nodes and
DATABASE_PASSWORD
which represents the password for the DPD network that the client wants to access.

The database client also participates in the DPD network as a node by replicating its own address to all the other nodes.

//////////////////////////////////////////////////////////
// [K] Kira Komarov - 2011, License: GPLv3              //
// Please see: http://www.gnu.org/licenses/gpl.html     //
// for legal details, rights of fair usage and          //
// the disclaimer and warranty conditions.              //
//////////////////////////////////////////////////////////
 
// DPD: DATABASE CLIENT
 
//////////////////////////////////////////////////////////
//------------------- CONFIGURATION --------------------//
//////////////////////////////////////////////////////////
 
// Time in seconds between the Distributed Primitive 
// Database (DPD) URL address replication attempts.
// This determines how fast the current prim/DPD will
// attempt to connect to other prims/DPDs in your 
// network. Keep this at a sensible value, way beyond a 
// setting of 1. Do NOT be greedy and go too low on this
// or you will overclock the script till it breaks.
// Sensible values are well beyond 60s and it should be that
// way for slow to moderate storage.
integer URL_REPLICATION_TIME = 5;
// This is your whole Distributed Primitive Database (DPD) 
// network password. Nobody would be able to hook up to your 
// network unless they know this password. Make sure it is 
// something unique. If you want a good password, google for an 
// md5 hash generator and use that. ALL the prims in your 
// Distributed Primitive Database (DPD) network must have the 
// same password that you enter here. It can be anything you 
// choose but WITHOUT SPACES and without PUNCTUATION MARKS/SYMBOLS. 
string DATABASE_PASSWORD = "49c11b5dfa51597b3021578810a1ebd2";
 
//////////////////////////////////////////////////////////
//--------------------- INTERNALS ----------------------//
//////////////////////////////////////////////////////////
 
// pragma inline
integer isValidURL(string URL) {
    if(~llSubStringIndex(URL, "http://") &&
        ~llSubStringIndex(URL, "lindenlab.com") &&
        ~llSubStringIndex(URL, "cap")) return 1;
    return 0;
}
 
integer dbON = 1;
integer menuHandle = 0;
integer registerHandle = 0;
list urlBeacons = [];
integer urlBeaconsNum = 0;
string selfURL = "";
integer gitra;
integer gitrb;
 
default 
{
    state_entry() {
        llReleaseURL(selfURL);
        selfURL = "";
        llRequestURL();
        llMessageLinked(LINK_THIS, 3, "", "@db_FETCHKICKSTART");
        llSetTimerEvent(URL_REPLICATION_TIME);
    }
 
    changed(integer change) {
        if(change & CHANGED_REGION_START || change & CHANGED_REGION) {
            llReleaseURL(selfURL);
            selfURL = "";
            llRequestURL();
            llMessageLinked(LINK_THIS, 3, "", "@db_FETCHKICKSTART");
            llSetTimerEvent(URL_REPLICATION_TIME);
        }
    }
 
    on_rez(integer pin) {
        llReleaseURL(selfURL);
        selfURL = "";
        llRequestURL();
        llMessageLinked(LINK_THIS, 3, "", "@db_FETCHKICKSTART");
        llSetTimerEvent(URL_REPLICATION_TIME);
    }
 
    timer() {
        llSetTimerEvent(0);
        if(gitrb >= llGetListLength(urlBeacons)) {
            ++gitra;
            gitrb = 0;
        }
        if(gitra >= llGetListLength(urlBeacons)) {
            gitra=0;
        }
        if(isValidURL(llList2String(urlBeacons, gitra)) && isValidURL(llList2String(urlBeacons, gitrb)))
            llHTTPRequest(llList2String(urlBeacons, gitra), [HTTP_METHOD, "POST"], llList2String(urlBeacons, gitrb) + " " + DATABASE_PASSWORD);
        ++gitrb;
        llMessageLinked(LINK_THIS, 3, selfURL, "@db_SETKICKSTART=" + llList2CSV(urlBeacons));
        llMessageLinked(LINK_THIS, 1, llList2CSV(urlBeacons), selfURL + "@db_REPLICATE");
        llSetTimerEvent(URL_REPLICATION_TIME);
    }
 
    touch_start(integer total_number) {
        if(llDetectedKey(0) != llGetOwner()) return;
        integer comChannel = ((integer)("0x"+llGetSubString((string)llGetKey(),-8,-1)) & 0x3FFFFFFF) ^ 0xBFFFFFFF;
        menuHandle = llListen(comChannel, "", llGetOwner(), "");
        llDialog(llGetOwner(), "Welcome to the Distributed Primitive Database (DPD) Client:\n\nAdd URL: Use this to add a new DPD.\n\nMy URL: Use this to get the address of this DPD.\n\List URLs: Use this to list all the linked DPDs.\n\nReset: Use this to permanently reset the current DPD since resettting the script will not unlink it from the network.\n\nOn/Off: This will turn the DPD on and off. It will remain connected to the network but will not receive or broadcast messages.\n\nList URLs: Use this to get a list of linked DPDs.", ["[ Add URL ]", "[ My URL ]", "[ List URLs ]", "[ Reset ]", "[ On ]", "[ Off ]"], comChannel);
    }
 
    listen(integer chan,string name,key id,string mes) {
        if(mes == "[ On ]") {
            dbON = 1;
            llOwnerSay("Distributed Primitive Database (DPD) is now: ON");
            jump close_chans;
        }
        if(mes == "[ Off ]") {
            dbON = 0;
            llOwnerSay("Distributed Primitive Database (DPD) is now: OFF");
            jump close_chans;
        }
        if(mes == "[ Reset ]") {
            llSetTimerEvent(0);
            llSetPrimitiveParams([PRIM_TEXT, "", <0,0,0>, 0.0]);
            llResetScript();
            return;
        }
        if(mes == "[ Add URL ]") {
            llOwnerSay("Please paste an URL on channel " + (string)89 + " in order to register it with the system by typing:\n/" + (string)89 + " URL\nWhere URL is the URL of another Distributed Primitive Database (DPD).");
            registerHandle = llListen(89, "", id, "");
            jump close_menu;
        }
        if(mes == "[ My URL ]") {
            if(selfURL == "") {
                llOwnerSay("I don't have an URL registered yet.");
                jump close_chans;
            }
            llOwnerSay("My URL is: " + selfURL);
            jump close_chans;
        }
        if(mes == "[ List URLs ]") {
            if(!llGetListLength(urlBeacons)) {
                llOwnerSay("No beacons registered.");
                jump close_chans;
            }
            integer itra;
            llOwnerSay("----- REGISTERED DATABASES -----");
            for(itra=0; itra<llGetListLength(urlBeacons); ++itra) {
                llOwnerSay(llList2String(urlBeacons, itra));
            }
            llOwnerSay("----- REGISTERED DATABASES -----");
            jump close_chans;
        }
        if(chan != 89) return;
        mes = llList2String(llParseString2List(mes, [" "], [""]), 0);
        if(!isValidURL(mes)) {
            llOwnerSay("Bad formatted URL");
            return;
        }
        if(~llListFindList(urlBeacons, [ mes ])) {
            llOwnerSay("URL already exists.");
            jump close_chans;
        }
        urlBeacons += mes;
        llOwnerSay("URL: " + mes + " has been registered.");
@close_chans;
        llListenRemove(registerHandle);
@close_menu;
        llListenRemove(menuHandle);
    }
 
    link_message(integer sender_num, integer num, string str, key id) {
        if(num != 0) return;
        if(id != "@db_KICKSTART") jump client;
        list kickstartBeacons = llCSV2List(str);
        integer itra;
        for(itra=0; itra<llGetListLength(kickstartBeacons); ++itra) {
            if(~llListFindList(urlBeacons, (list)llList2String(kickstartBeacons, itra)) || !isValidURL(llList2String(kickstartBeacons, itra))) jump continue;
            urlBeacons += [ llList2String(kickstartBeacons, itra) ];
@continue;
        }
        return;
@client;
        if(id != DATABASE_PASSWORD) return;
        if(!isValidURL(selfURL)) return;
        list qBeacons = llDeleteSubList(urlBeacons, llListFindList(urlBeacons, (list)selfURL), llListFindList(urlBeacons, (list)selfURL));
        string sendURL = llList2String((qBeacons = [] + qBeacons), (integer)llFrand(llGetListLength(qBeacons)));
        if(!isValidURL(sendURL)) return;
        llHTTPRequest(sendURL, [HTTP_METHOD, "PUT"], selfURL + str);
 
    }
 
    http_request(key id, string method, string body) {
        if(method == URL_REQUEST_GRANTED) {
            selfURL = body;
            urlBeacons += body;
            return;
        }
        if(method == URL_REQUEST_DENIED) {
            llRequestURL();
            return;
        }
        if(method == "POST") {
            list postPayload = llParseString2List(body, [" "], [""]);
            if(!isValidURL(llList2String(postPayload, 0))) return;;
            if(llList2String(postPayload, 1) != DATABASE_PASSWORD) return;
            if(~llListFindList(urlBeacons, (list)llList2String(postPayload, 0))) return;
            urlBeacons += llList2String(postPayload, 0);
            llHTTPResponse(id, 200, "OK");
            return;
        }
        if(method == "PUT") {
            if(~llSubStringIndex(body, "@db_REPLACE") || ~llSubStringIndex(body, "@db_FETCH")) return;
            llMessageLinked(LINK_THIS, 1, body, "db_ANSWER");
            llHTTPResponse(id, 200, "OK");
            return;
        }
    } 
 
    http_response(key id, integer status, list metadata, string body) {
        if(status == 404) {
            string badBeaconKey = llList2String(llParseString2List(body, [": ", "'"], [""]), 1);
            integer itra;
            for(itra=0; itra<llGetListLength(urlBeacons); ++itra) {
                if(~llSubStringIndex(llList2String(urlBeacons, itra), badBeaconKey))
                    urlBeacons = llDeleteSubList((urlBeacons = []) + urlBeacons, itra, itra);
            }
        }
    }
}

DATABASE TEST MODULE

The database test module is a trivial script which may be dropped in a primitive containing the database client so that the owner can type commands on the main chat which will be relayed to the DPD network that the database client is connected to.

//////////////////////////////////////////////////////////
// [K] Kira Komarov - 2011, License: GPLv3              //
// Please see: http://www.gnu.org/licenses/gpl.html     //
// for legal details, rights of fair usage and          //
// the disclaimer and warranty conditions.              //
//////////////////////////////////////////////////////////
 
// DPD: DATABASE TEST MODULE
 
default
{
    state_entry()
    {
        llListen(0, "", llGetOwner(), "");
    }
 
    listen(integer chan,string name,key id,string mes) {
        if(~llSubStringIndex(mes, "@db_FETCH") || ~llSubStringIndex(mes, "@db_REPLACE"))
            llMessageLinked(LINK_THIS, 0, mes, "49c11b5dfa51597b3021578810a1ebd2");
    }
 
    link_message(integer sender_num, integer num, string str, key id) {
        if(id != "db_ANSWER") return;
        llSay(0, "DB3 answer: " + str);
    }
}