Referential Consistency in a Distributed NoSQL Database (part 2)

December 13, 2011 2 comments

We continue the discussion from last time. The first step in our solution is remembering that we’ve already designed our objects so they can be handed forward to a web-based front end through a RESTful API. Specifically, we already needed our objects to be serializable in either XML or JSON format. The Spring webapp framework makes this simple, so long as we’ve marked up our classes using JAXB annotations. That is, the class definitions actually look like

@XmlRootElement
@XmlAccessorType(XmlAccessType.NONE)
public class Thing {
  @XmlElement
  private String name;
  @XmlElement
  private String hairColor;

  public Thing() {}

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public String getHairColor() {
    return hairColor;
  }

  public void setHairColor(String hairColor) {
    this.hairColor = hairColor;
  }
}

public class Hat {
  @XmlElement
  private String name;
  @XmlElement
  private String brimColor;
  @XmlElement
  private String otherColor;
  @XmlElement
  private int layers;

  public Hat() {}

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public String getBrimColor() {
    return brimColor;
  }

  public void setBrimColor(String brimColor) {
    this.brimColor = brimColor;
  }

  public String getOtherColor() {
    return otherColor;
  }

  public void setOtherColor(String otherColor) {
    this.otherColor = otherColor;
  }

  public int getLayers() {
    return layers;
  }

  public void setLayers(int layers) {
    this.layers = layers;
  }
}

public class CatWithHatAndThings {
  @XmlElement
  private String name;
  @XmlElement
  private Hat hat;
  @XmlElement
  private List<Thing> things;

  public CatWithHatAndThings() {}

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public Hat getHat() {
    return hat;
  }

  public void setHat(Hat hat) {
    this.hat = hat;
  }

  public List<Thing> getThings() {
    return things;
  }

  public void setThings(List<Thing> things) {
    this.things = things;
  }
}

These annotations tell us how to translate these objects into and out of either XML or JSON format. Since we’ve already got these markups, we may as well make use of them!

Our database table consists of a sparse list of keys and values; keys are made of two strings — the “row” and the “column” — while values are byte arrays that can hold arbitrary data. We will use the key to hold enough information to identify a domain object, and we will place the JSON-serialized form of an object into the corresponding value.

Specifically, we will use the class of the object as the row, so all the objects of the same type are held together. For the column, we want to give each object a unique identifier. To do this, we create an abstract parent:

@XmlRootElement
@XmlAccessorType(XmlAccessType.NONE)
public abstract class DomainObject {
  @XmlElement
  private String id;

  public DomainObject() {
    id = UUID.randomUUID().toString();
  }

  public String getId() {
    return id;
  }

  public void setId(String id) {
    this id = id;
  }
}

and make each of our classes extend it. Alternatively, we could make DomainObject an interface and insist that a getter/setter pair be implemented, which would usually consist of defining a local field in each class. This would be useful if, say, some of our classes already extended other classes.

Next, we define an abstract generic class to handle common reading and writing code:

public abstract class DomainObjectTable<T extends DomainObject> extends DatabaseTable {
  private static final String TABLE_NAME = "objects_table";
  private final ObjectMapper mapper;
  private final String rowName;
  private final Class<T> objectClass;

  public DomainObjectTable(String rowName,
                           Class<T> objectClass,
                           DatabaseConnection conn) {
    super(conn);
    this.rowName = rowName;
    this.objectClass = objectClass;

    mapper = new ObjectMapper();
    AnnotationIntrospector ai = new JaxbAnnotationIntrospector();
    mapper.getSerializationConfig().withAnnotationIntrospector(ai);
    mapper.getDeserializationConfig().withAnnotationIntrospector(ai);
  }

  public void put(T object) throws Exception {
    BatchWriter writer = getNewBatchWriter();
    Mutation mutex = new Mutation(rowName);
    mutex.put(object.getId(),mapper.writeValueAsString(object).getBytes());
    writer.addMutations(Arrays.asList(mutex));
    writer.close();
  }

  public T get(String id) throws Exception {
    List<T> maybeT = get(Arrays.asList(id));
    if (maybeT.isEmpty()) {
      return null;
    }
    return maybeT.get(0);
  }

  public List<T> get(List<String> ids) throws Exception {
    BatchScanner scanner = getNewBatchScanner();
    scanner.setRanges(Arrays.asList(new Range(rowName)));
    for (String id : ids) {
      scanner.fetchColumn(id);
    }
    List<T> fetched = new ArrayList<T>();
    for (Map.Entry<Key, byte[]> entry : scanner) {
      fetched.add(mapper.readValue(new String(entry.getValue()),objectClass));
    }
  }
}

