SpatialTable: A Distributed Database for Multidimensional Queries

Daniel Speyer Samuel Lee Peiran Hu

dls2192 hsl2113 ph2439

November 30, 2019

Abstract to efficiently query this type of two dimensional

data without the use of workarounds, which can
Both spatial databases and distributed databases only be put in place if the use of the data is
have proved useful for a variety of problems. Fur- predetermined. With this type of problem in
thermore, it is possible, albeit inelegant, to store mind we set out to build a database that was
spatial data in a nonspatial distributed database built from the ground up to easily and efficiently
by means of geohashing and this has proved use- handle this two dimensional data without any
ful as well. We propose a natively spatial dis- additional indexes. Additionally, we believed
tributed database, prototype it, and evaluate its that our design would also extend beyond 2-
performance. While it is not as performant as d to n-dimensions in a efficient manner not
the existing best-of-class solution in the most possible with current databases, and distribute
common case, it is superior in several other cases. to multiple servers. This multidimensionality
Finally, we make the claim that these cases are would allow our database to solve a range of
important, and therefore that natively spatial problems not currently feasible. A discussion
distributed databases are worth pursuing. on some of these applications are included in
section 5. We have created SpatialTable with
the previously stated goals, and we firmly believe
1 Introduction that it provides a solution to the problem of
efficiently making multidimensional queries.
With the explosion of GPS and other location
data available from virtually all internet
connected devices, coupled with incredibly rich
mapping APIs provided by Google and others,
applications of all types have been built that 2 Related Work
use this data for everything from locating the
closest restaurant that caters to your late night 2.1 Distributed Databases
cravings, to easily splitting the cost of a cab
with the closest stranger that happens to be The current standard for distributed databases
going your way. Applications of this sort have begins by having a single primary key (usually
a need to store and quickly query this type of a string) and arbitrary data. The table is
data. However, querying this geospatial data sorted by the key, and chopped into “tablets”
with traditional SQL databases has proved to be of consecutive rows. Which tablet is on which
very inefficient without the use of pre-generated server is stored in a metadata table, which is
indexes. Furthermore, it is very difficult to part of the database and fits this structure nicely.
efficiently distribute these types of databases and This makes it easy to search by key, or for a range
their additional indexes across multiple database of keys, but to search for anything else requires
servers, making scalability a difficult proposition either a separate index or scanning through the
at best. There is no solution currently available entire table.

1
2.2 Spatial Databases a box, it is computationally straightforward to
find the first and last points along the z-curve
There exist many single-node spatial databases, that are inside the box. Then all points inside
mostly based on rtrees,1 quadtrees,2 or similar the box must also have z values between those
structures.3 They are widely used in geographic two points. Not all values between those points
applications, as a single node can hold a fairly must be inside the box, but for most queries,
large amount of data. Still, like all single-node most of them will be. Specifically, the expected
systems, they have a cap on their scalability, and overhead grows logarithmically in the size of
they are not robust against hardware failure. the total database.5 A database can then scan
between the points and filter for being inside the
2.3 GeoHashing box, with good expected (but poor worst-case)
efficiency. This is illustrated in figure 1.
Geohashing allows 2-dimensional data to be
mapped to a one dimensional key with some
locality preserved. Conceptually, a finite fractal
“z” shape is drawn over the space, and every
point in the space is mapped to the closest point 2.4 Hyperspace Hashing
on the fractal. Note that this requires both the
range and precision of the data to be known Hyperspace hashing is another multidimensional
at index-construction time. The distance along technology. First, each key attribute is ‘hashed’
the fractal provides a scalar descriptor of the (the reason for the scare quotes will become
location. This can be used as a primary key in apparent). These hashes are then treated as axes
a classic distributed database.4 of a geometric space, which is statically broken
A query in 2-space can then be translated into hyperrectangles (called “regions”) which are
into an approximate query in z-space. Given statically assigned to servers.6
According to the original HyperDex paper,
the system scales poorly with a high number of
regions. Since regions grow exponentially with
dimension, HyperDex recommends that dimen-
sionality be kept low, and high-dimension tables
be divided into ‘subspaces’ using replication.
The system does offer transactions in this
replication, though one must worry about the
robustness of such a complex system. Also,
it requires all the data to be stored once per
subspace. Furthermore, queries that specify
multiple subspaces only get the benefits of
indexing for one, and must scan and filter for
the others.
While HyperDex does support range queries,
it requires that “objects’ relative orders for the
attribute must be preserved when mapped onto
the hyperspace axis.” Since these attributes are
Figure 1: A 4th degree z curve, showing not being hashed, but the attribute space is still
two queries and their respective linearizations. divided statically, the system is at high risk of
The blue query has only 50% overhead, hot spots unless the data’s distribution is well
whereas the green has over 30x known in advance.

