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:b...@ovn.org] > Sent: jueves 10 de marzo de 2016 11:06 p.m. > To: Aymerich, Edward <edward.aymer...@hpe.com> > Cc: Lutz, Arnoldo <arnoldo.lutz.guev...@hpe.com>; dev@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.aymer...@hpe.com > > > > Building 8, Ultra Park > > Heredia, Costa Rica > > hpe.com > > > > -----Original Message----- > > From: dev [mailto:dev-boun...@openvswitch.org] On Behalf Of Ben Pfaff > > Sent: viernes 26 de febrero de 2016 03:29 p.m. > > To: Lutz, Arnoldo > > Cc: dev@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@openvswitch.org > > http://openvswitch.org/mailman/listinfo/dev _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