For any of our domain object classes we can create a corresponding table object, which is sort of like a view on the (shared) underlying table. For instance, we can define

public class ThingTable extends DomainObjectTable<Thing> {
  public ThingTable(DatabaseConnection conn) {
    super("Thing", Thing.class, conn);
  }
}

public class HatTable extends DomainObjectTable<Hat> {
  public HatTable(DatabaseConnection conn) {
    super("Hat", Hat.class, conn);
  }
}

public class CatWithHatAndThingsTable extends DomainObjectTable<CatWithHatAndThings> {
  public CatWithHatAndThingsTable(DatabaseConnection conn) {
    super("CatWithHatAndThings", CatWithHatAndThings.class, conn);
  }
}

We provide methods for accessing either a single object or a list of objects in a single database access. At this point, the database interface is pretty much complete, but there’s a problem which we will get into next time.

Categories: Uncategorized

Referential Consistency in a Distributed NoSQL Database (part 1)

December 10, 2011 1 comment

I found a solution to a sort of interesting problem recently. First, some background.

We’ve been using path of the Spring framework to manage certain parts of our problem domain. Specifically, we’ve had some XML files defining beans, like so:

<beans>
  <bean id="thing1" class="Thing">
    <property name="name" value="thing1"/>
    <property name="hairColor" value="blue"/>
  </bean>
  <bean id="thing1" class="Thing">
    <property name="name" value="thing1"/>
    <property name="hairColor" value="blue"/>
  </bean>
  <bean id="thing2" class="Thing">
    <property name="name" value="thing2"/>
    <property name="hairColor" value="blue"/>
  </bean>
  <bean id="cat-hat" class="Hat">
    <property name="name" value="cat-hat"/>
    <property name="brimColor" value="white"/>
    <property name="otherColor" value="red"/>
    <property name="layers" value="5"/>
  </bean>
  <bean id="cat" class="CatWithHatAndThings">
    <property name="name" value="cat"/>
    <property name="hat" ref="cat-hat"/>
    <property name="things">
      <list>
        <ref>thing1</ref>
        <ref>thing2</ref>
      </list>
    </property>
  </bean>
</beans>

Now, many of you may be familiar with Spring’s beans, but this is really just a whole bunch of reflective shorthand. The most straightforward explanation is that we have a bunch of Plain Old Java Objects defined something like this:

public class Thing {
  private String name;
  private String hairColor;

  public Thing() {}

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public String getHairColor() {
    return hairColor;
  }

  public void setHairColor(String hairColor) {
    this.hairColor = hairColor;
  }
}

public class Hat {
  private String name;
  private String brimColor;
  private String otherColor;
  private int layers;

  public Hat() {}

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public String getBrimColor() {
    return brimColor;
  }

  public void setBrimColor(String brimColor) {
    this.brimColor = brimColor;
  }

  public String getOtherColor() {
    return otherColor;
  }

  public void setOtherColor(String otherColor) {
    this.otherColor = otherColor;
  }

  public int getLayers() {
    return layers;
  }

  public void setLayers(int layers) {
    this.layers = layers;
  }
}

public class CatWithHatAndThings {
  private String name;
  private Hat hat;
  private List<Thing> things;

  public CatWithHatAndThings() {}

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public Hat getHat() {
    return hat;
  }

  public void setHat(Hat hat) {
    this.hat = hat;
  }

  public List<Thing> getThings() {
    return things;
  }

  public void setThings(List<Thing> things) {
    this.things = things;
  }
}

When we start our program, we make an ApplicationContext, telling it where the XML files are. For each <bean> tag, Spring calls the public, no-argument constructor for the appropriate class, then calls public setter methods to fill in the specified properties with the specified values. Some are set by literal values, while others are set by reference to other named beans.

Now, transporting all these XML files can get annoying. If we want multiple developers to work on the project, they each need their copy. Worse, if some of the beans are written dynamically using earlier steps then a developer must rerun all those steps before they can work on later steps, or the references will be undefined. This is true even if they don’t really care about that particular reference.

But as it happens, we have a NoSQL database lying around. We want to put our domain objects in there instead of in Spring beans. It’s not Bigtable, but it’s a similar key-value store, so if thinking of Bigtable helps that wouldn’t be too far off.