2
3 Design 3.1.1 Tablets
Each tablet has borders (a box) and optionally
Rather than layering on top of a 1-dimensional a list of perpendicular hyperplanes through that
database, our design uses arbitrary-dimensional box which all entries inside the tablet must cross.
tablets as first-class members, giving full For brevity, we refer to these hyperplanes as
flexibility of dimension, range, resolution and “lines”, which they are in the 2-dimensional case.
distribution with no scan-and-filter needed for Since all the lines must be perpendicular, there
standard queries. can be at most as many lines as dimensions. In
this all-lines case, all entries inside the tablet
must contain a single point. The borders of the
box may include infinity or negative infinity. An
3.1 General Design
entry from (1,1) to (2,3) would qualify as inside
of a tablet from (0,0) to (5,3) but would not
Our design is largely inspired by Google’s
qualify as crossing a line at dim0 =2.
Bigtable.7 Like Bigtable, we divide our table
This definition, combined with the splitting
into tablets, keep our metadata in a table like the
algorithm, allows us to maintain a vital
original one, and cap the recursion at two levels.
invariant: for any possible entry, there is always
Also, like bigtable, we use a general distributed
exactly one tablet that should contain it.
filesystem (hdfs) as our backing store.
Our system is intended as a proof-of-concept,
3.1.2 Splitting
not a production-ready system. As such, we
do not support true statelessness as bigtable When a tablet becomes too large, we split it
does, but store data in RAM and write to hdfs along one dimension, producing three tablets:
eventually. As such, we are not robust against ‘less’, ‘crossing’ and ‘more’. The ‘less’ and ‘more’
node failures, but the technologies of write- tablets have smaller borders and the same (if
ahead logging and compactions are already well- any) lines which must be crossed. The ‘crossing’
established, and we would discover nothing new tablet has the same borders, but a new line where
by re-implementing them. the split occurred. Entries are then assigned to
We did consider implementing our system as the new tablets based on how they relate to the
an add-on to HBase (an existing open source split line in that dimension.
distributed database) but the codebase there was
too large and insufficiently documented, so this
was not practical.
Split Line
In a later section, we discuss both what would
be necessary to render our system production-
ready, and what would be necessary to merge it
with an existing database.
Since we want to use our same technology
for metadata, and the natural shape for tablets
is hyperrectangles (henceforth known as “boxes”
for brevity), the keys to our rows are boxes as
well. The data associated with the row is an
arbitrary binary blob. For our tests, we used Figure 2: Splitting a 2d tablet
strings, but a user is welcome to put protobufs
there (as we do for metadata). Supporting Note that the ‘less’ and ‘more’ tablets have
bigtable-like columns would again be a practical never-before-seen borders, and the ‘crossing’
feature of no research significance. tablet has the same borders as the tablet which

