SPDY Performance on Mobile Networks

SPDY is a replacement for HTTP, designed to speed up transfers of web pages, by eliminating much of the overhead associated with HTTP. SPDY supports out-of-order responses, header compression, server-side push, and other optimizations that give it an edge over HTTP when it comes to speed. SPDY is gaining a great deal of traction -- it has been implemented in Chrome, Firefox, and Amazon Silk, been deployed widely by Google, and there is now SPDY support for Apache through the mod_spdy module.

SPDY's design should help performance on mobile networks, which experience high round-trip times and typically lower throughput than to wired networks. SPDY includes several features that should improve web page download speeds on mobile networks, including:

1. Header compression, which eliminates redundant data for HTTP headers;
2. Out-of-order request processing, avoiding head-of-line blocking for HTTP responses;
3. Use of a single TCP connection for multiple requests, eliminating overheads for TCP connection establishment (which can be high on mobile networks).

We wondered what the performance of SPDY would be compared to HTTP for popular websites, using a real phone (a Samsung Galaxy Nexus running Android), a modern, SPDY-enabled browser (Chrome for Android), and a variety of pages from real websites (77 pages across 31 popular domains).

The net result is that using SPDY results in a mean page load time improvement of 23% across these sites, compared to HTTP. This is equivalent to a speedup of 1.3x for SPDY over HTTP. Much more work can be done to improve SPDY performance on 3G and 4G cellular networks, but this is a promising start. More details below.

Methodology

Our goal was to evaluate how SPDY performs on a real browser on a real phone when fetching popular websites. The challenge was in mitigating the variability across experiments.

• Phone and browser configuration: We ran our experiments on Chrome for Android, because it has an up-to-date draft 2 implementation of SPDY and is the only mobile browser we know of that supports SPDY. We ran the browser on Android 4.0 (Ice Cream Sandwich) on a Samsung Galaxy Nexus phone. We used Chrome's remote debugging interface with a custom client that starts up the browser on the phone, clears its cache and other state, initiates a web page load, and receives the Chrome developer tools messages to determine the page load times and other performance metrics.
• Pages measured: We selected 77 URLs from a selection of 31 popular websites, to ensure a broad cross-section of both front pages and article pages across different types of sites. To ensure that the phone retrieved the same content each time it fetched a particular URL, we captured and replayed this content using the Web Page Replaytool, which eliminates the nondeterminism associated with replaying web page loads. All content was cached on our Web Page Replay server.
• Server configuration: We needed a Web server implementation that supports SPDY. The best SPDY implementation available to us is Googles internal web server, called the Google Front End (or GFE). The GFE was configured to proxy to the Web Page Replay server hosting the actual site content. The GFE and the Web Page Replay servers ran on separate Linux desktop machines on the same LAN segment. All Web page contents were stored on the Web Page Replay servers local disk to eliminate additional sources of latency. The phones' /etc/hosts file was modified to return the GFE machine's IP address for all domain lookups, essentially isolating the phone and the desktop from the Internet. As a result, our measurements do not include realistic DNS lookup times.
• Consistent network conditions: In prior experiments, we found page load times to be highly variable over real 3G and 4G cellular networks, making it hard to draw conclusions without running hundreds of experiments per site in order to estimate the statistical distribution. To reduce this variability, the phone was tethered to the desktop machine hosting the server using a USB connection, and traffic shaping was applied to the tethered connection using Dummynet. We emulated a 3G network with uplink bandwidth of 1 Mbps, downlink bandwidth of 2 Mbps, and a round-trip delay of 150 ms. These values were chosen as representative of cellular network performance in the United States. Note that packet loss was not included in the traffic shaping parameters, since cellular networks hide packet loss at the PHY layer, and our previous experiments have shown a TCP-level packet loss of less than 1% over typical cellular networks.
• Data collection: For each page load, we recorded the page load time reported by the browser, as well as the detailed trace of Chrome remote debugging messages which were used to reconstruct a load time waterfall for each page, including the time to load each individual resource on the page, as well as timings for TCP connections, DNS lookups, and redirects. In addition, tcpdump was run on the phone to capture a trace of all network packets sent and received during the web page load.

Below is a diagram of our testbed.

We ran two sets of experiments:

1. SPDY: Fetch the 77 URLs through the GFE using SPDY.
2. HTTP: Fetch the 77 URLs through the GFE using HTTP.

Note that SPDY will use a single SSL connection per domain, whereas HTTP will open multiple parallel connections for fetching resources from the server. The SPDY measurements presented here include the SSL connection setup overhead.

Table 1: Domains included in the Web page measurements

bbc.co.uk	bloomberg.com	cricinfo.com
decor8blog.com	digg.com	droid-life.com
economictimes.com	espncricinfo.com	flickr.com
greenweddingshoes.com	huffingtonpost.com	ibtimes.com
imgur.com	michaeleisen.org	microsoft.com
nlm.nih.gov	qq.com	quickmeme.com
reddit.com	reuters.com	sciencemag.org
seattletimes.nwsource.com	slashdot.org	sohu.com
theboombox.com	timesofindia.com	wikipedia.org
windowsteamblog.com	wired.com	yomiuri.co.jp