Anyway, if this were a SQL database like PostgreSQL, we could use an Object-Relational Mapping framework like Hibernate. But since it isn’t we need another way around it. We’ll start in on one solution next time.

Categories: Uncategorized

A Shell-Scripted Hadoop Utility

September 15, 2011 2 comments

Wow, it’s been a while; there’s a lot I can’t or don’t want to write about in my programming career, and once I leave work I don’t do a whole lot of really new programming.

But anyway, I should start this with a bit of a confession: I never really got all that great with the standard Unix tools. And by this I don’t mean ls or cp or all those usual filesystem navigation essentials. I mean the heart of the shell scripting family: grep, sed, and awk. So I’ve been trying to use them where I can to make my life easier. And here’s a neat little application that other people might find useful as well.

I’ve been working with Hadoop lately. It’s basically a framework for distributed computing; we submit jobs to the server — the jobtracker — which then parcels its tasks out to various computers to do the work. We can throw hundreds of jobs at the jobtracker at once, for it to work through as it gets around to them.

But sometimes things go wrong. If a job needs to be cancelled, here’s what we have to say:

$ hadoop job -kill job_201109142032_0023

Here, the job is identified as job_201109132032_0023. The big number tells us that the jobtracker daemon was started on September 13, 2011, at 8:32 PM (machine time), and the small number tells us we’re talking about the 23rd job submitted to it.

Well, this is all well and good, but what if I’d submitted a thousand jobs to the jobtracker before realizing I’d done something horribly, horribly wrong (again)? I don’t want to have to type in all those lines; I’ll write a script to cancel all the jobs for me!

First, I need a way of getting all the jobs that are running in the first place. Luckily, Hadoop gives us a way of finding this out:

$ hadoop job -list | head
38 jobs currently running
JobId	State	StartTime	UserName	Priority	SchedulingInfo
job_201109132032_0017	1	1316025713074	hdfs	NORMAL	NA
job_201109132032_0018	1	1316025712977	hdfs	NORMAL	NA
job_201109132032_0019	1	1316025712975	hdfs	NORMAL	NA
job_201109132032_0021	1	1316025712975	hdfs	NORMAL	NA
job_201109132032_0023	1	1316025713098	hdfs	NORMAL	NA
job_201109132032_0026	1	1316025712976	hdfs	NORMAL	NA
job_201109132032_0027	1	1316025713088	hdfs	NORMAL	NA
job_201109132032_0028	1	1316025713096	hdfs	NORMAL	NA

We can see that some of the jobs have already finished, accounting for gaps in the list. Most of this information isn’t relevant to our purposes, so let’s get scripting.

An easy answer might look like

for jobid in `hadoop job -list | awk '{print $1}'`
do
  hadoop job -kill ${jobid}
done

And this will indeed work. But it’s not very modular, and doesn’t adapt well to other things I might want to do. Instead, I’m going to write it like this:

jobtrackerid=`hadoop job -list | awk '{print $1}' | awk -F_ '{print $2}' | sort -nr | head -n1`
for jobid in `hadoop job -list | awk '{print $1}' | awk -F_ '{print $3}'`
do
  hadoop job -kill job_${jobtrackerid}_${jobid}
done

The first line grabs the ID of the jobtracker for me. In fact, I could do well to pull this out into its own script and invoke it from here, and anywhere else I need this number. Notice that it actually only gets the highest jobtracker identifier available, but — as far as I can tell — we aren’t about to find jobs running from more than one jobtracker. If one goes down or is taken down, all of its jobs go too.

Now the clause in the for loop doesn’t get the whole job identifier, but only the index for each job. This could be useful if I wanted to see if some jobs aren’t getting started, or are finishing inordinately quickly; they’d show up as gaps in the list.

One last tweak: let’s say there are a bunch of us, all using the cluster. My colleague Omar started a whole bunch of jobs running before going home, but I’m seeing them throw exceptions; I can tell there’s a problem but I can’t fix his jobs myself. Still, there’s no sense in tying up all of those resources for his jobs that are doomed to fail, but I don’t want to kill all my jobs in the process. Luckily, I can use the script killalljobsforuser

jobtrackerid=`hadoop job -list | awk '{print $1}' | awk -F_ '{print $2}' | sort -nr | head -n1`
for jobid in `hadoop job -list | awk '$4 == "'$1'" {print $1}' | awk -F_ '{print $3}'`
do
  hadoop job -kill job_${jobtrackerid}_${jobid}
done

Now if I say killalljobsforuser littleman it will only kill those jobs listing Omar as the user who requested them.