3
was just destroyed. This pattern ensures that 3.1.5 Load Balancer
there will never be two tablets in the same table
with the same borders, and therefore that we can The job of the load balancer process is to
safely use the borders as the metadata key. distribute the ”load” of the overall database
Finding the split line is a matter for among the different tablet servers. We have
heuristics. The only constraint is that we cannot defined the load in our case to be the amount
split a tablet in a dimension for which it already of rows contained in each tablet. We follow a
has a must-cross line. Also, it is useless to split simple algorithm to determine which tablets to
a tablet in such a way that all the entries land in move and it is as follows. First, we measure the
the same child tablet. This leaves considerable load in each tablet, but instead of querying each
freedom. Our current heuristic is to take the table and counting the number of rows, we make
bounding box of the data actually there, then use of the fact that each tablet is an rtree and
split it in the widest dimension. To find the point we simply obtain the size attribute for each rtree
along that dimension at which to split, we take which corresponds exactly with the number of
the median after dropping the edges. In practice rows. Next, we determine which servers have
this works fairly well, but it is neither optimal the max and min loads and what is the target
nor robust against pathological data. number of rows we would ideally like to move
to balance the load. It is important to note
however, that we do not move individual rows
3.1.3 Finding a Single Entry from server to server, but instead move whole
To find a single entry, we look in md0 for tablets. This means that even though we have
metadata tablets that contain the box, ignoring a target number of rows we would ideally like to
must-cross lines, then we look in each of them for move, we still need to search for a tablet that
the tablet that contains the box and whose must- best matches the number of rows we would like
cross lines the box does satisfy. This may seem to move. If we find one, then we move it from the
counter-intuitive, but consider a box which in the max loaded server to the min loaded server. If
relevant dimension ranges from 11 to 12, inside no such tablet can be found, then we do nothing,
a tablet from 10 to 20, inside a metadata tablet and wait for the next iteration to hopefully find a
from 0 to 30 crossing 15. This is a perfectly valid better candidate. In our experience, this worked
arrangement, even though the entry could not be decently well, since we are also leveraging the
placed in the metadata tablet. fact that we are splitting the tablets that get too
The number of metadata tablets that must large and thus have mostly evenly sized tablets.
be looked at is one more than the number
of splits that location has gone through. 3.1.6 Locking
Since splits are equivalent to a binary tree,
the expected number of tablets to search is We have a lock on each tablet name, which is
logarithmic in the total number of metadata held whenever the tablet is in use (including
tablets. There is no balancing mechanism, being created or destroyed). We also have
however, and with pathological data it would be a lock on the map from names to tablets
possible to have to search 2/3 of the metadata that the tabletserver maintains, which is held
tablets. whenever creating or destroying tablets. These
are internal locks within the tabletserver that
exist to prevent simulataneous accesses from
3.1.4 Conducting a Query
corrupting the data structures.
Queries may be of the form ‘all boxes within this There is exactly one circumstance in which a
box’ or ‘all boxes intersecting this box’. In either lock is held another is waited on: when splitting
case, we must search all tablets that intersect the a tablet, the original tablet remains locked until
query box. the metadata updates are complete. Since

4
the metadata tree is shallow and acyclic, this select Boost Serialization as a way to write our
cannot produce a cyclic wait nor can a significant data structures to persistent storage, in our case
fraction of threads be blocked at once, unless HDFS. The stated goals of Boost serialization
there are serious delays in an md0 operation. of deconstructing an arbitrary set of C++ data
This provides a tablet-level linearization structures to a sequence of bytes fit our needs
guarantee to the user. Since tablets are not a perfectly, however we quickly realized that the
user-visible structure, this amounts to a row- stated goal was in fact still a goal, even when
level linearization guarantee. dealing with other Boost libraries such as the
Boost Geometry. However, we were able to
3.2 Test Infrastructure workaround this incomplete implementation and
were able to successfully use Boost Serialization
Our infrastructure consists of a four-node cluster to save our data structures to HDFS.
of virtual machines with Ubuntu 14.04 LTS
on KVM. Each VM is itself a datanode on 3.3.4 Protobuf
our distributed file system Hadoop File System
10 for our wire
(HDFS).8 Our code base is written in C++, We use Google Protobuf
using various libraries, and our testing software serialization needs. This is the same library used
for comparisons to other database systems was by HBase and many other distributed systems,
written in Java and Python. so we have a degree of compatibility there.

3.3.5 RPCZ
3.3 Dependencies
LibRPCZ11 is an open-source rpc client/server
3.3.1 HDFS
library using protobufs. It offers clean interfaces
HDFS is a fault tolerant scalable distributed for both synchronous and asynchronous RPCs.
storage component of the Hadoop distributed Unfortunately, it uses a naive round-robin
high performance computing platform, inspired thread scheduler which can cause it to hang if
by the Google File System. We chose this too many RPCs take place before the first one
file system because it met our reliability, completes. Special thanks to Dmitry Odzerikho
scalability, functionality, and performance goals, of that project for helping us to understand and
and has a very well documented installation and work around this bug.
development API in C++.
4 Results
3.3.2 Boost Geometry
4.1 Description of the Benchmarks
Rather than implement our own spatial data
structures in memory, we rely on the Boost We do all our benchmarking using queries,
Geometry9 library’s rtree implementation to because other operations might not be a fair
hold each tablet. test. SpatialTable accepts an insertion as soon as
Inconveniently, this uses
templates for the dimension, requiring the the data is in RAM. Other systems might wait
table dimension to be known at compile [Link] confirmation from the storage layer. That
We can work around this for most purposes would take considerably longer, but not reflect
an advantage of our system.
using function pointers, but It does limit the
dimensionalities we can support. We generate random data using 5 gaussians,
spread uniformly across the range (0, 1) with
σ = 0.1 in all dimensions. A heatmap of the
3.3.3 Boost Serialization
resulting data is shown in figure 4.
Since we were already using Boost Geometry We then generate random center points for
to implement our tablets, it was natural to queries using the same distribution. We select

