[ovs-dev] [Partial-Update-Map-Columns 0/7] Add Initial code for Partia-map-columns funtionality

Aymerich, Edward edward.aymerich at hpe.com
Wed Mar 23 23:15:29 UTC 2016


I see two approaches to implement your suggestions:

## 1. First Approach

The "new" datum contains a copy of the "old" datum, and the desired changes
(insert, delete or update) are applied into the "new" datum.

This implies that, at commit time, to find out what changed in the map, 
each key in the "old" datum must be compared with its pair in the "new" datum,
to find out what mutate operations should be perform. The following cases could
arise:
* if the key is found and the values are identical, then no change is needed. 
* if the key is found and the values are different, then the value must be 
  updated. Two mutators are generated in this case: one "delete" and one
  "insert".
* if the key is not found, then the key-value must be deleted. This generates
  a "delete" mutator.

Then, in order to find out what elements were inserted, each element in the
"new" datum must be compared to its pair in the "old" datum, then:
* if the key is found, then nothing must be done (any change is already
  covered in the previous cases).
* if the key is not found, then it is a new element and it must be inserted
  into the map. The corresponding "insert" mutator is generated.

Since elements in both datums are ordered, this comparisons can be perfomed in
O(n) time, being n the biggest number of elements in "old" or "new". The trick
would be to maintain the invariants (keys must be unique and sorted) in "new"
datum when elements are inserted or deleted.
  
This approach duplicates map memory, when maybe only a small number of
key-values are changed. It also uses a lot of CPU time doing a lot of
comparisons between elements in both "old" and "new" datums, and maintaining
invariants. And finally, the processing time depends on the size of the map,
not on the number of changes, which may be bad for big maps.

## 2. Second Approach

The "new" datum is initially empty, and only changes are stored.

In this case, when a user changes the value of some key, the new key-pair
element is stored in the "new" datum. The same happens when a user inserts a
new key-value. At commit time, the two cases can be differentiated as follows:
for each element in the "new" datum, search for it's key in the "old" datum:
* if the key is not found, then generate just a "insert" mutator.
* if the key is found, then generate two mutators: one "delete" and one
  "insert".

Using this approach, how a delete operation is stored inside the "new" datum?
One option is to set a key's value to NULL in the "new" datum, but for some
maps (simaps for example) setting a NULL value is not possible.

This approach avoids duplication of map memory, but it doesn't allow to store
delete operations.

## 3. Current Approach

The first and second approaches were considered and discarted, the first
because there were memory consumption concerns, and the second because it does
not store delete operations.

The approach currently implemented avoids duplicating the whole map by creating
a data structure that holds the desired changes (for all operation types:
insert, delete or update), in order to keep a small memory footprint. Moreover,
the current approach avoids comparing all keys by calculating the desired
operation just for the affected keys in the moment that such key if modified.
During commit time, it is necessary to do one pass in this structure to
generate the corresponding mutate operations.


## 4. Comparison

Given the limitation in the second approach, the first approach was implemented
to compare against the current approach, and to compare both against the old
method (get and set the full map).

A simple table was created containing one column of type map of strings to
strings. This table was populated with 100 rows, each one with a map of 20,000
elements. Then a number of operations (insert, delete, update) were performed,
i.e., 10 elements were inserted or 100 elements were deleted, for each row. The
results are shown below:

A = Old method
B = First described approach
C = Current approach

    INSERT (Time in s.)
|-------------------------|
|   |    1 |   10 |   100 |
|-------------------------|
| A | 7.55 | 7.46 |  7.72 |
| B | 3.90 | 8.35 | 52.39 |
| C | 3.16 | 3.11 |  3.31 |
|-------------------------|

    DELETE (Time in s.)
|-------------------------|
|   |    1 |   10 |   100 |
|-------------------------|
| A | 7.70 | 7.60 |  7.68 |
| B | 3.94 | 8.11 | 52.12 |
| C | 3.18 | 3.14 |  3.36 |
|-------------------------|

    UPDATE (Time in s.)
|------------------------|
|   |    1 |   10 |  100 |
|------------------------|
| A | 7.64 | 7.52 | 7.62 |
| B | 3.86 | 3.97 | 4.01 |
| C | 3.55 | 3.72 | 4.15 |
|------------------------|

For updates the time difference between B and C is not significant, and both
perform better than updating the whole map. But in the case of inserts and
deletes, the first described approach doesn't perform well. This is because
each time an element is inserted or deleted from the map, internally the IDL
inserts or deletes an element from the 'new' datum using
ovsdb_datum_add_unsafe() and ovsdb_datum_remove_unsafe(), and after that it
must run ovsdb_datum_sort() to maintain the invariants. When a significant
number of elements are inserted or deleted, the sorting time adds up and
degrades performance.

-----Original Message-----
From: Ben Pfaff [mailto:blp at ovn.org] 
Sent: jueves 10 de marzo de 2016 11:06 p.m.
To: Aymerich, Edward <edward.aymerich at hpe.com>
Cc: Lutz, Arnoldo <arnoldo.lutz.guevara at hpe.com>; dev at openvswitch.org
Subject: Re: [ovs-dev] [Partial-Update-Map-Columns 0/7] Add Initial code for Partia-map-columns funtionality

I understand the intention now.  The key seems to be your final
paragraph:

    Using different structures and logic to handle map operations,
    instead of trying to force the current structures (like 'old' and
    'new' datums in the row) to handle then, ensures that map operations
    won't mess up with the current logic to generate JSON messages for
    other operations.

