[go: up one dir, main page]

WO2019155264A1 - Timer based cache for synchronization - Google Patents

Timer based cache for synchronization Download PDF

Info

Publication number
WO2019155264A1
WO2019155264A1 PCT/IB2018/050828 IB2018050828W WO2019155264A1 WO 2019155264 A1 WO2019155264 A1 WO 2019155264A1 IB 2018050828 W IB2018050828 W IB 2018050828W WO 2019155264 A1 WO2019155264 A1 WO 2019155264A1
Authority
WO
WIPO (PCT)
Prior art keywords
page
cache
page frame
hash table
secondary memory
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/IB2018/050828
Other languages
French (fr)
Inventor
Pratik Sharma
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Individual
Original Assignee
Individual
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Individual filed Critical Individual
Priority to PCT/IB2018/050828 priority Critical patent/WO2019155264A1/en
Publication of WO2019155264A1 publication Critical patent/WO2019155264A1/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0866—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches for peripheral storage systems, e.g. disk cache
    • G06F12/0871—Allocation or management of cache space
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0864—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches using pseudo-associative means, e.g. set-associative or hashing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/12—Replacement control
    • G06F12/121—Replacement control using replacement algorithms
    • G06F12/123—Replacement control using replacement algorithms with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0866—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches for peripheral storage systems, e.g. disk cache
    • G06F12/0868—Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1008—Correctness of operation, e.g. memory ordering
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/46—Caching storage objects of specific type in disk cache
    • G06F2212/461—Sector or disk block

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)

Abstract

Here we have a hash table with page number as key and the address of the corresponding page frame in the cache along with the dirty bit as the value. If the referenced page involves a write operation then for the corresponding entry in hash table the dirty bit is set and a timer is invoked which will fire an event after x seconds to synchronize the secondary memory by updating with all the changes that occurred for the page frame.

Description

Timer based Cache for Synchronization
In this invention we synchronize the disk or secondary memory with cache depending upon system architecture. For example in the case of Least Recently Used caching algorithm we are provided with total possible pages frames from secondary memory that can be referred and number of page frames that cache can hold at a time. Also we have a doubly linked list queue(cache itself) which can have nodes or page frames equal to total number of page frames possible in cache. In addition to this we have a hash table with page number as key and the address of the corresponding page frame in the cache(queue of page frames) along with the dirty bit(default value is zero) as the value. When a page is referenced, the required page may be in cache and if it is, then we need to remove the page frame in the double linked list(or queue) and bring it to the front of the queue. If the required page is not in cache we bring that in cache from secondary memory and we add a new node(or page frame) to the front of the queue and update the corresponding entry with page frame address and page frame number in the hash table. If the referenced page involves a write operation then for the corresponding entry in hash table the dirty bit is set and a timer is invoked which will fire an event after x seconds to synchronize the secondary memory by updating with all the changes that occurred for the page frame or only blocks of memory along with their addresses that have changed and reset the dirty bit value for that corresponding entry to zero. Also if another write operation happens for the same page frame within x seconds of the timer being invoked or if the dirty bit is set, then we cancel the first due timer event, finish the second write operation and reset the timer to fire an event after x seconds. Also to be able to update the secondary memory with blocks of memory along with their addresses that have changed for a particular page frame in the cache, we maintain a second hash table with page number as key and a list of block addresses that have changed in cache as value. For multiple writes within x seconds we keep on appending to the list of block addresses(duplicates will be ignored when updating) that have changes in cache for the corresponding page frame in the second hash table. When the secondary memory is updated about all the write operations which occurred for the page frame in cache then the corresponding entry for the page frame in the second hash table gets deleted.

Claims