5
 70 18 30

2 dim, 10k rows

8 dim, 10k rows
2 dim, 100k rows 16
60
25

14

50
12 20

Average Latency (ms)

Average Latency (ms)

Latency (ms)

40
10

15

8
30

6 10

20
rows<100
100<rows<200
4 200<rows<300 250<rows<500
300<rows<400 500<rows<750
5
10 400<rows<500 750<rows<1000
500<rows<750 1000<rows<1250
2
750<rows<1000 1250<rows<1500
1500<rows<1750

0 0 0
0 500 1000 1500 2000 2500 3k 10k 30k 100k 2 4 6 8

Number of Rows Returned Number of Rows in Database Dimension

Figure 3: SpatialTable Performance: (a) Latency vs Rows Returned for individual queries, showing
10k rows of 2 dimensions, 10k rows of 8 dimensions and 100k rows of 2 dimensions; (b) Latency vs
Rows in Database, averaged and blocked by rows returned; (c) Latency vs Dimensions, averaged and
blocked by rows returned

The number of rows returned had a strong

effect on latency, every hundred rows costing an
extra 0.7ms (r2 = 0.54).
The number of dimensions had a weaker
effect, each dimension costing about 1.4ms (r2 ≈
0.8). This is a smaller effect because an extra 200
rows in a response is far more likely than an extra
dimension. Our test at 8 dimensions also showed
a significant number of outliers, which our tests
at 4 and 6 dimensions did not. This might be an
artifact of the testing.
The size of the total database also has a
small effect, with a factor of 10 increase costing
about 5ms. Both the figures for dimension and
Figure 4: A Heatmap of 100k Random Rows database-size effect are highly susceptable to
change in how they are measured. The volume
an expected number of results uniformly from of the query box did not effect latency at all.
the range (500, 2000) and create a (hyper)square All of this is illustrated in figure 3.
query to return this. However, if the query is in a
very low-density region of the map, we limit the 4.3 Comparison to HBase
size of the query so that it does not enter a higher
density region, which produces some queries with HBase is a column-oriented scalable distributed
significantly fewer results. database built on top of Hadoop file system.
Tables in HBase are split into regions served by
different region servers. If the size of a region is
4.2 SpatialTable Performance
beyond the configurable threshold, master server
Drawing from a database of 100 thousand will handle load balancing by shifting the regions
2-dimensional rows using this distribution, from over occupied servers to less busy servers.
SpatialTable has a mean latency of 19ms (σ = Data in each table are sorted by row-key. A
4.8) with a 95th percentile of 28ms and a table consists of multiple Column Families (CF),
maximum (out of our 1000 test queries) of 38ms. and each column belongs to a specific CF. The

6
cross point of row and column is defined as “cell” 4.4 Comparison to MongoDB with
in HBase with its assigned timestamp. These GeoHash
above storage structures make HBase suitable for
MongoDB is a popular open-source distributed
supporting fast random access (read/write) to
database with built in geospatial support via
huge amount of semi-structured and structured
geohashing.15, 16 This makes it a natural choice
data.
for a comparison. We compared MongoDB
However, HBase does not natively support
to SpatialTable using 100k rows and the same
spatial data processing. Row-key in HBase
multigaussian distribution as before.
only supports one-dimentional access to stored
Mongo is approximately 5ms faster than
data. It is possible to layer geohash,12 or
SpatialTable in the median case, but suffers
similar technologies (Hilbert space-filling curve13
from high outliers. At the 95th percentile,
or Grid spatial index method14 ) on top of HBase,
performance is roughly even, and at the 99th
but these are not well-supported.
SpatialTable is almost 20ms faster. This is
Rather than attempt to install additional lay- shown in more detail in figure 6.
ers on top of HBase, we saved geohashing for
MongoDB and used HBase’s native filtering sys- 100
MongoDB
SpatialTable
100%

95%

90%

tem: SingleColumnValueFilter. Our experimen- 80

85%

80%

75%

tal result is presented in figure 5. Here, we com- 70%

Percentage Below Latency

65%

pared the average latency performance of Spa- 60 60%

Latency (ms)

55%

50%

tialTable and HBase based on varied number of 40

45%

40%

35%

rows in database. Naturally, as the growth in the 30%

25%

20%

size of rows, average latency of two databases is