Results

Figure 2 shows the page load time for each of the 77 URLs using both HTTP and SPDY. As the figure shows, in all but one case, SPDY is faster than HTTP, with an average page load time reduction of 23% across all pages. For one of the URLs (an article from huffingtonpost.com), the page loaded 6% slower on SPDY than HTTP.

Figure 2: Comparison of SPDY vs. HTTP page load times

Figure 3 shows the average SPDY load time reduction for each of the measured pages. The load time reduction is calculated as (SPDY load time) / (HTTP load time) for each page.

Figure 3: Page load time reduction for SPDY for each of the measured sites

In order to take a closer look at SPDY's performance, Figures 4 and 5 show the waterfall chart for SPDY and HTTP (respectively) for one of the pages.

Figure 4: SPDY load waterfall for http://en.m.wikipedia.org/wiki/Harvard_University

Figure 5: HTTP load waterfall for http://en.m.wikipedia.org/wiki/Harvard_University

The waterfall diagrams clearly show SPDY's main advantage over HTTP: The use of out-of-order responses. In the SPDY case, the browser opens a number of SPDY streams (over the same TCP connection) to fetch the various resources on the page, whereas in HTTP, each of the resources are fetched across several (6 in this case) TCP connections, with each connection handling requests in a FIFO fashion. Note that there are several 404 Not Found errors in both traces, owing to the Web Page Replay setup not caching all of the resources on the page.

Conclusions

SPDY shows promise to improve the performance of web page load times over mobile networks. Of course, its necessary to look across many more sites and a wider range of network conditions, but in this controlled experiment we find that SPDY yields a mean page load time reduction of 23% over HTTP, yielding a speedup of 1.3x. Website operators should consider using SPDY to speed up access to their sites from mobile devices.

F1: A Distributed SQL Database That Scales

F1: A Distributed SQL Database That Scales - Google, 2013

• [Paper] [Mirror]

F1 is a SQL database built on top of Spanner.

• Originally built to replace Google’s MySQL cluster used for AdWords
  • My friend Jason Lucas of OrlyAtomics said it best, “NoSQL: Whom Shall We Screw?”
  • If we have a distributed database, we often choose to relax consistency making things very difficult for the software engineers
  • There’s enough to deal with ensure business logic is correct for AdWords then to have engineers write logic to deal with eventual consistency
  • While F1 does increase the latency for many reads and writes, they’ve done a lot of work to alleviate the issues including an ORM that tries to guide engineers to write good client code
• Architecture
  • Spanner on top of Colossus provides the KV store with distributed transactions
  • F1 servers are “mostly stateless”
    • Generally placed in the same DC as Spanner servers
    • Client can usually communicate with any F1 server
    • During a pessimistic transaction (i.e. the client holds locks) it must stay in communication with the same server
  • F1 Slave Pool
    • For execution of parts of distributed queries
    • Shared
  • Since F1 servers do not store data, adding and removing nodes does not require re-balancing of data
    • Interesting idea that allows you to scale computation separately from storage or access
  • Spanner
    • Directory, a ‘database’ name in the conventional sense
    • Each directory is made up of several fragments
    • A collections of fragments in a directory is called a group
      • Groups are replicated across DCs.
      • Groups use Paxos
      • One replica is deemed the Paxos leader for the group
      • Some groups have readonly replicas that do not vote
    • Pessimistic transactions use 2PL
      • Transactions within a group do not require 2PC (only one leader)
      • Transactions across groups require 2PC (on top of Paxos) and are slower
        • Does not work well with 100s of participants
    • Spanner allows for reading a snapshot of the data without locks
      • Spanner has a grantee that there are no current or future transactions that will commit before theglobal safe timestamp
      • Typically this timestamp is 5-10 seconds behind
• Data Model
  • Schema
    • F1 has a hierarchical schema
    • Logical child tables can be interleaved with a physical parent table
    • The child table must have a FK to it’s parent as part of it’s PK
    • A row in the physical table is deemed the root row
      • All data associated with the row in the parent and child tables are clustered together (generally the same Spanner server)
    • This means that joins between a parent and child table can be satisfied with fast range queries on the same server
    • Updates tend to be only on one or few servers requiring little coordination
  • Protocol Buffers are first class citizens and are exposed in the SQL
  • Indexes
    • Transactional and fully consistent
    • Stored in separate tables in Spanner
      • I like this idea, reuse all the infra we already have!
    • Keys comprise of the index key and the PK of the index table
    • Index keys can be extracted from Protos
    • Local indexes have the root row’s PK as part of their prefix
      • Local indexes can be stored as child tables
    • Global indexes are not keyed by a root row (for example an index on Keyword)
      • Usually large with high update rates
      • Stored on multiple spanner servers
      • To update a single row in the index required only adding one participant to 2PC
        • However, I note that if this is a search index and you are adding a document with N words you could see that the number of participants count increase quite a bit
      • The authors encourage users to use small transactions when updating data in a global index
    • Schema Changes
      • This seems like a heroic effort to me
      • In AdWords, many schema changes happen each day!
      • They can’t just lock a table
      • Their scheme is non-blocking
      • Their algorithm is summarized as follows:
        • Only two schemas are active in the cluster at a time
        • Each server is using either the previous or new schema
          • Leases are used to enforce this
        • Each schema change is divided into a series of phases where each consecutive pair is compatible
        • They may use MapReduce to backfill index entries for a new index
        • This index may be invisible until the index is current
