home

These are a few of my favorite things...

Sep 20 '17

Some brief notes on a couple of projects I've been involved with this year for my edification and for profit ;)

edit-along

Collaborative in-browser text editor

Challenges

Pessimistic concurrency control

Methods to achieve consistency

Can this approach scale?

Consider the time complexity of mutual exclution:

Any alternatives?

Enters optimistic concurrency control:

The algorithm

differential synchronization (source: )
Differential synchronization algorithm (source: https://neil.fraser.name/writing/sync/ )

Normal operations

Error scenarios

The algorithm is forgiving of unreliable networks:

json-distill

This past summer I had the good fortune to work in the company of some very capable developers and all around wonderful people at Earnest. One of the two projects I completed while there turned out to be particularly rewarding and involved designing a tiny domain specific language and implementing an interpreter to go with it for querying JSON. In the process, I discovered the joy of logic programming and conceived of a pet project to work on in the coming months. The GitHub link is off limits at present, but I'm hoping that the project will be released under an open source license.

Problem statement:

What if...

Industrial strength solution

What I set out to do

How do we typically deal with big JSON?

Is there a query language for JSON?

asked: 8 years, 3 months ago

viewed: 87,895 times

active: 1 month ago

https://stackoverflow.com/questions/777455/is-there-a-query-language-for-json

Can we do it in a simpler way?

Sample JSON:

1     {
2       ...
3         "ancestor": ...
            ...
              "parent": {
                "child": ...,
                "sibling": ...,
                ...
              },
            ...
          ...
        ...
13852 }

Query to match:

const query = `
{
  ancestor {
    parent {@parent
        child
        sibling
    }
  }
}
`;

A few additional features:

const query = `
{
  ancestor {
    parent (${aFilter}) {@parent @container
        child
        sibling
    }
  }
}
`;

Can in principle serialize and pass with the query a callback to filter results in the context made available by the service:

const { match } = require('json-distill');

const aFilter = (results, context) => {
    // ...filter 'results' with access to 'context'
};

const query = `
{
  ancestor {
    parent (${aFilter}) {@parent @container
        child
        sibling
    }
  }
}
`;

Main use case: match on the server

However, we're not limited to server-side processing. Can pattern match JSON from within any module:

const results = fetch(
    'https://www.googleapis.com/...')
  .then(res => res.json())
  .then(json => match(query, json));

NP-hard crux

Reasons for optimism: typical JSON object to be pattern matched is not significantly larger than the DOM tree that the language of CSS selectors or jQuery target.