20

15% SpatialTable
MongoDB
10%

increasing. However, HBase suffers severely from 0

0 500 1000 1500 2000 2500 3000
5%

0%
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90
Number of Rows Returned Latency (ms)
the increased database size. While, SpatialTable
has a almost flat performance. It indicates that Figure 6: MongoDB vs SpatialTable Drawn
SpatialTable will far better outperform HBase from 100k Rows (a) Individual Requests by
with even larger database size. Rows Returned; (b) Cumulative Histogram for
Requests Returning 1000-1500 Rows
500
HBase: rows<100
HBase: 100<rows<200 These outliers are exactly what we expect
HBase: 200<rows<350
HBase: 350<rows<500 from geohashing in general. We also expect that
HBase: 500<rows<1000
400 HBase: 1000<rows<1500
HBase: 1500<rows
a distribution with many points concentrated
SpatialTable: rows<100
SpatialTable: 100<rows<200
below the resolution will cause problems. To
SpatialTable: 200<rows<350
SpatialTable: 350<rows<500 trigger this, we reran the test using an power
Average Latency (ms)

SpatialTable: 500<rows<1000
300 SpatialTable: 1000<rows<1500 law distribution. Each co-ordinate’s base 10 log
SpatialTable: 1500<rows
was drawn from a uniform distribution of (-9,9).
We placed the high-density point at the origin to
200 prevent floating point underflow.
With this dataset, we saw a sharp
multimodality of MongoDB latencies (see figure
100 7). The exact nature of this pattern is unclear,
but to a first approximation for 38% of queries
the geohashing system worked well, while for
0 the rest it hit resolution issues. For queries
3k 10k 30k 100k
Number of Rows in Database which returned between 1000 and 1500 rows,
only 21% worked well. The exact numbers are
Figure 5: HBase vs SpatialTable at different not important, as they are an effect of the exact
database sizes, bucketed by rows returned data chosen, but the lesson is clear: geohashing

7
does not cope well with power-law-distributed 5.1 High Resolution
data.
5.1.1 High Resolution Geospatial
400 100%

The resolution of geohashing is sufficient 95%

90%

85%

300
for human-sized objects and gps-resolution 80%

75%

70%

locations. Many “smart city” projects

Percentage Below Latency

65%

60%
Latency (ms)

200 propose higher precision. One approach being 55%

50%

45%

prototyped involves sensors a few centimeters 40%

35%

30%

100
in size embedded in sidewalk tiles recording 25%

20%

microclimate and traffic information.17 A more

15%
SpatialTable
SpatialTable 10% MongoDB
MongoDB
5%

0
0 1000 2000
Rows Returned
ambitious approach is to access all security
3000 4000
0%
0 50 100 150 200 250
Latency (ms)
300 350 400

cameras and merge them into a single image.18

Figure 7: The same graphs as figure 6, but In this case, the resolution would be the pixel’s
with an power law distribution of rows
size from the camera: highly variable but often
submilimeter. Thus far these proposals are
limited to cities, but unifying all data across
large regions, such as the United States, seems
4.5 Theoretical Comparison to Hyper- inevitable.
Dex
HyperDex is an implementation of hyperspace 5.1.2 Power Laws in Abstract Spaces
hashing – the existing technology truly distinct Power law distributions are extremely common
from geohashing. Unfortunately, we were not in nature for nonspatial properties. For example,
able to make it work. Even simple queries websites have power law distributions for both
produced undocumented errors from deep in its traffic and inbound links (or, when they don’t,
internals. it’s close enough to that for our purposes).19 If
We can, however, note that to support range one wanted to keep a database of these and query
queries, hyperspace hashing must use “order it by combinations of those, SpatialTable would
preserving hashes”. Combined with its static be well suited. Geohashing would not be an
assignment of regions, this ensures it will fail option, both because the highest possible traffic
dramatically in the power law distribution case. would not be known in advance, and because
Not only will its hashing contribute nothing, but the most popular websites’ traffic exceeds the
it will store the vast majority of data on a single distinctions of interest among the less popular
node. If this traffic causes that node to fail, the by more than 226 .
database will become essentially unavailable.
5.2 Higher Dimensional
5.2.1 Geospatialtemporal
5 Applications
The simplest reason to expand beyond two
For most practical geospatial tasks, geohashing dimensions is to add time. One might create
is a good solution. It is fast, well-suited to gps a photo collation system that noted both the
data on the surface of the Earth, and robustly location and the date on which the photo was
implemented. Nevertheless, it suffers from three taken. These are, after all, common search
issues: fixed resolution, strict two dimensionality criteria and included by default in most cameras’
and high outliers. We believe there are cases exif data. If the most common search pattern
in which these issues are important enough to included ranges of both place and time, a
justify the use of a SpatialTable-like solution three dimensional database would be the ideal
instead. backend.