• Transactions
  • An F1 transaction us a set of reads followed by an optional single write
  • Types:
    • Snapshot Transactions
      • Read only
      • Uses a fixed timestamp
      • Reads are repeatable
      • By default it uses the global safe timestamp
      • Can use a client specified timestamp
        • This could require many RPCs
      • This is the default type
    • Pessimistic Transactions
      • These are Spanner transactions
      • Acquires locks (2PL)
      • Locks can either be shared or exclusive
    • Optimistic Transactions
      • Read phase followed by a write phase
      • Read phase holds no locks
      • Read phase can take arbitrarily long
      • In the read phase, F1 returns the last modified timestamp with each row
      • The timestamp for a row is stored in a hidden lock column
      • The client library returns these timestamps to the F1 server
      • If the timestamps differ from the current timestamps at the time of commit the transaction is aborted
      • Benefits
        • Bad clients don’t hold any locks so they don’t hurt the rest of the system
        • They can be easily retried on the F1 server to hide transient errors
        • Transaction state is kept on the client, therefore the client can failover to another F1 server if it chooses
        • Clients can read values outside of a transaction and then write at some later time (great for MapReduce)
      • Drawbacks
        • Insertion Phantoms
          • Insertions can happen without being noticed because there is no timestamp at read time that can be passed to the client
          • They use parent-table locks to avoid phantoms
        • Like many optimistic locking strategies, throughput goes down if there is high contention
    • Locking Granularity
      • Row level locking by default
      • Additional lock columns can be added in the schema to cover a subset of the columns in the row
• Change History
  • While the Java libraries for accessing data in the AdWords MySQL cluster added change logs, Python scripts and other clients didn’t always do proper change logs
  • Change history is a “first-class feature”
  • Each F1 transaction creates one or more ChangeBatch protos that contain the PK and before and after values of each column
  • These records are added as children of their root table
    • Thus their are close to the data being tracked requiring no extra participants in the transaction
  • The records have pointers to eachother if multiple rows were included in the same transaction
  • F1 publishes the change history for others to subscribe to
  • The authors discuss a cool use of this feature, a cache
    • An in-memory cache includes the timestamp of the data it caches
    • When a user commits data to F1 and subsequently reads from the cache (perhaps to show the data on the next page), it can request the data from the cache with the commit timestamp
    • If the cache is out of data, it can read the change history to catch up
    • Less intensive then a full refresh and is a simple cache invalidation method
• Client Design
  • ORM
    • I believe this section illustrates that thinking hard about good abstractions can really improve performance
    • In a way typical of many published Google projects, the authors limit the API to provided better guarantees
  • NoSQL Interface
    • ORM uses the NoSQL interface under the hood
    • Clients can use it directly
    • Can sometimes be easier to read and write data
  • SQL Interface
    • An extended SQL
• Query Processing
  • Can either be centrally excited for low-latency or distributed for high parallelism
  • To maximize pipelining, query plan operators stream results to the next operators as soon as possible
  • Distributed Queries
    • Always uses snapshot transactions
    • Good for OLAP style
    • Tasks are spread across the slave pool
    • All the data is remote (on Spanner/Colossus)
    • Network latency is mitigated by pipelining and batching
    • In this case, since there are many discs involved in the read, it’s fine to ignore conventional DBMS wisdom and issues many data accesses at the same time
      • They see near-linear speedup with this approach (until the storage is overloaded)
      • Their lookup join requests 50 MB of data and then looks up all the keys in the inner table simultaneously!
        • WOAH!
    • Their network fabric is such that servers on different racks can communicate at full link speed
    • Hash Join Partitioning
      • Repartitions both inputs with a hash function on the join key
      • Each worker deals with a shard of the data
      • The query planner determines the smallest input and each shard loads it into an in-memory hash table
    • Distributed Aggregation
      • Buffer as much as possible in small buffers and then repartition the data by group key for final aggregation
    • There is no checkpointing which means that if any component fails the entire query could fail
  • Partitioned Consumers
    • The client might not be able to receive data at the rate F1 can produce it
    • Multiple clients can consume the result stream in parallel
    • Often used in MapReduce jobs
    • If a client doesn’t keep up, this can cause the F1 slaves to block, slowing other transactions
    • Eventually they are thinking of implementing a disk based buffer
  • You can join on fields in a Protocol Buffer as part of the SQL
