Make old-timestep eviction less surprising

[philip-davis]

Two aspects of old timestep eviction are surprising (to me at least):

1. Eviction is performed without consideration of whether it is required. This is fine if version always increments by one, but suppose we have max_versions = 5, and the following versions are written:
   0 2 4 5 7

Here we wrote 5 time steps, so as a user I would expect all of them to still be stored. But it is not so! Five overwrote 0 and 7 overwrote 2. So I only have three timesteps in dataspaces after this sequence of puts.

2. Eviction is based upon overlap of bounding boxes. Suppose max_versions = 1. Consider the following three scenarios:

a. {version:0, lb:{0,0}, ub:{3,3}} followed by {version: 1, lb:{0,0}, ub:{3,3}}. The first put is evicted and replaced. So far, so good.
b. {version:0, lb:{0,0}, ub:{3,3} } followed by {version: 1, lb:{4,4}, ub:{7,7}}. Nothing is evicted, both are in memory. This seems to violate "max_versions = 1".
c. {version:0, lb:{0,0}, ub:{3,3} } followed by {version: 1, lb:{3,3}, ub:{6,6}}. The first put is evicted and replaced. This honors max_versions, but inconsistent with b.

Fixing 1 seems to just require adding some logic when checking for eviction. We only want to evict if we actually have max_versions objects stored that are eligible for eviction otherwise.

Fixing 2 gets at a semantics issue of what we mean by max_version. So do we mean that we will hold max_version versions of each element of each variable, or do we mean that we will hold elements for up to max_threads, or something else?

[philip-davis]

This sequence of puts is also concerning:

d. {version:0, lb:{0,0}, ub:{3,3}} followed by {version: 0, lb:{3,3}, ub:{3,3}} The first put will be evicted, and only the second put remains. It seems to be that the second put should have resulted in the update of the element at [3][3], and that eviction should not come into play at all here.

[melrom]

There are two things being discussed here and they need to be separated.

1. Logical Eviction
2. Physical Eviction

For logical eviction, there are two criteria: variable name and bounding box. Max versions does not mean that there is only 1 version of data for the entire data domain. That doesn't make sense because a lot of scientific applications work on separate regions. We don't want to clear out timestep 0 data in lb:{0,0}, ub:{3,3} if the application in timestep 1 is operating on region lb:{4,4}, ub:{7,7}. The two regions have no overlap with one another. The data in region (0,3)-(3,3) is still valid data in the entire data domain.

In c and d, the bounding box at 3,3 overlaps, which triggers the eviction. The reason the entire region is evicted is mostly just because it was easiest to code -- we have the metadata info that there IS overlap -- however, if we wanted to only 'evict' element (3,3), we would have to find out what server has the data object, copy the object back into the form relevant to the application, and replace a single element of it.

In part b, you start bringing up "both are in memory" and that's starting to refer to physical eviction. The servers that are responsible for keeping track of the data don't necessarily have the data in their physical memory. The eviction process is mostly at the DHT level only (i.e., metadata) unless the physical data object is on the same server. I've always found this to be somewhat irritating because it means we are essentially taking up space in memory for data objects that the user has already deemed as being irrelevant to them and that even DataSpaces no longer knows about but the memory itself is not cleared or freed.

[parasharmanish]

Thank you for the clarification. We need to document the semantics precisely. Is there a garbage collection mechanism to follow up the logical eviction with physical eviction. Regards Manish

…

-- ========================================================================== Manish Parashar Office: CoRE Bldg, Rm 628 RDI2/Dept. of Computer Science Phone: (848) 445-5388 Rutgers University Fax: (732) 445-0537 110 Frelinghuysen Road Email: parashar at rutgers dot edu Piscataway, NJ 08854-8019 WWW: http://parashar.rutgers.edu =========================================================================== On Jul 13, 2017, at 11:05 PM, Melissa <notifications@github.com<mailto:notifications@github.com>> wrote: There are two things being discussed here and they need to be separated. 1. Logical Eviction 2. Physical Eviction For logical eviction, there are two criteria: variable name and bounding box. Max versions does not mean that there is only 1 version of data for the entire data domain. That doesn't make sense because a lot of scientific applications work on separate regions. We don't want to clear out timestep 0 data in lb:{0,0}, ub:{3,3} if the application in timestep 1 is operating on region lb:{4,4}, ub:{7,7}. The two regions have no overlap with one another. The data in region (0,3)-(3,3) is still valid data in the entire data domain. In c and d, the bounding box at 3,3 overlaps, which triggers the eviction. The reason the entire region is evicted is mostly just because it was easiest to code -- we have the metadata info that there IS overlap -- however, if we wanted to only 'evict' element (3,3), we would have to find out what server has the data object, copy the object back into the form relevant to the application, and replace a single element of it. In part b, you start bringing up "both are in memory" and that's starting to refer to physical eviction. The servers that are responsible for keeping track of the data don't necessarily have the data in their physical memory. The eviction process is mostly at the DHT level only (i.e., metadata) unless the physical data object is on the same server. I've always found this to be somewhat irritating because it means we are essentially taking up space in memory for data objects that the user has already deemed as being irrelevant to them and that even DataSpaces no longer knows about but the memory itself is not cleared or freed. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fmelrom%2Fdataspaces%2Fissues%2F24%23issuecomment-315257724&data=02%7C01%7Cparashar%40ored.rutgers.edu%7C7293f42446cc487f23f408d4ca653911%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636355983482085413&sdata=MjLdtrYPSdWq8su2Rv8Y14UJ42z7UTMk%2F4lq8UuCB7k%3D&reserved=0>, or mute the thread<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAIvVmT16A4OjGg3XWpnMWO-caOEcqklQks5sNtsGgaJpZM4OXYa0&data=02%7C01%7Cparashar%40ored.rutgers.edu%7C7293f42446cc487f23f408d4ca653911%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636355983482085413&sdata=eNFvUUDnW%2FJXZgMmaTkPel5362FwD8eAjK9E5HAXwxU%3D&reserved=0>.

