Time to process incoming vectors and return results is too slow

@janbiedermann

According to @janbiedermann for a sample request of 70 vectors it can take say 50 MS to process, but for a similar request of 140 vectors (same application) it then goes up to 335 MS, this for a request that only uses a few MS of Active Record processing time.

While it is understandable that the time increases based on the amount of data returned (probably O(n*log(n) of total amount of data returned) 335 MS seems like a long time.

This issue is to discuss and understand the algorithm, and suggest improvements.

@janbiedermann

This comment was actually from @janbiedermann on the chat but I am copying it here to get the conversation rolling:

@catmando i dont think its a good idea to have the client do the compilation here. I step back a little and look at the process:
The client collects items in a hash
A hash is not that far away from a graphql like hashy structure.
The client could as well collect items into a graphql like structure.
Then the client could push this as is to the server
The server would then understand this and collect items from the db.
So the server would then be a, limited to AR attribute and scope accesses, graphql interpreter/compiler. Emphasis on limited. With datatypes implied, comvention over configuration.
Maybe.
And we would then have another cool badge for marketing "GraphQL"
We could then even delegate part of the process to existing, possibly js, libraries, what @barriehadfield would like.

@janbiedermann

I don't think switching to graphQL would help. That would just change the syntax for communicating the request to a more general purpose syntax, from one that is already specialized to the purpose.

Lets start by understanding how the vectors work:

Each request during rendering turns into a "vector" (a json structure) that looks like this:
[model, method, method, method, method, method....]
methods come in several flavors: just the name (a string) of a method to apply to the chain.
methods can also be an array like [method, param, param] allowing for parameters to passed to the method.
Finally there are some special methods like 'all' and "" and "*1" "*2" etc. which will be explained below.

So you might have 2 vectors like this:

['User', ['managed_by', 'fred'], '*all', 'first_name']
['User', ['managed_by', 'fred'], '*all', 'last_name']

this might be the result of somebody rendering this:

   # param.manager currently = 'fred'
  UL do
    User.managed_by_(param.manager).each do |user|
      LI { "#{user.first_name} #{user.last_name}" }
    end
  end

In reality, the vectors represent a tree structure like this:

User -> managed_by('fred') -> *all -> first_name
                                   -> last_name

However, the current code structure does not preserve the tree structure and instead passes each terminal request (such as first_name or last_name) as a separate vector.

At the end of each render cycle all the vectors are shipped up to the server, where they get fetched from the data base.

One inefficiency is because the vectors are no longer "trees" the sql lookup has to be "smart" and avoid re-evaluating each sub branch of the tree that might be repeated. So for example:

In the above case we first get the "User" model, for the first vector, and save this in a structure.

Then we get the "managed_by('fred')" (a relation) from the saved "User" sub-vector and save that.

Then we get apply "all" to that relation, this generates a subtree for each record in the "all" sql search.

finally, we get the value of first_name and apply it to all those records.

Then we start down the second vector, but this time we notice that each of the sub-vectors has already been evaluated, so we skip those, until we get the unique part ("last_name") and just add that to our data.

The problem is that each of these sub-vectors is having to do a hash lookup to see if sub-vector has already been evaluated.

In essence we are reconstructing the tree structure that got flattened into the separate vectors.

More over when we evaluate a sub-vector ending in "*all" we add a new "sub-vector" for each record in the "all" search. This means the lookup space to find subvectors can be huge. For example in this case there are 5 subvectors coming from the client, but if "fred" is managing 100 employees, there will be 104 subvectors after the first vector is evaluated, now we start processing the second vector and have to search all 104 vectors every time looking for matching subvectors.

Finally when all this work is done, all the collected data gets packaged back up as a tree structure (annotated so the client can easily reassociate the data with the waiting expressions.)

From memory I think @janbiedermann 's studies showed that this final step is not the biggest part of the problem, so perhaps we ignore it for now

Before going any further, after writing this it seems pretty obvious we can make a huge improvement by keeping the tree structure intact from the client. This would eliminate all the searches and keep the entire process in linear time based on the size of the tree.

As an initial step rather than rewriting both the client (sender) and server (receivers), I am suggesting we add a preprocessing step to the server side whereby take the vectors and then simply rebuild the tree structure. This will run in O(n*log(n)) time but n will just be the sum of all the vector lengths, but will not include all the search results. So in the above simple example, n will be 10, not 105.

This will be relatively easy to do, and will can prove the concept.

It will also (I think) hugely simplify the code, as right now we are in a way doing both at once (i.e. evaluating AR expressions, while trying to figure out where they fit into the tree.) Instead we can just have a tree, that we walk down calculating what we need, and updating with the results.

Also while I don't think GraphQL would help the performance issue in of itself, In looking at it, it does seem that it makes a lot of sense to make GraphQL the underlying protocol.

I.e. hyper-model on the client would package up the requests as a graph, send it off the server to fetch. We might be able to throw away a huge pile of code :-) and at the same time make attaching to other persistence stores much easier.