• Misc
  • MapReduce clients are allowed to communicate directly with Spanner for performance
  • Read only replicas allow for OLAP load to be on separate servers
  • 3-way replication is not enough
    • If one replica is offline, F1 can not handle another failure as Paxos requires a majority of replicas
    • In practice they use 5 replicas (two east coast, two west coast and one centrally)

Other notes about database

• Bigtable: A Distributed Storage System for Structured Data [Google, 2006]
• Cassandra: A Decentralized Structured Storage System [Facebook, 2009]
• Dynamo: Amazon's Highly Available Key-value Store [Amazon, 2007]
• Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing [Google, 2014]
• PNUTS: Yahoo!'s Hosted Data Serving Platform [Yahoo!, 2008]
• Spanner: Google's Globally-Distributed Database [Google, 2012]
• TAO: Facebook’s Distributed Data Store for the Social Graph [Facebook, 2013]

F1: A Distributed SQL Database That Scales

Databases are a lot like programming languages: there’s a great variety to chose from, they have wildly different programming and query interfaces, and there’s a wide gap in available features. And just as choosing the right programming language for a project can have a significant impact on the outcome of success, so does choosing the right database. So what really matters when choosing a database?

Absolute Raw Speed Does Not Matter

Surprisingly, raw speed of the database does not matter in 99% of cases. From an application perspective, database queries tend to have a bimodal distribution: they’re either good enough or too slow to complete. Usually, it’s more important to keep good enough performance while scaling concurrent access with growing dataset sizes over getting the best possible performance out of a narrow set of queries.

For example, look at Google’s F1 distributed database. The commit latency on F1 is quite high (at 50-100ms). Read latency takes a hit as well, with simple reads in the 5-10ms range. Compared with a single instance MySQL, the numbers are quite high. However, Google’s core ad business runs on F1, at a scale of 10s of TBs across 1000s of machines. Ability to keep good enough performance by scaling the system matters more.

Expressiveness of the Query Language Matters

Chocolate or vanilla? Beer or wine? SQL or NoSQL? All questions which inspire endless debates. However, most of the debates on database query languages tend to miss the mark. It’s possible to have a weak SQL implementation (e.g. lack of subqueries, limited aggregate functionality, poor planner, etc.) and a relatively feature rich non-SQL implementation (RethinkDB supports join operations between documents while MongoDB does not).

Consider some of the following criteria when evaluating a database query language:

1. How many network trips do I need to make to the database for typical query patterns?
2. For operations that require looking at a great deal of records, does the database support necessary aggregate/window/analytics functions without having to transfer the burden onto the application? casino online Does it support concepts such as temporary tables when more complex/multi-stage evaluations are necessary?
3. Can I leverage existing queries/work without having to duplicate queries (e.g. SQL views)?

While there’s nothing inherent to SQL that makes it a better fit, it turns out that most database implementations which rely on it offer a much richer and powerful interface than those that don’t. Perhaps in a few years some of the alternatives will catch up, but we are not there yet.

Transactions Matter

And finally, a subject of many flame wars: transactions. It’s true that many folks have built large scale systems which do not rely on the database’s support (or lack of) transactions. However, such systems typically move the well understood properties of transactions as offered by their databases into an ad-hoc implementation within the application itself. Which generally leads to a more complex and fragile codebase.

The Google Spanner designers said the following about transactions:

“We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions. Running two-phase commit over Paxos mitigates the availability problems.”

Tracks social interactions Google

/**
 * Namespace.
 * @type {Object}.
 */
var _ga = _ga || {};


/**
 * Ensure global _gaq Google Analytics queue has been initialized.
 * @type {Array}
 */
var _gaq = _gaq || [];


/**
 * Tracks social interactions by iterating through each tracker object
 * of the page, and calling the _trackSocial method. This function
 * should be pushed onto the _gaq queue. For details on parameters see
 * http://code.google.com/apis/analytics/docs/gaJS/gaJSApiSocialTracking.html
 * @param {string} network The network on which the action occurs.
 * @param {string} socialAction The type of action that happens.
 * @param {string} opt_target Optional text value that indicates the
 *     subject of the action.
 * @param {string} opt_pagePath Optional page (by path, not full URL)
 *     from which the action occurred.
 * @return a function that iterates over each tracker object
 *    and calls the _trackSocial method.
 * @private
 */
_ga.getSocialActionTrackers_ = function(
    network, socialAction, opt_target, opt_pagePath) {
  return function() {
    var trackers = _gat._getTrackers();
    for (var i = 0, tracker; tracker = trackers[i]; i++) {
      tracker._trackSocial(network, socialAction, opt_target, opt_pagePath);
    }
  };
};