Categories: Shell Games

Sieving

October 25, 2010 2 comments

Jeez, it’s been a while. I was hoping to continue my exploration of agent-oriented programming, but for reasons I’d rather not get into I have to back-burner that for the time being. Anyway, I did something the other day that I thought was clever, and even better I have a way of talking about it that won’t tread on anyone’s toes.

Imagine, if you will, a country consisting of villages and towns scattered across a vast landscape, and with few roads to speak of outside the populated centers. Besides, it’s dangerous to travel more than a day outside because at night the roving packs of beasties will surely steal one’s goods and devour everyone in sight. So that limits travel to about twenty miles for all but the bravest adventurers.

Luckily, there are magical teleporters that can transport people and goods from one door to another in the blink of an eye. Convenient, no? Unfortunately, they themselves are limited to a hundred mile range. So, you can travel over land to the nearest town with a teleporter (up to twenty miles), then cobble together a sequence of teleports that will get you near your destination (up to a hundred miles each), and then travel over land again to your destination (again, up to twenty miles away).

The downside is that there’s a lot of traffic through these teleporter towns, especially where there are bottlenecks to some far-flung arm of the country. On top of that, having to take a dozen hops to get where you’re going — with a line to wait in each time — gets really annoying. Even worse, there are some clusters of towns that are still each more than a hundred miles from any other town, and so they can’t use the teleporters to get out into the wider world. The teleporter network is nice, but it’s not ideal.

But now along comes a new super-teleporter that has no maximum range. Any two super-teleporters can send people and goods from one to the other, no matter how far apart they are. But of course they’re phenomenally expensive and difficult to maintain, so we don’t want to put them everywhere. It only really makes sense to put them in towns that already have basic teleporters, to eliminate an extra ground transport step. So here’s the sketch of the new transportation method:

  1. Travel over land to the nearest teleporter town (there’s already one within twenty miles). If you can travel the next day to your destination, great; otherwise, take the teleporter.
  2. If you can teleport directly to the nearest teleporter town to your destination from here, do that and then travel over land like before; otherwise, you’ll use the super-teleporter. If the current town doesn’t have one, use the basic teleporter to get to a super-teleporter town in one hop.
  3. Take the super-teleporter as close as you can get to your destination.
  4. If your destination is within twenty miles, travel over land; otherwise, take one basic teleport hop to get to a teleporter town that’s within twenty miles of your destination.

And there: within at most three hops and two overland trips we can go from any town to any other town. To restate it a bit, the longest travel consists of an overland trip to a teleporter town, one basic teleport hop to a super-teleporter town, one super-teleport hop towards the destination, one basic teleport hop even closer to the destination, and one last overland trip. Any of these legs might be collapsed if, say, the super-teleport towns on both ends happen to be the same town anyway.

Okay, so what does this require of our super-teleporter network? To make this work, we have to assume that there will always be a super-teleporter within one basic teleport hop of any teleporter town. But how are we to pick where to install the super-teleporters?

The method we’re going to use is called a “sieve”. We have a collection of objects that we need to “cover” in some way, and we have a collection that will do the job, but is redundant. We want to filter the redundant covering down to a more efficient one. The sieve isn’t a terribly complicated way of doing it, either: we pick out one of our teleporter towns and place a super-teleporter there, then we remove from consideration all of the teleporter towns that this one covers, and we repeat this until we’ve dealt with all the teleporter towns.

Let’s see how this looks in the language of the mystical Eastern sorcerers, j’Va:

Comparator<TeleporterTown> sortOrder =
          Collections.reverseOrder(new NearbyTownsComparator());
SortedSet<TeleporterTown> potentialSuperTeleporterLocations =
         new TreeSet<TeleporterTown>(sortOrder);
potentialSuperTeleporterLocations.addAll(teleporterTownSet);

Set<TeleporterTown> superTeleporterTowns = new HashSet<TeleporterTown>();
 
while (!potentialSuperTeleporterLocations.isEmpty()) {
    TeleporterTown selectedTown = potentialSuperTeleporterLocations.first();
    potentialSuperTeleporterLocations.remove(selectedTown);
    superTeleporterTowns.add(selectedTown);

    Set<TeleporterTown> townsToRemove = new HashSet<TeleporterTown>();
    for (TeleporterTown town : potentialSuperTeleporterLocations) {
        if (distanceBetween(selectedTown,town) <= TELEPORT_RADIUS) {
            townsToRemove.add(town);
        }
    }
    potentialSuperTeleporterLocations.removeAll(townsToRemove);
}