Put it this way if I were writing hyper-model today (instead of 3 years ago) I would probably start with GraphQL as the base.

Pretty exciting possibility.

I think I will put it in as a separate issue!

Currently vectors are created and collected once a data item is referenced.
If a data items is referenced several times, this leads to creation of several, identical vectors, which are collected. Then before the request is made, so that not to many vectors are requested, .uniq is called on the resulting array. That significantly hurts performance (adds 35ms for 140 vectors before the request is even made, comparison on vector_count * vector_depth again).

@catmando

Thanks for the detailed write-up @catmando, now I see a little more how this magic works!

Thinking more about the above... here is what we do:

Currently the cache consists of many many "resolved" vectors. Keep in mind that a simple vector like [User, 'some_scope', ...] can add 1000's of resolved vectors (one for each record returned by some_scope) to the cache, and before each new vector is added the cache has to be searched.

Because the cache is "flat" following vector lookups in the cache must search the entire cache.

Step 1: Modify this method (in server_data_cache.rb)

        def self.[](models, associations, vectors, acting_user)
          ActiveRecord::Base.public_columns_hash
          result = nil
          ActiveRecord::Base.transaction do
            cache = new(acting_user, ReactiveRecord::Base.save_records(models, associations, acting_user, false, false))
            vectors.each { |vector| cache[*vector] }
            result = cache.as_json
            raise ActiveRecord::Rollback
          end
          result
        end

So it looks like this:

        def self.[](models, associations, vectors, acting_user)
          # convert the vectors list back to a tree.
          # the tree is in the format of the final output (i.e. cache.as_json) but with pieces that
          # are not yet populated.  

          # eventually we will just build this tree on the client and pass it up instead of re-building it here
          # in other words this line can be removed eventually
          tree = build_tree_from_vectors(vectors)
          ActiveRecord::Base.public_columns_hash
          ActiveRecord::Base.transaction do
            # save all the models that have been updated on the client, but not yet saved
            # these will get rolled back below
            temp_record_buffer = ReactiveRecord::Base.save_records(models, associations, acting_user, false, false)
            # now walk the tree evaluating each branch using active record, and filling in the leaf
            # nodes
            tree.populate_tree(acting_user, temp_record_buffer)
            raise ActiveRecord::Rollback
          end
          tree.as_json # this is just a simple "as_json" not the complex custom thing.
        end

this should be much faster as we are only transforming the vectors into the tree once (at the beginning) and even this transform can eventually be removed by having the client keep the "vectors" in actual tree format and just shipping them up to the client in that form.

The only problem with this approach is that to support pre-rendering we need to modify the def [] method (i.e. the add vector to instance of a cache)

The reason is that during pre-rerendering we have direct access to the database so as each piece is rendered we pull the data out of the db. Easy. But we also want to save it in the same output tree structure that the above fetch returns. This is so that at the end of prerendering we not only have the generated HTML, but also the data to pre-reload into the client DB cache as if we had just fetched it all.

So really what we are doing is replacing the "cache" which with a "cache-tree

it should at the end just be:
result_tree = ReactiveRecord::Base.save_records(request_tree, acting_user, false, false)

nope

save_records saves records.

The fetch process works like this:

- vectors (or should be tree) is gathered during rendering
- client gathers up all changed (but not saved) records that have a relationship with the data being fetched by the vectors.
- vectors/tree + changed record list is sent to the server
- server saves the changed records inside of transaction (so it can be rolled back)
- evaluates vector/tree
- rolls back transaction
- returns the evaluated tree (must be a tree by now)

The reason for sending the changed stuff to the server is like this:

Say you were executing on the server (normal rails - no hyperloop) and you have a user model, and user's manager relationship. You now change user "mitch" from being managed by manager "fred" to manager "barry", but don't yet save. You then ask AR for "barry's" list of workers. Even though nothing is saved, AR will return the correct list of info.

So when we evaluate expressions from the "vector/tree" on the server we have to have any other related records hanging around. I can't remember why the actual save/rollback was necessary but it was the easiest way to solve some problem

Some thoughts on the basic plan here:

vectors are conceptually always in the form:

Model.exp1.exp2...expn.terminal-operator