/**
 * Tracks Facebook likes, unlikes and sends by suscribing to the Facebook
 * JSAPI event model. Note: This will not track facebook buttons using the
 * iframe method.
 * @param {string} opt_pagePath An optional URL to associate the social
 *     tracking with a particular page.
 */
_ga.trackFacebook = function(opt_pagePath) {
  try {
    if (FB && FB.Event && FB.Event.subscribe) {
      FB.Event.subscribe('edge.create', function(opt_target) {
        _gaq.push(_ga.getSocialActionTrackers_('facebook', 'like',
            opt_target, opt_pagePath));
      });
      FB.Event.subscribe('edge.remove', function(opt_target) {
        _gaq.push(_ga.getSocialActionTrackers_('facebook', 'unlike',
            opt_target, opt_pagePath));
      });
      FB.Event.subscribe('message.send', function(opt_target) {
        _gaq.push(_ga.getSocialActionTrackers_('facebook', 'send',
            opt_target, opt_pagePath));
      });
 FB.Event.subscribe('comment.create', function(targetUrl) {
_gaq.push(_ga.getSocialActionTrackers_('facebook', 'comment',
            opt_target, opt_pagePath));
 });
 FB.Event.subscribe('comment.remove', function(targetUrl) {
 _gaq.push(_ga.getSocialActionTrackers_('facebook', 'uncomment',
            opt_target, opt_pagePath));
});
    }
  } catch (e) {}
};


/**
 * Handles tracking for Twitter click and tweet Intent Events which occur
 * everytime a user Tweets using a Tweet Button, clicks a Tweet Button, or
 * clicks a Tweet Count. This method should be binded to Twitter click and
 * tweet events and used as a callback function.
 * Details here: http://dev.twitter.com/docs/intents/events
 * @param {object} intent_event An object representing the Twitter Intent Event
 *     passed from the Tweet Button.
 * @param {string} opt_pagePath An optional URL to associate the social
 *     tracking with a particular page.
 * @private
 */
_ga.trackTwitterHandler_ = function(intent_event, opt_pagePath) {
  var opt_target; //Default value is undefined
  if (intent_event && intent_event.type == 'tweet' ||
          intent_event.type == 'click') {
    if (intent_event.target.nodeName == 'IFRAME') {
      opt_target = _ga.extractParamFromUri_(intent_event.target.src, 'url');
    }
    var socialAction = intent_event.type + ((intent_event.type == 'click') ?
        '-' + intent_event.region : ''); //append the type of click to action
    _gaq.push(_ga.getSocialActionTrackers_('twitter', socialAction, opt_target,
        opt_pagePath));
  }
};

/**
 * Binds Twitter Intent Events to a callback function that will handle
 * the social tracking for Google Analytics. This function should be called
 * once the Twitter widget.js file is loaded and ready.
 * @param {string} opt_pagePath An optional URL to associate the social
 *     tracking with a particular page.
 */
_ga.trackTwitter = function(opt_pagePath) {
  intent_handler = function(intent_event) {
    _ga.trackTwitterHandler_(intent_event, opt_pagePath);
  };

  //bind twitter Click and Tweet events to Twitter tracking handler
  twttr.events.bind('click', intent_handler);
  twttr.events.bind('tweet', intent_handler);
};


/**
 * Extracts a query parameter value from a URI.
 * @param {string} uri The URI from which to extract the parameter.
 * @param {string} paramName The name of the query paramater to extract.
 * @return {string} The un-encoded value of the query paramater. undefined
 *     if there is no URI parameter.
 * @private
 */
_ga.extractParamFromUri_ = function(uri, paramName) {
  if (!uri) {
    return;
  }
  var regex = new RegExp('[\\?&#]' + paramName + '=([^&#]*)');
  var params = regex.exec(uri);
  if (params != null) {
    return unescape(params[1]);
  }
  return;
};

AutoSuggester Js for without jquery

if (typeof(bsn) == "undefined")
_b = bsn = {};


if (typeof(_b.Autosuggest) == "undefined")
_b.Autosuggest = {};
else
consol.log("Autosuggest is already set!");

_b.AutoSuggest = function (id, param)
{
// no DOM - give up!
//
if (!document.getElementById)
return 0;


// get field via DOM
//
this.fld = _b.DOM.gE(id);

if (!this.fld)
return 0;




// init variables
//
this.sInp = "";
this.nInpC = 0;
this.aSug = [];
this.iHigh = 0;



// parameters object
//
this.oP = param ? param : {};

// defaults
//
var k, def = {minchars:1, meth:"get", varname:"input", className:"autosuggest", timeout:2500, delay:500, offsety:-5, shownoresults: true, noresults: "No results!", maxheight: 250, cache: true, maxentries: 25};
for (k in def)
{
if (typeof(this.oP[k]) != typeof(def[k]))
this.oP[k] = def[k];
}


// set keyup handler for field
// and prevent autocomplete from client
//
var p = this;

// NOTE: not using addEventListener because UpArrow fired twice in Safari
//_b.DOM.addEvent( this.fld, 'keyup', function(ev){ return pointer.onKeyPress(ev); } );

this.fld.onkeypress = function(ev){ return p.onKeyPress(ev); };
this.fld.onkeyup = function(ev){ return p.onKeyUp(ev); };

this.fld.setAttribute("autocomplete","off");
};