8
5.2.2 DNA ngrams on bad-case latencies for any user-facing system.
Intermittent very bad experiences cause more
Bacterial population studies routinely produce user aggravation than consistently mediocre
large amounts of data. A single 16S Ribosomal ones.21 Furthermore, if a handful of users have
sequence is only a few kilobytes, but each very bad experiences, those users are likely to be
bacterium in the sample contains at least one the most vocal, shaping the service’s reputation.
copy of that sequence. The first task in Perhaps it is for these reasons that Amazon
examining such data is often to match each measures all latencies at the 99.9th percentile.22
sequence to similar sequences, either in a
reference database or in the rest of the sample.
Similarity is defined in terms of alignment, which 6 Production Readiness
is very computationally expensive.
One way to make the examinations more 6.1 As a Stand Alone
computationally tractable is to use ngrams. Take
Converting SpatialTable from a proof-of-concept
all possible sequences of a given length (there are
to a deployable system would require several
4n ) and count how many times they appear in
changes, all of which can be copied with minimal
the sequence, including overlapping ones. Then
changes from Bigtable or other existing tablet-
divide the counts by their sum. While there is no
based distributed databases.
theoretical guarantee, empirically similar ngram
signatures predict similar DNA sequences quite
well, even for small n.20 6.1.1 Write ahead Logging
One option would then be to create a 4n − 1 At present, writes to SpatialTable complete
(subtract one because the values sum to 1, so the when the data is in RAM of the relevant
last one provides no information) dimensional tabletserver, and the data will be written
table in SpatialTable and store all the sequences to permanent storage when the tabletserver
in it. Then for each new sequence, consider unloads that tablet. This is clearly not the
only a small box around it to compute precise robustness standard production databases aspire
alignment scores. to.
So long as we maintain the principle that all
5.3 High Reliability data being served is in RAM in rtrees, managing
logging is straightforward. Each write can be
There are circumstances under which the 99th appended to a log as well as updated in RAM.
percentile performance is more important than The log would then be loadable as easily as
the median. For example, consider a control a saved tablet. When actually unloading a
system for a swarm of mobile robots. A general tablet, we could order the log for optimal loading
increase in database latency harms efficiency, but (something we do not currently do).
a single timed out request has the potential to Note that in this case the log might contain
cause physical collisions, damaging the robots or insertion and deletion events for the same rows.
their cargo. These could be removed in periodic compactions,
For a less dramatic example, consider a or we could just wait for unload.
web service with numerous backends. Each
user query results in parallel queries to all
6.1.2 Catching Dropped Tablets
the backends. The user-perceived latency is
determined by the slowest backend. Even if the At present, we assume all tablet management
queries are in sequence, the anomalously slow operations succeed. To be production-ready,
ones will account for a large fraction of the total we must handle scenarios in which the tablets
time spent. loaded, the metadata table and the tablets in
There are also psychological reasons to focus persistent storage disagree.

9
 The tablets in persistent storage must be In the latter case, the tabletservers should check
the ultimate authority. The tablets loaded paxos on startup to find the address of the
can always be lost in a server crash, and the current balancer and then inform it of their
metadata can be reconstructed from the tablets existence. If a tabletserver does not hear from
but not vice verse. the balancer for some time (perhaps ten seconds)
The balancer already makes regular surveys it should recheck paxos to see if the balancer has
of which servers have loaded which tablets, so moved, and introduce itself to the new balancer
it seems well-placed to check for errors. At the if necessary. If it still does not hear, it should
same time that it sends those RPCs, it can also kill itself.
read all metadata tables and check all persistent As a side effect, either the tabletserver locks
storage. in paxos or the introductions to the balancer
If the balancer notices a tablet with no will provide a way to find a list of all active
metadata, it can simply instruct the least loaded tabletservers. This is currently hardcoded. In
server to load that tablet. That tabletserver will addition to being used by the balancer, this list
then create the necessary metadata. can be used to find a server to send table-create
If the balancer notices a tablet which is not requests to.
loaded on the server the metadata says it should
be, it should instruct that server to load it. If 6.1.4 Handling Metadata Timeouts
the server is already in the process of loading,
unloading or splitting the tablet, the lock on the At present, when splitting a tablet, a tabletserver
tablet name will be held and the tabletserver can first performs the split, then removes the old
return an appropriate error code. tablet from the metadata, then inserts the new
If a tabletserver continues to return error ones. These metadata operations involve sending
codes for an excessive time, or times out the RPCs to whichever tabletserver is holding the
load or list request, the balancer can kill it. relevant metadata tablet. If those RPCs fail
The tablets will now be held by a nonexistent or timeout (perhaps because the metadata
tabletserver. tablet was moved at exactly the wrong time)
the tabletserver prints an error message and
If the balancer notices a tablet which is held
continues, causing database corruption. Several
by a nonexistent tabletserver, it can erase that
changes are needed to make this robust.
metadata line and issue a load as if the tablet
First, failures should be retried after
had no metadata.
reasonable backoffs. This still does not
No tabletserver should ever hold a tablet
guarantee success, but it greatly decreases the
which the metadata does not list as belonging to
frequency of failures.
it. If the balancer ever observes this, it should
In order to ensure a valid table can always be
kill the tabletserver and file a bug report.
reconstructed, the order of operations becomes
quite complex:
6.1.3 Discovery and Partition-Resistance
Several steps in the dropped tablet process • Create the new tablets
assume the balancer can always talk to all • Write a note to persistent storage indicat-
servers, and that there is exactly one balancer. ing that the new tablets aren’t real
These invariants must be enforced. The classic • Write the new tablets to persistent storage
solution for this is paxos. Maintaining a
solitary canonical balancer is a straightforward • Atomically replace the note in persistent
application. For ensuring connectivity, either storage with one indicating the old tablet
a system of tabletserver locks can be used as isn’t real
bigtable does or the tabletservers can directly • Remove the tablet from the list of tablets
depend on receiving messages from the balancer. loaded

10
 • Remove the tablet from the metadata table implement different levels of access to allow finer
• Delete the old tablet’s persistent storage granular control of privileges. Again, there are
(this step could be moved to an asynchronous industry standard practices that have benefitted
garbage collector) from years of research and development, that
we would try to leverage in our implementation.
• Add the new tablets to the metadata table The same care would go into preventing denial of
• Add the new tablets to the list of tablets service attacks, and the safe backup of database
loaded data.

This ensures that there is always one correct

table structure which can be reconstructed from 6.2 As Part of an Existing Database
persistent storage, and that the tablets will never Implementing our database on top of an existing
be seen as dropped (unless the server crashes, project would certainly require us to gain
and they actually are). intimate knowledge about the inner workings of
their data structures and methods. It would
6.1.5 Tablet Naming certainly be a considerate time commitment
At present, tablets are addressed using textual that was too long for us to undertake this
names which are themselves human-readable semester, and thus inspired us to develop our
descriptions of their boundaries. This is own solution. However, there are some aspects of
very convenient for debugging, but risks name typical implementations that are well known and
collisions for small tablets. The human- established that we could leverage, particularly
readability is probably worth keeping, but a the writing of the database log and compaction
robust system would need a textualization that to persistent storage. It is definitely feasible
guaranteed different strings for different IEEE- to use for example the way HBase writes their
754 values. log and compacts their data, and have the same
procedures write our data structures and log to
persistent storage. Again, although it seems that
6.1.6 Security
there are certain aspects of currently available
In terms of security there are a few threats database systems that we can leverage, overall
that are most common to the integrity of our design is sufficiently different that would
the database, in no particular order they hinder a total integration without a substantial
include, excessive privilege abuse, privilege rewrite of our codebase.
elevation, denial of service, weak authentication,
backup data exposure, and weak database 6.2.1 Per-Table Metadata
communication protocol vulnerabilities.23 These
have all been previously addressed in commercial A bigger difference between SpatialTable and tra-
database and we can certainly learn from their ditional distributed databases is that SpatialTable
implementations. has separate metadata tables for each data table.
In the case of authentication, we believe This is necessary because tables can be of varying
we can make use of industry standard methods dimensions. Even tables of the same dimension
to hash passwords in a secure store, and also cannot easily share metadata tables as there is
implement strict password requirements. To no spatial equivalent to prepending table names
prevent excessive privilege abuse, we would have to keys.
to make sure that our database can operate Finding relevant tablets is a spatial-specific
in a way that our users receive only enough task that would simply involve spatial code,
privilege to access only what they must. This but every other task that uses metadata (such
means that we will not default to giving all as iterating over all tablets to ensure they are
users complete access to all database data, and loaded) would need to be altered to support both