Claims
Following is the claim for this invention: -
1> In this invention we synchronize the disk or secondary memory with cache depending upon system architecture. For example in the case of Least Recently Used caching algorithm we are provided with total possible pages frames from secondary memory that can be referred and number of page frames that cache can hold at a time. Also we have a doubly linked list queue(cache itself) which can have nodes or page frames equal to total number of page frames possible in cache. In addition to this we have a hash table with page number as key and the address of the corresponding page frame in the cache(queue of page frames) along with the dirty bit(default value is zero) as the value. When a page is referenced, the required page may be in cache and if it is, then we need to remove the page frame in the double linked list(or queue) and bring it to the front of the queue. If the required page is not in cache we bring that in cache from secondary memory and we add a new node(or page frame) to the front of the queue and update the corresponding entry with page frame address and page frame number in the hash table. If the referenced page involves a write operation then for the corresponding entry in hash table the dirty bit is set and a timer is invoked which will fire an event after x seconds to synchronize the secondary memory by updating with all the changes that occurred for the page frame or only blocks of memory along with their addresses that have changed and reset the dirty bit value for that corresponding entry to zero. Also if another write operation happens for the same page frame within x seconds of the timer being invoked or if the dirty bit is set, then we cancel the first due timer event, finish the second write operation and reset the timer to fire an event after x seconds. Also to be able to update the secondary memory with blocks of memory along with their addresses that have changed for a particular page frame in the cache, we maintain a second hash table with page number as key and a list of block addresses that have changed in cache as value. For multiple writes within x seconds we keep on appending to the list of block addresses(duplicates will be ignored when updating) that have changes in cache for the corresponding page frame in the second hash table. When the secondary memory is updated about all the write operations which occurred for the page frame in cache then the corresponding entry for the page frame in the second hash table gets deleted. The novel technique by which we synchronize the secondary memory with cache is the claim for this invention.
PCT/IB2018/050828 2018-02-11 2018-02-11 Timer based cache for synchronization Ceased WO2019155264A1 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/IB2018/050828 WO2019155264A1 (en) 2018-02-11 2018-02-11 Timer based cache for synchronization

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/IB2018/050828 WO2019155264A1 (en) 2018-02-11 2018-02-11 Timer based cache for synchronization

Publications (1)

Publication Number Publication Date
WO2019155264A1 true WO2019155264A1 (en) 2019-08-15

Family

ID=67549305

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/IB2018/050828 Ceased WO2019155264A1 (en) 2018-02-11 2018-02-11 Timer based cache for synchronization

Country Status (1)

Country Link
WO (1) WO2019155264A1 (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111078410A (en) * 2019-12-11 2020-04-28 Oppo（重庆）智能科技有限公司 Memory allocation method and device, storage medium and electronic equipment

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7234021B1 (en) * 2001-10-05 2007-06-19 Emc Corporation Methods and apparatus for accessing data elements using improved hashing techniques
US20110072196A1 (en) * 2009-09-23 2011-03-24 Lsi Corporation Cache Synchronization for Solid State Disks
CN104049918A (en) * 2014-07-03 2014-09-17 浪潮集团有限公司 Cache management method of double-control storage server

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7234021B1 (en) * 2001-10-05 2007-06-19 Emc Corporation Methods and apparatus for accessing data elements using improved hashing techniques
US20110072196A1 (en) * 2009-09-23 2011-03-24 Lsi Corporation Cache Synchronization for Solid State Disks
CN104049918A (en) * 2014-07-03 2014-09-17 浪潮集团有限公司 Cache management method of double-control storage server

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111078410A (en) * 2019-12-11 2020-04-28 Oppo（重庆）智能科技有限公司 Memory allocation method and device, storage medium and electronic equipment

Similar Documents

Publication Publication Date Title
US9639591B2 (en) Low latency replication techniques with content addressable storage
US7903665B2 (en) System and method for synchronizing packet forwarding information
US9940205B2 (en) Virtual point in time access between snapshots
WO2012172551A1 (en) Low latency replication techniques with content addressable storage
CN109800239B (en) Redis-based distributed architecture data sharing method
CN105739924B (en) Caching method and system based on cache cluster
US10082973B2 (en) Accelerated recovery in data replication environments
US11513972B2 (en) TLB device supporting multiple data streams and updating method for TLB module
US9152507B1 (en) Pruning unwanted file content from an image backup
JP2005222552A5 (en)
TW200602862A (en) Communication-link-attached persistent memory system
JP4988370B2 (en) Method, system, and program for integrating session information for a cluster of sessions in a coupled session environment
US8966200B1 (en) Pruning free blocks out of a decremental backup chain
WO2014141343A1 (en) Data multiplexing system
GB2560851A (en) Memory synchronization filter
WO2017088192A1 (en) Data backup device, method and system
US11586605B2 (en) Processing method for changing time-series database table structure
CN110442645B (en) Data indexing method and device
WO2019155264A1 (en) Timer based cache for synchronization
CN107665155B (en) Method and apparatus for processing data
WO2018119998A1 (en) Snapshot rollback method, apparatus, storage controller, and system
US8825603B2 (en) Ordering volumes and tracks for data transfer based on usage characteristics
CN118897759B (en) Data backup method, recovery method, electronic device, medium, and program product
CN106855869A (en) A kind of methods, devices and systems for realizing database High Availabitity
CN104702508A (en) Method and system for dynamically updating table items

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 18904505

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 18904505

Country of ref document: EP

Kind code of ref document: A1