_b.AutoSuggest.prototype.onKeyPress = function(ev)
{

var key = (window.event) ? window.event.keyCode : ev.keyCode;



// set responses to keydown events in the field
// this allows the user to use the arrow keys to scroll through the results
// ESCAPE clears the list
// TAB sets the current highlighted value
//
var RETURN = 13;
var TAB = 9;
var ESC = 27;

var bubble = 1;

switch(key)
{
case RETURN:
this.setHighlightedValue();
bubble = 0;
break;

case ESC:
this.clearSuggestions();
break;
}

return bubble;
};



_b.AutoSuggest.prototype.onKeyUp = function(ev)
{
var key = (window.event) ? window.event.keyCode : ev.keyCode;



// set responses to keydown events in the field
// this allows the user to use the arrow keys to scroll through the results
// ESCAPE clears the list
// TAB sets the current highlighted value
//

var ARRUP = 38;
var ARRDN = 40;

var bubble = 1;

switch(key)
{


case ARRUP:
this.changeHighlight(key);
bubble = 0;
break;


case ARRDN:
this.changeHighlight(key);
bubble = 0;
break;


default:
this.getSuggestions(this.fld.value);
}

return bubble;


};


_b.AutoSuggest.prototype.getSuggestions = function (val)
{

// if input stays the same, do nothing
//
if (val == this.sInp)
return 0;


// kill list
//
_b.DOM.remE(this.idAs);


this.sInp = val;


// input length is less than the min required to trigger a request
// do nothing
//
if (val.length < this.oP.minchars)
{
this.aSug = [];
this.nInpC = val.length;
return 0;
}




var ol = this.nInpC; // old length
this.nInpC = val.length ? val.length : 0;



// if caching enabled, and user is typing (ie. length of input is increasing)
// filter results out of aSuggestions from last request
//
var l = this.aSug.length;
if (this.nInpC > ol && l && l<this.oP.maxentries && this.oP.cache)
{
var arr = [];
for (var i=0;i<l;i++)
{
if (this.aSug[i].value.substr(0,val.length).toLowerCase() == val.toLowerCase())
arr.push( this.aSug[i] );
}
this.aSug = arr;

this.createList(this.aSug);



return false;
}
else
// do new request
//
{
var pointer = this;
var input = this.sInp;
clearTimeout(this.ajID);
this.ajID = setTimeout( function() { pointer.doAjaxRequest(input) }, this.oP.delay );
}

return false;
};


_b.AutoSuggest.prototype.doAjaxRequest = function (input)
{
// check that saved input is still the value of the field
//
if (input != this.fld.value)
return false;


var pointer = this;


// create ajax request
//
if (typeof(this.oP.script) == "function")
var url = this.oP.script(encodeURIComponent(this.sInp));
else
var url = this.oP.script+this.oP.varname+"="+encodeURIComponent(this.sInp);

if (!url)
return false;

var meth = this.oP.meth;
var input = this.sInp;

var onSuccessFunc = function (req) { pointer.setSuggestions(req, input) };
var onErrorFunc = function (status) { consol.log("AJAX error: "+status); };

var myAjax = new _b.Ajax();
myAjax.makeRequest( url, meth, onSuccessFunc, onErrorFunc );
};

_b.AutoSuggest.prototype.setSuggestions = function (req, input)
{
// if field input no longer matches what was passed to the request
// don't show the suggestions
//
if (input != this.fld.value)
return false;


this.aSug = [];


if (this.oP.json)
{
var jsondata = eval('(' + req.responseText + ')');

for (var i=0;i<jsondata.results.length;i++)
{
this.aSug.push(  { 'id':jsondata.results[i].id, 'value':jsondata.results[i].value, 'info':jsondata.results[i].info, 'url':jsondata.results[i].url }  );
}
}
else
{

var xml = req.responseXML;

// traverse xml
//
var results = xml.getElementsByTagName('results')[0].childNodes;

for (var i=0;i<results.length;i++)
{
if (results[i].hasChildNodes())
this.aSug.push(  { 'id':results[i].getAttribute('id'), 'value':results[i].childNodes[0].nodeValue, 'info':results[i].getAttribute('info') }  );
}

}

this.idAs = "as_"+this.fld.id;


this.createList(this.aSug);

};