where exp is
method(param1, param2 ...)

and terminal-operator is either an exp (like above) or one of the special terminals *all or *count

combining vectors will result in a tree structure, with each Model being a root of a tree:

Simple representation:

# REQUEST TO SERVER
{Model1 => { 
  [method-a, param1, param2] => { 
    [method-b, param1, param2] => {},
    '*all' => {}
    [method-c] => {},
  [method-d] => {},
  '*count' => {},
  }
}

A real-world example might be:

# REQUEST TO SERVER
{User => {
  [:find, 12] => {
    [:first_name] => {}
    [:todos] => {
      [:title] => {}
      '*count' => {}
      [:active] => {
        [:due_date] => {}
        }
      }
    }
  }
}

above structure does not show which are relations (arrays of items) and which are single values, so the result would be somewhat different coming back:

# RESPONSE FROM SERVER BACK (WITH DATA FILLED IN)
{User => {
  [:find, 12] => {
    [:first_name] => 'fred'
    [:todos] => {
      'all' =>  [ 
        {[:title] => 'the todo'}},
        {[:title] => 'another todo'}}
      ],
      'count' => 2,
      [:active] => {
        'all' => [
          {
            [:due_date] => '1/1/2019'
          }
        ]
      }
    }
  }
}

We could do this with GraphQL (see #9) it looks very similar (but not now :-) )
Both the request and response is very similar to GraphQL, just different syntax, for now I am heading to a more verbose syntax just for ease of understanding.

One problem is that the way data is being sent back from the server was "optimized" to be fairly "compact" but still use regular JSON. I think I was wrong to make it so "compact" because it takes a lot of extra processing power on the client to decode the JSON. Instead I think a more explicit structure where we say exactly what is going on, will be better. It will be much bigger, but the client decode will be faster.

# RESPONSE COMING BACK FROM SERVER
{
  method:  'User',
  send: [
    {
      method: :find,  # this is not strictly needed in the response, but I would 
      params: [12],   # leave it for debug purposes.
      type: :record,
      id: 12,
      send: [
        { 
          method: :first_name,
          type: :string,
          value: 'fred'
        },
        {
           method: :todos
           type: :collection,
           count: 2,
           send: [
             {  <--- here is confusing part I think... .todos.title is actually .todos.collect.title
               method: :title

To be continued

The last of the above snippet is where i am in my thoughts too.

Question:
Why is there a method "find"?
We have attributes, relations, scopes.
Instead in GraphQl we just submit what we have, and ask for what we want.

# Request
{ user(id: 12) {
    first_name,
    todos {   
      title
}}}

(If i got that query right, of which i am currently not sure, because i am still learning)

# Response
{ user {
    id: 12,
    first_name: 'Hans-Peter',
    todos: [
        title: 'Do it!',
        title: 'Order Hyperloop'
    ]
}}}

@janbiedermann

@janbiedermann - what do you mean by "why send this information"??
not sure what information you mean.

I have updated the above comment to hopefully clarify.

Also the reason "find" is needed is because that is presumably what the client code requested.

In otherwords the client has some line like this: Todo.find(12)...

There is nothing special about "find" we just treat it as another class method, that happens to return a record. I guess we could somehow optimize the query to "notice" the use of find, and use a shorter syntax (like graphql) but this would be more work in client and server.

The way hyperloop works is simple: We just encode the method call find(12) in some JSON, send it the server, and let the server send whatever method to the object. Basically we are doing ruby method "sends" across the wire.

Your clarification answered my question. I updated my comment above.
Still, the 'find' looks odd, but it depends on what you want.
If you want to support other ORMs custom convenience methods on the client too, then its very nice. everything there out of the box.
If its just about getting the data, then just working with the attributes, relations, scopes is good.

This is now in progress, because of necessity, see:
ruby-hyperloop/hyper-mesh#45

Navigation Menu

Repository navigation

Time to process incoming vectors and return results is too slow #8

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Time to process incoming vectors and return results is too slow #8

Description

Activity

catmando commented on Nov 21, 2017

catmando commented on Nov 21, 2017

catmando commented on Nov 21, 2017

janbiedermann commented on Nov 22, 2017

barriehadfield commented on Nov 22, 2017

catmando commented on Nov 22, 2017

janbiedermann commented on Nov 22, 2017

catmando commented on Nov 22, 2017

catmando commented on Nov 22, 2017

janbiedermann commented on Nov 23, 2017

catmando commented on Nov 23, 2017

janbiedermann commented on Nov 26, 2017

janbiedermann commented on Dec 31, 2017

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions