99 Matching Annotations
  1. Jun 2020
    1. With this second scheme, the DBMS stores the physical addressof versions in the index entries. This approach is only applicablefor append-only storage, since the DBMS stores the versions in thesame table and therefore all of the indexes can point to them. Whenupdating any tuple in a table, the DBMS inserts the newly createdversion into all the secondary indexes. In this manner, the DBMScan search for a tuple from a secondary index without comparingthe secondary key with all of the indexed versions. Several MVCCDBMSs, including MemSQL and Hekaton, employ this scheme

      Physical Pointers: 只对Append-only storage有用

      问题:“since the DBMS stores the versions in the same table and therefore all of the indexes can point to the”这句话怎么理解

      Likewise, using physical pointers is better for read-intensive workloads because an index entry points to the exact version. But it is slower for update operations because this scheme requires theDBMS to insert an entry into every secondary index for each new version, which makes update operations slower

    2. The main idea of using logical pointers is that the DBMS usesa fixed identifier that does not change for each tuple in its indexentry. Then, as shown in Fig. 5a, the DBMS uses an indirectionlayer that maps a tuple’s identifier to the HEAD of its version chain.This avoids the problem of having to update all of a table’s indexesto point to a new physical location whenever a tuple is modifiedHEADINDEXVERSION CHAINSHEADINDIRECTION(a)Logical PointersHEADINDEXVERSION CHAINSHEAD(b)Physical PointersFigure 5: Index Management– The two ways to map keys to tuples in aMVCC are to use logical pointers with an indirection layer to the versionchain HEAD or to use physical pointers that point to an exact version.(even if the indexed attributes were not changed). Only the mappingentry needs to change each time. But since the index does not pointto the exact version, the DBMS traverses the version chain fromthe HEAD to find the visible version. This approach is compatiblewith any version storage scheme. As we now discuss, there are twoimplementation choices for this mapping

      Logical Pointers:

      logical pointer approach is better for write-intensive workloads, as the DBMS updates the secondary indexes only when a transaction modifies the indexes attributes.

    3. Tuple Id (TupleId):One drawback of thePKeypointers is thatthe database’s storage overhead increases as the size of a tuple’sprimary key increases, since each secondary index has an entirecopy of it. In addition to this, since most DBMSs use an order-preserving data structure for its primary key indexes, the cost ofperforming the additional look-up depends on the number of entries.An alternative is to use a unique 64-bit tuple identifier instead ofthe primary key and a separate latch-free hash table to maintain themapping information to the tuple’s version chain HEAD.

      Logical Pointers: TupleId

    4. Primary Key (PKey):With this, the identifier is the same as thecorresponding tuple’s primary key. When the DBMS retrieves anentry from a secondary index, it performs another look-up in thetable’s primary key index to locate the version chain HEAD. If asecondary index’s attributes overlap with the primary key, then theDBMS does not have to store the entire primary key in each entry.

      Logical Pointers: PKey

    5. Primary key indexes always point to the current version of a tuple.But how often the DBMS updates a primary key index depends onwhether or not its version storage scheme creates new versions whena tuple is updated. For example, a primary key index in the deltascheme always points to the master version for a tuple in the maintable, thus the index does not need to be updated. For append-only,it depends on the version chain ordering:N2Orequires the DBMSto update the primary key index every time a new version is created.If a tuple’s primary key is modified, then the DBMS applies this tothe index as aDELETEfollowed by anINSERT

      Index什么时候会被更新

      Example: N2O

    6. We define anindex entryas a key/value pair, where thekeyis atuple’s indexed attribute(s) and thevalueis a pointer to that tuple.The DBMS follows this pointer to a tuple’s version chain and thenscans the chain to locate the version that is visible for a transaction.The DBMS will never incur a false negative from an index, but itmay get false positive matches because the index can point to aversion for a key that may not be visible to a particular transaction.

      Index entires and false positives

    7. Since MVCC creates new versions when transactions updatetuples, the system will run out of space unless it reclaims the versionsthat are no longer needed.

      为何要进行GC

      GC在长交易不太行:The DBMS’s performance drops in the presence of long-running transactions. This is because all the versions generated during the lifetime of such a transaction cannot be removed until it completes.

    8. In this GC mechanism, the DBMS reclaims storage space attransaction-level granularity. It is compatible with all of the versionstorage schemes. The DBMS considers a transaction as expiredwhen the versions that it generated are not visible to any activetransaction. After an epoch ends, all of the versions that weregenerated by the transactions belonging to that epoch can be safely

      Transaction-level Garbage Collection:

      Downside: "however, is that the DBMS tracksthe read/write sets of transactions for each epoch instead of justusing the epoch’s membership counter"

    9. Cooperative Cleaning (COOP):When executing a transaction,the DBMS traverses the version chain to locate the visible version.During this traversal, it identifies the expired versions and recordsthem in a global data structure. This approach scales well as theGC threads no longer needs to detect expired versions, but it onlyworks for theO2Nappend-only storage. One additional challengeis that if transactions do not traverse a version chain for a particulartuple, then the system will never remove its expired versions. Thisproblem is called “dusty corners” in Hekaton [16]. The DBMSovercomes this by periodically performing a complete GC pass witha separate thread like inVAC.

      Tuple-level GC: COOP

      如果不遍历某一个chain,那么就无法GC而变成dusty corners

    10. Background Vacuuming (VAC):The DBMS uses backgroundthreads that periodically scan the database for expired versions. Asshown in Table 1, this is the most common approach in MVCCDBMSs as it is easier to implement and works with all version stor-age schemes. But this mechanism does not scale for large databases,especially with a small number of GC threads. A more scalableapproach is where transactions register the invalidated versions ina latch-free data structure [27]. The GC threads then reclaim theseexpired versions using the epoch-based scheme described above.Another optimization is where the DBMS maintains a bitmap ofdirty blocks so that the vacuum threads do not examine blocks thatwere not modified since the last GC pass

      Tuple-level GC: VAC

    11. There are two GC implementations for a MVCC that differ onhow the DBMS looks for expired versions. The first approachistuple-levelGC wherein the DBMS examines the visibility ofindividual tuples. The second istransaction-levelGC that checkswhether any version created by a finished transaction is visible

      GC的两种实现

    12. The DBMS registers each newtransaction into the active epoch and increments this counter. Whena transaction finishes, the DBMS removes it from its epoch (whichmay no longer be the current active one) and decrements this counter.If a non-active epoch’s counter reaches zero and all of the previousepochs also do not contain active transactions, then it is safe for theDBMS to reclaim expired versions that were updated in this epoch

      Epoch流程

    13. An in-memory DBMS can avoid this problem with coarse-grainedepoch-basedmemory management that tracks the versions createdby transactions [44]. There is always one active epoch and an FIFOqueue of prior epochs

      GC如何解决bottleneck:用epoch

    14. The GC process is divided into three steps: (1) detect expiredversions, (2) unlink those versions from their associated chains andindexes, and (3) reclaim their storage space. The DBMS considers aversion as expired if it is either an invalid version (i.e., created byan aborted transaction) or it is not visible to any active transaction.For the latter, the DBMS checks whether a version’send-tsisless than theTidof all active transactions. The DBMS maintainsa centralized data structure to track this information, but this is ascalability bottleneck in a multi-core system

      GC的三个步骤

      为什么end-ts比其他交易的时间戳小,那么他就对任何active的交易不可见呢?(可以从版本来理解,end-ts在最新版本里是被set成无穷的)

    15. all of the tuple versions for a table are storedin the same storage space. This approach is used in Postgres, aswell as in-memory DBMSs like Hekaton, NuoDB, and MemSQL.To update an existing tuple, the DBMS first acquires an empty slotfrom the table for the new tuple version. It then copies the contentof the current version to the new version. Finally, it applies themodifications to the tuple in the newly allocated version slot.

      Append-only Storage:

      “better for analytical queries that perform large scans because ver-sions are stored contiguously in memory, which minimizes CPUcache misses and is ideal for hardware prefetching”

      但是旧版本需要chase pointer

      同时给索引结构暴露了很多物理版本,所以可以有很多索引管理的选项

    16. With this last scheme, the DBMS maintains the master versionsof tuples in the main table and a sequence ofdelta versionsin aseparatedelta storage. This storage is referred to as therollbacksegmentin MySQL and Oracle, and is also used in HyPer. Mostexisting DBMSs store the current version of a tuple in the main table.To update an existing tuple, the DBMS acquires a continuous spacefrom the delta storage for creating a new delta version.

      Delta Storage: 有利于更新操作,因为 “This scheme is ideal forUPDATEoperations that modify a subsetof a tuple’s attributes because it reduces memory allocations”

      但是对于read intensive的工作,却有额外的overhead

    17. the older versions are stored in a separate table. TheDBMS maintain amasterversion of each tuple in the main table andmultiple versions of the same tuple in a separate time-travel table.In some DBMSs, like SQL Server, the master version is the currentversion of the tuple. Other systems, like SAP HANA, store theoldest version of a tuple as the master version to provide snapshotisolation

      Time-Travel Storage

    18. Newest-to-Oldest (N2O):The alternative is to store the newestversion of the tuple as the version chain’s HEAD (see Fig. 3b). Sincemost transactions access the latest version of a tuple, the DBMS doesnot have to traverse the chain. The downside, however, is that thechain’s HEAD changes whenever a tuple is modified. The DBMSthen updates all of the table’s indexes (both primary and secondary)to point to the new version. As we discuss in Sect. 6.1, one canavoid this problem through an indirection layer that provides a singlelocation that maps the tuple’s latest version to physical address. Withthis setup, the indexes point to tuples’ mapping entry instead of theirphysical locations. This works well for tables with many secondaryindexes but increases the storage overhead

      N2O

    19. The key decision with the append-only scheme is how the DBMSorders the tuples’ version chains. Since it is not possible to maintaina latch-free doubly linked list, the version chain only points in onedirection. This ordering has implications on how often the DBMSupdates indexes whenever transactions modify tuples.Oldest-to-Newest (O2N):With this ordering, the chain’s HEADis the oldest extant version of a tuple (see Fig. 3a). This versionmight not be visible to any active transaction but the DBMS has yetto reclaim it. The advantage ofO2Nis that the DBMS need notupdate the indexes to point to a newer version of the tuple wheneverit is modified. But the DBMS potentially traverses a long versionchain to find the latest version during query processing. This is slowbecause of pointer chasing and it pollutes CPU caches by readingunneeded versions. Thus, achieving good performance withO2Nishighly dependent on the system’s ability to prune old versions

      O2N

    20. thechain’s HEAD is either the newest or oldest version

      Version Storage: head of chain

    21. A transaction can commit only when all ofthe transactions that it depends on have committed.

      eagerly update

    22. Atransaction is allowed to commit only when its dependency counteris zero, whereupon the DBMS traverses its dependency list anddecrements the counters for all the transactions that are waitingfor it to finish.

      speculative read uncommitted

    23. The serial safety net (SSN) is a newer certifier-based proto-col [45]. Unlike withSSI, which is only applicable to snapshotisolation,SSNworks with any isolation level that is at least as strongasREAD COMMITTED. It also uses a more more precise anomaly de-tection mechanism that reduces the number of unnecessary aborts.SSNencodes the transaction dependency information into meta-data fields and validates a transactionT’s consistency by computinga low watermark that summarizes “dangerous” transactions thatcommitted before theTbut must be serialized afterT[45]. Re-ducing the number of false aborts makesSSNmore amenable toworkloads with read-only or read-mostly transactions

      Serialization Certifier: SSN -- 利于只读/Read-mostly的交易

    24. the DBMS maintains a serialization graphfor detecting and removing “dangerous structures” formed by con-current transactions

      Serialization Certifier

    25. When a transaction commits, the DBMSassigns it a unique timestamp (Tcommit) that is used to update thebegin-tsfield for the versions created by that transaction and thenreleases all of the transaction’s locks.

      MV2PL: when to release locks

    26. Similarly, atransaction is allowed to update a versionBxonly if bothread-cntandtxn-idare set to zero

      MV2PL: when can update

    27. To perform a read operation on a tupleA, the DBMS searches fora visible version by comparing a transaction’sTidwith the tuples’begin-tsfield. If it finds a valid version, then the DBMS incre-ments that tuple’sread-cntfield if itstxn-idfield is equal to zero(meaning that no other transaction holds the write lock)

      MV2PL: when can read

    28. The tuple’swrite lockis thetxn-idfield. For theread lock, the DBMS usesaread-cntfield to count the number of active transactions thathave read the tuple. Although it is not necessary, the DBMS canpacktxn-idandread-cntinto contiguous 64-bit word so that theDBMS can use a single CaS to update them at the same time

      MV2PL: 锁同样大小所以单个CAS就可以执行更新

    29. This protocol uses the two-phase locking (2PL) method [11] toguarantee the transaction serializability. Every transaction acquiresthe proper lock on the current version of logical tuple before it isallowed to read or modify it.

      MV2PL

    30. But atransaction cannot read a new version until the other transaction thatcreated it commits. A transaction that reads an outdated version willonly find out that it should abort in the validation phase

      MVOCC: when cannot read

    31. If the transaction passes these checks, it then enters thewrite phasewhere the DBMS installs all the new versions and setstheirbegin-tstoTcommitandend-tstoINF

      Write Phase of MVOCC: end-ts initialized to INF

    32. When a transaction instructs the DBMS that it wants to commit,it then enters thevalidation phase. First, the DBMS assigns thetransaction another timestamp (Tcommit) to determine the serializationorder of transactions. The DBMS then determines whether the tuplesin the transaction’s read set was updated by a transaction that alreadycommitted.

      Validation Phase of MVOCC

    33. TheMVOCCprotocol splits a transaction into three phases.When the transaction starts, it is in theread phase. This is where thetransaction invokes read and update operations on the database. LikeMVTO, to perform a read operation on a tupleA, the DBMS firstsearches for a visible versionAxbased onbegin-tsandend-tsfields.Tis allowed to update versionAxif its write lock is not ac-quired. In a multi-version setting, if the transaction updates versionBx, then the DBMS creates versionBx+1with itstxn-idset toTid

      Read Phase of MVOCC: read operation & creation of new versions

    34. The motivation behind OCCis that the DBMS assumes that transactions are unlikely to conflict,and thus a transaction does not have to acquire locks on tuples whenit reads or updates them.

      MVOCC: optimistic about the conflict

    35. WithMVTO, a transaction always updates the latest version ofa tuple. TransactionTcreates a new versionBx+1if (1) no activetransaction holdsBx’s write lock and (2)Tidis larger thanBx’sread-tsfield. If these conditions are satisfied, then the DBMScreates a new versionBx+1and sets itstxn-idtoTid. WhenTcommits, the DBMS setsBx+1’sbegin-tsandend-tsfields toTidandINF(respectively), andBx’send-tsfield toTid

      MVTO: update create new version based on two conditions and update the begin-ts field on commit

    36. Upon readingAx, the DBMS setsAx’sread-tsfield toTidif its current value is less thanTid. Otherwise, the transaction readsan older version without updating this field

      MVCC: after read

    37. When transactionTinvokes a read operation on logical tupleA,the DBMS searches for a physical version whereTidis in betweenthe range of thebegin-tsandend-tsfields

      MVTO: when can read

    38. The crux ofthis approach is to use the transactions’ identifiers (Tid) to pre-compute their serialization order. In addition to the fields describedin Sect. 2.2, the version headers also contain the identifier of the lasttransaction that read it (read-ts). The DBMS aborts a transactionthat attempts to read or update a version whose write lock is held byanother transaction.

      MVTO:记录上一个交易读操作的时间戳

    39. Existing approachesto provide serializable transaction processing use either (1) addi-tional latches in the index [35, 44] or (2) extra validation steps whentransactions commit [27].

      有一点像乐观/悲观的Approaches

    40. Every DBMS includes aconcurrency control protocolthat coor-dinates the execution of concurrent transactions [11]. This protocoldetermines (1) whether to allow a transaction to access or modify aparticular tuple version in the database at runtime, and (2) whether toallow a transaction to commit its modifications.

      并发控制

    41. Tuples:As shown in Fig. 1, each physical version contains fourmeta-data fields in its header that the DBMS uses to coordinatethe execution of concurrent transactions (some of the concurrencycontrol protocols discussed in the next section include additionalfields). Thetxn-idfield serves as the version’s write lock. Everytuple has this field set to zero when the tuple is not write-locked.Most DBMSs use a 64-bittxn-idso that it can use a single compare-and-swap (CaS) instruction to atomically update the value. If atransactionTwith identifierTidwants to update a tupleA, then theDBMS checks whetherA’stxn-idfield is zero. If it is, then DBMSwill set the value oftxn-idtoTidusing a CaS instruction [27, 44].begin-tscolumnsContentHeadertxn-idend-ts...pointerFigure 1: Tuple Format– The basic layout of a physical version of a tuple.Any transaction that attempts to updateAis aborted if thistxn-idfield is neither zero or not equal to itsTid. The next two meta-datafields are thebegin-tsandend-tstimestamps that represent thelifetime of the tuple version. Both fields are initially set to zero. TheDBMS sets a tuple’sbegin-tstoINFwhen the transaction deletesit. The last meta-data field is thepointerthat stores the address ofthe neighboring (previous or next) version (if any)
    42. Transactions:The DBMS assigns a transactionTa unique,monotonically increasing timestamp as its identifier (Tid) whenthey first enter the system. The concurrency control protocols usethis identifier to mark the tuple versions that a transaction accesses.Some protocols also use it for the serialization order of transactions

      每一个交易都要有一个时间戳

    43. Foremost is that it canpotentially allow for greater concurrency than a single-version sys-tem.

      优点1:更加并发,相比与单版本系统

      读查询可以查阅历史版本,读写查询可以继续更新对象。

      如果旧版本不被移除,甚至可以“时间旅行”😂

    44. This is especially true for in-memory DBMSswhere disk is no longer the main bottleneck

      印证了之前的bottleneck

    45. A transaction management scheme permits end-users to access adatabase in a multi-programmed fashion while preserving the illu-

      让用户以为每一个程序都在单独执行:

      Atomicity和Isolation原则

    46. this previous work does not reflect recent trends in latch-free [27] and serializable [20] concurrency control, as well as in-memory storage [36] and hybrid workloads [40]

      过去的研究没有考虑的问题,因为disk-oriented的overhead主要是读写,而in-memory的overhead在于以上几方面

    47. Multi-versioning allows read-only transactionsto access older versions of tuples without preventing read-writetransactions from simultaneously generating newer versions.

      一般来讲更新操作会实时地override原有的tuple

    48. but almost every MVCC DBMS uses tuples because itprovides a good balance between parallelism versus the overheadof version tracking
    49. Thebasic idea of MVCC is that the DBMS maintains multiple physicalversions of each logical object in the database to allow operations onthe same object to proceed in parallel.

      How to make sure different physical copies are in sync?

  2. May 2020
  3. Apr 2020
    1. le « devenir-animal » de l’humain

      hum j'aurai besoin d'une rapide définition

    2. devenir humain

      Il faudrait que tu expliques en quelques mots (genre une parenthèse) ce que tu entends par cette expression de devenir humain

  4. Jul 2019
    1. In a simple linear regression model, we model the relationship between both variables by a straight line, formally

      It would be better to start in the following way: "To build simple linear regression model, we hypothesize that the relationship between dependent and independent variable is linear, formally:"

      By saying that, In a simple linear regression model, we model the relationship between both variables by straight line is strictly speaking wrong. Strictly speaking, by straight line we model the relationship between regressors the expected value of the dependent variable given the value of the regressors.

      Then later, you point out that the relationship is not exact because not all points fall on the straight line and because of that you come up with an error terms and you continue in this way util you arrive to the final formulation of the Simple Linear Regression Model. (Which you do well later).

    1. Job says: “The ear trieth words, as the mouth tasteth meat.
    2. the universe, including man and his divine Principle, is harmonious and eternal.
    3. 1. God is All in all. 2. God is good. Good is Mind. 3. God, Spirit, being all, nothing is matter. 4. Life, God, omnipotent Good, deny death, evil, sin, disease. — Disease, sin, evil, death, deny Good, omnipotent God, Life.
    4. The vital part, the heart and Soul of Christian Science, is Love.
    5. there is no pain in Truth, and no truth Inversions. in pain; no nerve in Mind, and no mind in nerve; no matter in Mind, and no mind in matter; no matter in Life, and no life in matter; no matter in Good, and no good in matter.
    6. The Principle of Divine Metaphysics is God; its practice is the power of Truth over error; its rules demonstrate Science.
    7. the awful unreality called evil.
    8. omnipotence, omnipresence, omniscience, — Spirit possessing all power, God's allness learned. filling all space, constituting all Science
    9. I knew the Principle of all harmonious Mind-action to be God
    10. the only realities are the divine Mind Scientific evidence. and idea.
    11. this same mind calls matter, thereby shutting out the true sense of Spirit.
    12. the opposite of Truth — called error, sin, sickness, disease, death — is the false testimony of false material sense; that this false sense evolves, in belief, a subjective state of mortal mind, which this same mind calls matter, thereby shutting out the true sense of Spirit.
    13. Life, Truth, and Love are all-powerful and ever-present
    14. Feeling so perpetually the false consciousness that life inheres in the body, yet remembering that God is A divine discontent. really our Life, we may well tremble, in the prospect of those days wherein we must say, “I have no pleasure in them.”
    15. the revelation of Immanuel, the everpresent God
    16. the demonstrable fact that matter possesses neither sensation nor life;
    17. all real Being is in the divine Mind and idea
  5. Mar 2019
    1. This is a reasonable list of Knowles' assumptions about adult learners -- not as complete or nuanced as one might find in a textbook, but worth having a look at when starting a new project. rating: 3/5

  6. Aug 2018
    1. The sideboard is stylish and dramatic, but it is also quite appropriate for use in a dining room

      digital "side"-demands asks for side storage

  7. Jul 2017
    1. Because it is so important to be seen as competent and productive members of society, people naturally attempt to present themselves to others in a positive light. We attempt to convince others that we are good and worthy people by appearing attractive, strong, intelligent, and likable and by saying positive things to others (Jones & Pittman, 1982; Schlenker, 2003). The tendency to present a positive self-image to others, with the goal of increasing our social status, is known as self-presentation, and it is a basic and natural part of everyday life.

      A short film captures how social interactions influence our complex relationships between self-presentation, self-esteem and self concept in a unique way.

  8. Jun 2017
  9. Nov 2015
    1. I see using the LPP lens to identify the types of participation,how they influence learningand the coproduction of the “learning curriculum”that newcomersand oldtimers engage with in regulating and producing the local “community of practice”thatis the robotics club. Within this I aim to also investigate what physical, and non-physical resources studentshave for participationwithin this community(Nasir, et al., 2008). This an

      You clearly map the trajectory of your paper based on the concepts we learned. Your analytical lens is very clear to me as I understand the concepts in the same way you use them. It's like a concept map, how you linked the ideas.

  10. Feb 2014
    1. Concepts seem to be structurable, in that a new concept can be composed of an organization of established concepts. For present purposes, we can view a concept structure as something which we might try to develop on paper for ourselves or work with by conscious thought processes, or as something which we try to communicate to one another in serious discussion. We assume that, for a given unit of comprehension to be imparted, there is a concept structure (which can be consciously developed and displayed) that can be presented to an individual in such a way that it is mapped into a corresponding mental structure which provides the basis for that individual's "comprehending" behavior. Our working assumption also considers that some concept structures would be better for this purpose than others, in that they would be more easily mapped by the individual into workable mental structures, or in that the resulting mental structures enable a higher degree of comprehension and better solutions to problems, or both.
  11. Nov 2013
    1. schema

      definition: • (in Kantian philosophy) a conception of what is common to all members of a class; a general or essential type or form.

    2. We obtain the concept, as we do the form, by overlooking what is individual and actual; whereas nature is acquainted with no forms and no concepts, and likewise with no species, but only with an X which remains inaccessible and undefinable for us.

      That which is beyond rhetoric is beyond our conceptual reach

    3. In particular, let us further consider the formation of concepts. Every word instantly becomes a concept precisely insofar as it is not supposed to serve as a reminder of the unique and entirely individual original experience to which it owes its origin;

      words are concepts and conceptual

    4. That is to say, this conceptual edifice is an imitation of temporal, spatial, and numerical relationships in the domain of metaphor.

      Interesting.

    5. Bees construct a physical world and man constructs a conceptual world.

    6. We obtain the concept, as we do the form, by overlooking what is individual and actual
    7. Every concept arises from the equation of unequal things.
    8. dissolve an image into a concept.

      Do we lose something in this dissolution?

    9. A concept becomes a word based on its relationship to other cases.