The sortation part isn’t really necessary to the operation of the sieve, but it helps with the overall efficiency to first pick objects that do a good job of covering on their own. In this case, potentialSuperTeleporterLocations will be sorted in descending order by the number of towns within a day’s ground travel, so we will always pick out the most central towns first.

So what’s so cute about this? Well, it’s the same procedure that we use to identify prime numbers with the Sieve of Eratosthenes!

SortedSet<Integer> potentialPrimes = new TreeSet<Integer>();
for(Integer i=2;i<MAX_INT_TO_TEST;i++) {
    potentialPrimes.add(i);
}

Set<Integer> primes = new HashSet<Integer>();

while (!potentialPrimes.isEmpty()) {
    Integer p = potentialPrimes.first();
    potentialPrimes.remove(p);
    primes.add(p);

    Set<Integer> numbersToRemove = new HashSet<Integer>();
    for (Integer n : potentialPrimes) {
        if (n%p == 0) {
            numbersToRemove.add(n);
        }
    }
    potentialPrimes.removeAll(numbersToRemove);
}
Categories: Uncategorized

Peer-Reviewing Agents

September 18, 2010 Leave a comment

There’s a quick little paper up on the arXiv that uses an agent-based approach to investigate the behavior of peer-review in the presence of dishonest (or stupid) actors. A hat-tip to Alexandre Borovik for the heads-up.

Bidirectional Maps

September 17, 2010 12 comments

Today I have a bit of a data structures question. I have a many-to-one relation, and I want a good way to query it in both directions.

Let’s say, for instance, that I’ve got a list of NANP area codes and the states and territories that they serve Every area code serves only one state or territory (if this isn’t quite accurate, fudge it), but a given state or territory may be served by more than one area code.

A common use might be to bring an area code and see which state or territory it serves. The obvious data structure for this purpose is a map — a collection of key/value pairs — which takes a single access to return the answer.

But now let’s say I want to bring a state or territory and get a set of the area codes that serve it. Using a map, the na├»ve approach would be to walk through the entire key set of the map, accumulating a set of those keys which correspond to the specified value. For a map with n keys, this takes a guaranteed n accesses to return the answer. For area codes, this is a thousand times slower than searches in the other direction.

Now, there may be a better way of doing this, but I can’t seem to think of it myself. So I’m going to throw it out to the wisdom of the internet. To be explicit: the information itself is a many-to-one relation between two sets containing n “entries”, which may be queried in either direction. I have a two solutions so far, which illustrate some of the trade-offs.

First is the aforementioned solution of a map with an auxiliary function for the reverse query. This gives us one query direction in 1 accesses, the other query in n accesses, taking up n units of space. In Java, this can be implemented by a prepackaged Map object and a new method.

The second solution is to maintain two maps, the second of which is keyed by the value set of the first map, and whose values are sets of keys from the first map. This gives both queries in 1 time, but doubles the required space since we’re essentially duplicating the data. In fact, this makes implementation more complicated, because we have to maintain the constraint that both maps contain equivalent relations expressed in two different ways. In Java, we’d have to write a whole new class backed by our two maps and carefully hide all the implementation details so that neither backing map could be altered without altering the other correspondingly. Either that or we’d have to use two Map objects and program extremely carefully, which is basically the sort of thing you want to avoid.

There is a potential third solution, but it doesn’t apply to this situation. Apache Commons provides a BidiMap or “bi-directional map” data structure. Unfortunately, as the Javadocs tell us:

This map enforces the restriction that there is a 1:1 relation between keys and values, meaning that multiple keys cannot map to the same value. This is required so that “inverting” the map results in a map without duplicate keys.

So this solution achieves its goal of “equal performance” at the cost of excluding many-to-one relations.

This sort of setup seems to be pretty natural; I’m sure that someone has looked into it. Is this truly the best we can do? Is there a tradeoff that makes one query direction take more accesses, but the other direction take fewer so they meet in the middle somewhere?

Categories: Uncategorized

A DaliBug Story

September 15, 2010 Leave a comment

Over at his LiveJournal — yeah, in the UK they evidently still use LiveJournal — @pozorvlak tells an interesting story about chasing down a bug while writing a C compiler. Includes a pretty cogent explanation of what a C compiler is supposed to do, in order to see why it wasn’t doing it.

Categories: Uncategorized
Follow

Get every new post delivered to your Inbox.