[philip-davis]

Good point. I think I'm primarily concerned with logical behavior in this issue, since it has consequences for program behavior, for example if I split a put into multiple component puts, then different data will be evicted by future overlapping puts, and so a different set of data will be available depending how the puts are decomposed. Sent from my mobile.

…

On Jul 14, 2017, at 7:10 AM, parasharmanish ***@***.***> wrote: Thank you for the clarification. We need to document the semantics precisely. Is there a garbage collection mechanism to follow up the logical eviction with physical eviction. Regards Manish -- ========================================================================== Manish Parashar Office: CoRE Bldg, Rm 628 RDI2/Dept. of Computer Science Phone: (848) 445-5388 Rutgers University Fax: (732) 445-0537 110 Frelinghuysen Road Email: parashar at rutgers dot edu Piscataway, NJ 08854-8019 WWW: http://parashar.rutgers.edu =========================================================================== On Jul 13, 2017, at 11:05 PM, Melissa ***@***.******@***.***>> wrote: There are two things being discussed here and they need to be separated. 1. Logical Eviction 2. Physical Eviction For logical eviction, there are two criteria: variable name and bounding box. Max versions does not mean that there is only 1 version of data for the entire data domain. That doesn't make sense because a lot of scientific applications work on separate regions. We don't want to clear out timestep 0 data in lb:{0,0}, ub:{3,3} if the application in timestep 1 is operating on region lb:{4,4}, ub:{7,7}. The two regions have no overlap with one another. The data in region (0,3)-(3,3) is still valid data in the entire data domain. In c and d, the bounding box at 3,3 overlaps, which triggers the eviction. The reason the entire region is evicted is mostly just because it was easiest to code -- we have the metadata info that there IS overlap -- however, if we wanted to only 'evict' element (3,3), we would have to find out what server has the data object, copy the object back into the form relevant to the application, and replace a single element of it. In part b, you start bringing up "both are in memory" and that's starting to refer to physical eviction. The servers that are responsible for keeping track of the data don't necessarily have the data in their physical memory. The eviction process is mostly at the DHT level only (i.e., metadata) unless the physical data object is on the same server. I've always found this to be somewhat irritating because it means we are essentially taking up space in memory for data objects that the user has already deemed as being irrelevant to them and that even DataSpaces no longer knows about but the memory itself is not cleared or freed. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fmelrom%2Fdataspaces%2Fissues%2F24%23issuecomment-315257724&data=02%7C01%7Cparashar%40ored.rutgers.edu%7C7293f42446cc487f23f408d4ca653911%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636355983482085413&sdata=MjLdtrYPSdWq8su2Rv8Y14UJ42z7UTMk%2F4lq8UuCB7k%3D&reserved=0>, or mute the thread<https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAIvVmT16A4OjGg3XWpnMWO-caOEcqklQks5sNtsGgaJpZM4OXYa0&data=02%7C01%7Cparashar%40ored.rutgers.edu%7C7293f42446cc487f23f408d4ca653911%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636355983482085413&sdata=eNFvUUDnW%2FJXZgMmaTkPel5362FwD8eAjK9E5HAXwxU%3D&reserved=0>. — You are receiving this because you were assigned. Reply to this email directly, view it on GitHub, or mute the thread.

[philip-davis]

Specifically, this sequence:
*1. put:{version:0, lb:{0,0}, ub:{1,1}}
2. put:{version:0, lb:{1,1}, ub:{1,1}}
3. get:{version:0, lb:{0,0}, ub:{0,0}} [error]

will have different results than this sequence:

1. put:{version:0, lb:{0,0}, ub:{0,1}}
   *2. put:{version:0, lb:{1,0}, ub:{1,1}}
2. put:{version:0, lb:{1,1}, ub:{1,1}}
3. get:{version:0, lb:{0,0}, ub:{0,0}} [no problem]

Even though it seems intuitive for the system to be in the same state after the starred operation for each sequence.