What I don't understand yet is the perceived problem with using the old
and new data to handle map operations.  When I've thought about
implementing a similar feature myself, I had basically concluded that
the following was a reasonable approach:

    * Add another bitmap to each IDL row, one bit per column.

    * Retain the current functions to set columns.  If the client calls
      such a function, set the column's bit to 0 for the row.

    * Add a function to insert a key into a set column (or a key-value
      pair into a map column) and one to delete a key from a set column.
      Ordinarily, the implementation of the function would add or delete
      the key to/from the "new" datum and set the column's bit to 1.

Then, when the transaction gets committed, output a column with a bit
set to 0 as an "update" operation, or one with a bit set to 1 as a
"mutate" operation.  I think there might be some extra details to deal
with situations where the IDL client actually does a combination of
"set" and "insert/delete" operations for a single column, but is there a
real reason this simpler doesn't work?

Thanks,

Ben.

On Thu, Mar 03, 2016 at 02:40:32AM +0000, Aymerich, Edward wrote:
> Hello,
> 
> In the current implementation, every time an element of either a map or set
> column has to be modified, the entire content of the column is sent to the
> server to be updated. This is not a major problem if the information contained
> in the column for the corresponding row is small, but there are cases where
> these columns can have a significant amount of elements per row, or these
> values are updated frequently, therefore the cost of the modifications becomes
> high in terms of time and bandwidth.
> 
> In this solution, the ovsdb-idl code is modified to use the RFC 7047 'mutate'
> operation, to allow sending partial modifications on map columns to the server.
> The functionality is exposed to clients in the vswitch idl. This was
> implemented through map operations.
> 
> A map operation is defined as an insertion, update or deletion of a key-value
> pair inside a map. The idea is to minimize the amount of map operations
> that are send to the OVSDB server when a transaction is committed. 
> 
> In order to keep track of the requested map operations, structs map_op and
> map_op_list were defined with accompanying functions to manipulate them. These
> functions make sure that only one operation is send to the server for each
> key-value that wants to be modified, so multiple operation on a key value are 
> collapsed into a single operation.
> 
> As an example, if a client using the IDL updates several times the value for
> the same key, the functions will ensure that only the last value is send to
> the server, instead of multiple updates. Or, if the client inserts a key-value,
> and later on deletes the key before committing the transaction, then both
> actions cancel out and no map operation is send for that key.
> 
> To keep track of the desired map operations on each transaction, a list of map
> operations (struct map_op_list) is created for every column on the row on which
> a map operation is performed. When a new map operation is requested on the same
> column, the corresponding map_op_list is checked to verify if a previous 
> operations was performed on the same key, on the same transaction. If there is
> no previous operation, then the new operation is just added into the list. But
> if there was a previous operation on the same key, then the previous operation
> is collapsed with the new operation into a single operation that preserves the
> final result if both operations were to be performed sequentially. This design
> keep a small memory footprint during transactions.
> 
> When a transaction is committed, the map operations lists are checked and
> all map operations that belong to the same map are grouped together into a
> single JSON RPC "mutate" operation, in which each map_op is transformed into
> the necessary "insert" or "delete" mutators. Then the "mutate" operation is
> added to the operations that will be send to the server.
> 
> Once the transaction is finished, all map operation lists are cleared and
> deleted, so the next transaction starts with a clean board for map operations.
> 
> Using different structures and logic to handle map operations, instead of
> trying to force the current structures (like 'old' and 'new' datums in the row)
> to handle then, ensures that map operations won't mess up with the current
> logic to generate JSON messages for other operations.
> 
> 
> Regards,
> 
> Edward Aymerich
> Networking Software Engineer
> 
> edward.aymerich at hpe.com
> 
> Building 8, Ultra Park
> Heredia, Costa Rica
> hpe.com
> 
> -----Original Message-----
> From: dev [mailto:dev-bounces at openvswitch.org] On Behalf Of Ben Pfaff
> Sent: viernes 26 de febrero de 2016 03:29 p.m.
> To: Lutz, Arnoldo
> Cc: dev at openvswitch.org
> Subject: Re: [ovs-dev] [Partial-Update-Map-Columns 0/7] Add Initial code for Partia-map-columns funtionality
> 
> On Mon, Feb 22, 2016 at 07:58:16PM +0000, Lutz, Arnoldo wrote:
> > In the current implementation, every time an element of either a map 
> > or set column has to be modified, the entire content of the column is 
> > sent to the server to be updated. This is not a major problem if the 
> > information contained in the column for the corresponding row is 
> > small, but there are cases where these columns can have a significant 
> > amount of elements per row or the frequency at which these values are 
> > updated is high that making the cost of the modifications to become 
> > high in terms of time and bandwidth.
> > 
> > In this solution, the ovsdb-idl code is modified to use mutate 
> > operation, already implemented in the server code, to allow that kind 
> > of partial modifications on map columns. The functionality is exposed 
> > to clients in the vswitch idl.
> > 
> > Arnoldo Lutz (3):
> >       Add code to create partial map functions in autogenerated code
> >       Add documentation on how to use partial update of map columns
> >       Adds usage help on command to test of partial update of map 
> > column
> > 
> > Edward Aymerich (3):
> >       Add functionality to skeleton functions for Partial Map Update
> >       Add and correct functionality of Partial Update Map Columns
> >       Add fixes, improvements, refactors and cleans code
> 
> Thanks for working on this.  It seems like a useful feature.
> 
> I've started skimming through the series.  Before I get into all the details, though, please help me with a general question.  It seems to me like this is actually a pretty simple thing to do.  The idea is that if the client just wants to add or remove key-value pairs, instead of replacing the entire map, then the IDL should be able to send operations to do that.  I can see why this requires a new bit-vector, to distinguish columns where the client wants to add/remove columns from those where the client wants to replace the map, but it seems like the series add a lot more infrastructure than that.  Can you explain the overall design?
> 
> Thanks,
> 
> Ben.
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev



More information about the dev mailing list