_b.AutoSuggest.prototype.createList = function(arr)
{
var pointer = this;




// get rid of old list
// and clear the list removal timeout
//
_b.DOM.remE(this.idAs);
this.killTimeout();


// if no results, and shownoresults is false, do nothing
//

if (arr.length == 0 && !this.oP.shownoresults)
return false;


// create holding div
//
var div = _b.DOM.cE("div", {id:this.idAs, className:this.oP.className});

var hcorner = _b.DOM.cE("div", {className:"as_corner"});
var hbar = _b.DOM.cE("div", {className:"as_bar"});
var header = _b.DOM.cE("div", {className:"as_header"});
header.appendChild(hcorner);
header.appendChild(hbar);
div.appendChild(header);




// create and populate ul
//
var ul = _b.DOM.cE("ul", {id:"as_ul"});



// loop throught arr of suggestions
// creating an LI element for each suggestion
//
for (var i=0;i<arr.length;i++)
{
// format output with the input enclosed in a EM element
// (as HTML, not DOM)
//
var val = arr[i].value;
var st = val.toLowerCase().indexOf( this.sInp.toLowerCase() );
var output = val.substring(0,st) + "<em>" + val.substring(st, st+this.sInp.length) + "</em>" + val.substring(st+this.sInp.length);


var span = _b.DOM.cE("span", {}, output, true);
if (arr[i].info != "")
{
var br = _b.DOM.cE("br", {});
span.appendChild(br);
var small = _b.DOM.cE("small", {}, arr[i].info);
span.appendChild(small);
}

var a = _b.DOM.cE("a", { href:"javascript:void();" });

var tl = _b.DOM.cE("span", {className:"tl"}, " ");
var tr = _b.DOM.cE("span", {className:"tr"}, " ");
a.appendChild(tl);
a.appendChild(tr);

a.appendChild(span);

a.name = i+1;
a.onclick = function () { pointer.setHighlightedValue(); return false; };
a.onmouseover = function () { pointer.setHighlight(this.name); };

var li = _b.DOM.cE(  "li", {}, a  );

ul.appendChild( li );
}


// no results
//
if (arr.length == 0 && this.oP.shownoresults)
{
var li = _b.DOM.cE(  "li", {className:"as_warning"}, this.oP.noresults  );
ul.appendChild( li );
}


div.appendChild( ul );


var fcorner = _b.DOM.cE("div", {className:"as_corner"});
var fbar = _b.DOM.cE("div", {className:"as_bar"});
var footer = _b.DOM.cE("div", {className:"as_footer"});
footer.appendChild(fcorner);
footer.appendChild(fbar);
div.appendChild(footer);



// get position of target textfield
// position holding div below it
// set width of holding div to width of field
//
var pos = _b.DOM.getPos(this.fld);

div.style.left = pos.x + "px";
div.style.top = ( pos.y + this.fld.offsetHeight + this.oP.offsety ) + 5 + "px";
div.style.width = this.fld.offsetWidth + "px";



// set mouseover functions for div
// when mouse pointer leaves div, set a timeout to remove the list after an interval
// when mouse enters div, kill the timeout so the list won't be removed
//
div.onmouseover = function(){ pointer.killTimeout() };
div.onmouseout = function(){ pointer.resetTimeout() };


// add DIV to document
//
document.getElementsByTagName("body")[0].appendChild(div);



// currently no item is highlighted
//
this.iHigh = 0;


// remove list after an interval
//
//var pointer = this;
//this.toID = setTimeout(function () { pointer.clearSuggestions() }, this.oP.timeout);
};


_b.AutoSuggest.prototype.changeHighlight = function(key)
{
var list = _b.DOM.gE("as_ul");
if (!list)
return false;

var n;

if (key == 40)
n = this.iHigh + 1;
else if (key == 38)
n = this.iHigh - 1;


if (n > list.childNodes.length)
n = list.childNodes.length;
if (n < 1)
n = 1;


this.setHighlight(n);
};



_b.AutoSuggest.prototype.setHighlight = function(n)
{
var list = _b.DOM.gE("as_ul");
if (!list)
return false;

if (this.iHigh > 0)
this.clearHighlight();

this.iHigh = Number(n);

list.childNodes[this.iHigh-1].className = "as_highlight";


this.killTimeout();
};


_b.AutoSuggest.prototype.clearHighlight = function()
{
var list = _b.DOM.gE("as_ul");
if (!list)
return false;

if (this.iHigh > 0)
{
list.childNodes[this.iHigh-1].className = "";
this.iHigh = 0;
}
};


_b.AutoSuggest.prototype.setHighlightedValue = function ()
{
if (this.iHigh)
{
var lastSearchTerm = this.fld.value;
this.sInp = this.fld.value = this.aSug[ this.iHigh-1 ].value;

// move cursor to end of input (safari)
//
this.fld.focus();
if (this.fld.selectionStart)
this.fld.setSelectionRange(this.sInp.length, this.sInp.length);


this.clearSuggestions();

// pass selected object to callback function, if exists
//
if (typeof(this.oP.callback) == "function")
this.oP.callback( this.aSug[this.iHigh-1],  lastSearchTerm);
}
};


_b.AutoSuggest.prototype.killTimeout = function()
{
clearTimeout(this.toID);
};

_b.AutoSuggest.prototype.resetTimeout = function()
{
clearTimeout(this.toID);
var pointer = this;
this.toID = setTimeout(function () { pointer.clearSuggestions() }, 1000);
};







_b.AutoSuggest.prototype.clearSuggestions = function ()
{

this.killTimeout();

var ele = _b.DOM.gE(this.idAs);
var pointer = this;
if (ele)
{
var fade = new _b.Fader(ele,1,0,250,function () { _b.DOM.remE(pointer.idAs) });
}
};

// AJAX PROTOTYPE _____________________________________________


if (typeof(_b.Ajax) == "undefined")
_b.Ajax = {};



_b.Ajax = function ()
{
this.req = {};
this.isIE = false;
};



_b.Ajax.prototype.makeRequest = function (url, meth, onComp, onErr)
{

if (meth != "POST")
meth = "GET";

this.onComplete = onComp;
this.onError = onErr;

var pointer = this;

// branch for native XMLHttpRequest object
if (window.XMLHttpRequest)
{
this.req = new XMLHttpRequest();
this.req.onreadystatechange = function () { pointer.processReqChange() };
this.req.open("GET", url, true); //
this.req.send(null);
// branch for IE/Windows ActiveX version
}
else if (window.ActiveXObject)
{
this.req = new ActiveXObject("Microsoft.XMLHTTP");
if (this.req)
{
this.req.onreadystatechange = function () { pointer.processReqChange() };
this.req.open(meth, url, true);
this.req.send();
}
}
};


_b.Ajax.prototype.processReqChange = function()
{

// only if req shows "loaded"
if (this.req.readyState == 4) {
// only if "OK"
if (this.req.status == 200)
{
this.onComplete( this.req );
} else {
this.onError( this.req.status );
}
}
};


// DOM PROTOTYPE _____________________________________________


if (typeof(_b.DOM) == "undefined")
_b.DOM = {};



/* create element */
_b.DOM.cE = function ( type, attr, cont, html )
{
var ne = document.createElement( type );
if (!ne)
return 0;

for (var a in attr)
ne[a] = attr[a];

var t = typeof(cont);

if (t == "string" && !html)
ne.appendChild( document.createTextNode(cont) );
else if (t == "string" && html)
ne.innerHTML = cont;
else if (t == "object")
ne.appendChild( cont );

return ne;
};



/* get element */
_b.DOM.gE = function ( e )
{
var t=typeof(e);
if (t == "undefined")
return 0;
else if (t == "string")
{
var re = document.getElementById( e );
if (!re)
return 0;
else if (typeof(re.appendChild) != "undefined" )
return re;
else
return 0;
}
else if (typeof(e.appendChild) != "undefined")
return e;
else
return 0;
};



/* remove element */
_b.DOM.remE = function ( ele )
{
var e = this.gE(ele);

if (!e)
return 0;
else if (e.parentNode.removeChild(e))
return true;
else
return 0;
};



/* get position */
_b.DOM.getPos = function ( e )
{
var e = this.gE(e);

var obj = e;

var curleft = 0;
if (obj.offsetParent)
{
while (obj.offsetParent)
{
curleft += obj.offsetLeft;
obj = obj.offsetParent;
}
}
else if (obj.x)
curleft += obj.x;

var obj = e;

var curtop = 0;
if (obj.offsetParent)
{
while (obj.offsetParent)
{
curtop += obj.offsetTop;
obj = obj.offsetParent;
}
}
else if (obj.y)
curtop += obj.y;

return {x:curleft, y:curtop};
};


// FADER PROTOTYPE _____________________________________________



if (typeof(_b.Fader) == "undefined")
_b.Fader = {};





_b.Fader = function (ele, from, to, fadetime, callback)
{
if (!ele)
return 0;

this.e = ele;

this.from = from;
this.to = to;

this.cb = callback;

this.nDur = fadetime;

this.nInt = 50;
this.nTime = 0;

var p = this;
this.nID = setInterval(function() { p._fade() }, this.nInt);
};




_b.Fader.prototype._fade = function()
{
this.nTime += this.nInt;

var ieop = Math.round( this._tween(this.nTime, this.from, this.to, this.nDur) * 100 );
var op = ieop / 100;

if (this.e.filters) // internet explorer
{
try
{
this.e.filters.item("DXImageTransform.Microsoft.Alpha").opacity = ieop;
} catch (e) {
// If it is not set initially, the browser will throw an error.  This will set it if it is not set yet.
this.e.style.filter = 'progid:DXImageTransform.Microsoft.Alpha(opacity='+ieop+')';
}
}
else // other browsers
{
this.e.style.opacity = op;
}


if (this.nTime == this.nDur)
{
clearInterval( this.nID );
if (this.cb != undefined)
this.cb();
}
};



_b.Fader.prototype._tween = function(t,b,c,d)
{
return b + ( (c-b) * (t/d) );
};