11
traditional and per-table metadata. 2 Finkeland Bentley. Quad Trees: A Data
Also, a traditional distributed database Structure for Retrieval on Composite Keys.
only needs a single md0 tablet whose location Acta Informatica. 1974
bootstraps all access. A single hostport can 3 [Link] of Spatial Data
be stored in paxos or other expensive storage
Structures. Addison Wesley. 1990
without trouble. Permitting this for every table
is probably acceptable, but the costs should be 4 Morton.A computer Oriented Geodetic Data
monitored. If they prove too high, another layer Base; and a New Technique in File
of indirection is needed. This comes at a latency Sequencing. IBM Technical Reports. 1966
cost, but perhaps caching can alleviate it.
5 Tropfand Herzog Multidimensional Range
Search in Dynamically Balanced Trees.
6.2.2 Protocol Angewandte Informatik. 1981
The protocols spoken by existing distributed 6 Escriva,Wong and Sirer. HyperDex: A
database are not designed for spatial data. All Distributed, Searchable Key-Value Store.
bitstring primary keys will need to be replaced ACM SigCOMM. 2012
with lists of pairs. If the protocol was designed
7 Changs et al. Bigtable: a distributed storage
for extensibility, this may be possible with
minimal disruption. system for structured data. OSDI. 2006
8 Shvachko,et al. The Hadoop Distributed File
System Proceedings of the 2010 IEE 26th
7 Roles Symposium on Mass Storage Systems and
Technologies (MSST) 2010
Peiran Hu was responsible for testing stuff
about HBase and MongoDB. She figured out 9 Schiling,
Boris The Boost C++ Libraries
the storage mechanisms and query methods in XML Press 2011
HBase and MongoDB. She wrote the test cases 10 Google.
about 2-D spatial data queries for Starbuck [Link]
shops through Java Client API for both of the 2015
databases. 11 Samet, Nadav
Sam Lee built all of the infrastructure needed [Link] 2015
to implement our database, and also installed
12 Dimiduk, Nick, et al. HBase in action.
all of the databases used for comparison. He
also wrote the basic HDFS access code, tablet Shelter Island: Manning. 2013
balancer process, and some testing Python code. 13 Li,Qingcheng, et al. Optimizational Method
Daniel Speyer did the basic design; wrote
of HBase Multi-dimensional Data Query
the framework, fundamental operations, tablet-
Based on Hilbert Space-Filling Curve. P2P,
finding code, splitter and client; and devised the
Parallel, Grid, Cloud and Internet
test datasets. He also provided general support
Computing (3PGCIC), 2014 Ninth
to the other team members in their tasks.
International Conference on. IEEE. 2014.
14 Zhang, Ningyu, et al. HBaseSpatial: A
References Scalable Spatial Data Storage Based on
HBase. Trust, Security and Privacy in
1 Guttman. R-Trees: A Dynamic Index Computing and Communications
Structure for Spatial Searching. ACM (TrustCom), 2014 IEEE 13th International
SigMOD. 1984 Conference on. IEEE. 2014.

12
15 MongoDB Manual: 2d Index Internals. 19 Penneck et al. Winners don’t take all:
[Link] Characterizing the competition for links on
geospatial-indexes/ 2015 the web. PNAS. 2001
20 Sun et al. ESPRIT: estimating species
16 MongoDB Manual: GeoSpatial Tutorials
richness using large collections of 16S rRNA
[Link]
pyrosequences. Nucleic Acids Research. 2009
tutorial/build-a-2d-index/ 2015
21 Dornic, Stan, and Tarja Laaksonen.
17 [Link] “Connected Boulevard”: Taking Continuous noise, intermittent noise, and
the Fast Lane to the Internet of Everything. annoyance. Perceptual and Motor Skills 68.1
Cisco Press Release. [Link] 1989
com/government/intelligent- 22 DeCandia
communities-global-blog-series-the- et al. Dynamo: Amazons Highly
connected-boulevard-taking-the-fast- Available Key-value Store. Symposium on
lane-to-the-internet-of-everything Operating Systems Principles. 2007
2013 23 Horwath, Jim Setting Up a Database Security
Logging and Monitoring Program SANS
18 Calavia et al. A Semantic Autonomous Video Institute Reading Room 2012
Surveillance System for Dense Camera
Networks in Smart Cities. Sensors. 2012

13