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

Ben Pfaff blp at ovn.org
Wed May 18 17:16:47 UTC 2016


I didn't realize that you were interested in such huge maps.  OK, that's
fine then.

On Wed, Mar 23, 2016 at 11:15:29PM +0000, Aymerich, Edward wrote:
> 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