Re: [HACKERS] Guidelines for GSoC student proposals / Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Thanks, I've updated the proposal. Just one issue: I agree that we can make skip list a general data structure. But can we use the fixed-level skip list as a Plan B? Or a quick attempt before the general data structure ? Because I am not familiar with shared memory structure and tricks used in it, and I cannot estimate how much time it would take. > -Original Messages- > From: "Kevin Grittner" <kgri...@gmail.com> > Sent Time: 2017-03-28 00:16:11 (Tuesday) > To: "Mengxing Liu" <liu-m...@mails.tsinghua.edu.cn> > Cc: "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > Subject: Re: [HACKERS] Guidelines for GSoC student proposals / Eliminate > O(N^2) scaling from rw-conflict tracking in serializable transactions > > On Sat, Mar 25, 2017 at 9:24 PM, Mengxing Liu > <liu-m...@mails.tsinghua.edu.cn> wrote: > > > I've updated the proposal according to your comments. > > But I am still wondering that can you review it for a double-check > > to make sure I've made everything clear? > > Additional comments added. > > I'm afraid a few new issues came to mind reading it again. (Nothing > serious; just some points that could benefit from a little > elaboration.) > > -- > Kevin Grittner > > > -- > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Guidelines for GSoC student proposals / Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Thanks for your time. I've updated the proposal according to your comments. But I am still wondering that can you review it for a double-check to make sure I've made everything clear? You can read my replies for reference. > -Original Messages- > From: "Kevin Grittner" <kgri...@gmail.com> > Sent Time: 2017-03-25 04:53:36 (Saturday) > To: "Mengxing Liu" <liu-m...@mails.tsinghua.edu.cn> > Cc: "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > Subject: Re: [HACKERS] Guidelines for GSoC student proposals / Eliminate > O(N^2) scaling from rw-conflict tracking in serializable transactions > > On Wed, Mar 22, 2017 at 2:24 AM, Mengxing Liu > <liu-m...@mails.tsinghua.edu.cn> wrote: > > > I've finished a draft proposal for "Eliminate O(N^2) scaling from > > rw-conflict tracking in serializable transactions". > > I've attached some comments to the document; let me know if they > don't show up for you or you need clarification. > > Overall, if the comments are addressed, I think it is great. > > -- > Kevin Grittner -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
> -Original Messages- > From: "Kevin Grittner" <kgri...@gmail.com> > Sent Time: 2017-03-15 23:20:07 (Wednesday) > To: DEV_OPS <dev...@ww-it.cn> > Cc: "Mengxing Liu" <liu-m...@mails.tsinghua.edu.cn>, > "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > Subject: Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from > rw-conflict tracking in serializable transactions > > On Tue, Mar 14, 2017 at 3:45 PM, Kevin Grittner <kgri...@gmail.com> wrote: > >> On 3/14/17 17:34, Mengxing Liu wrote: > >>> There are several alternative benchmarks. Tony suggested that we > >>> should use TPC-E and TPC-DS. > > > > More benchmarks is better, all other things being equal. Keep in > > mind that good benchmarking practice with PostgreSQL generally > > requires a lot of setup time (so that we're starting from the exact > > same conditions for every run), a lot of run time (so that the > > effects of vacuuming, bloat, and page splitting all comes into play, > > like it would in the real world), and a lot of repetitions of each > > run (to account for variation). In particular, on a NUMA machine it > > is not at all unusual to see bifurcated > > Sorry I didn't finish that sentence. > > On a NUMA machine It is not at all unusual to see bifurcated results > -- with each run coming in very close to one number or a second > number, often at about a 50/50 rate, with no numbers falling > anywhere else. This seems to be based on where the processes and > memory allocations happen to land. > Do you mean that for a NUMA machine, there usually exists two different results of its performance? Just two? Neither three nor four? Anyway, firstly, I think I should get familiar with PostgreSQL and tools you recommended to me at first. Then I will try to have a better comprehension about it, to make our discussion more efficient. Recently, I am busy preparing for the presentation at ASPLOS'17 and other lab works. But I promise I can finish all preparation works before May. Here is my working plan: At first, I will compile and install PostgreSQL by myself and try the profile tools (perf or oprofile). Then I will run one or two benchmarks using different config, where I may need your help to ensure that my tests are close to the practical situation. PS: Disable NUMA in BIOS means that CPU can use its own memory controller when accessing local memory to reduce hops. On the contrary, "enable" means UMA. Therefore, I think Tony is right, we should disable this setting. I got the information from here. http://frankdenneman.nl/2010/12/28/node-interleaving-enable-or-disable/ Regards. -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Guidelines for GSoC student proposals / Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi, Kevin. I've finished a draft proposal for "Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions". You can find it from GSOC website or by the link below. https://docs.google.com/document/d/17TAs3EJIokwPU7UTUmnlVY3ElB-VHViyX1zkQJmrD1A/edit?usp=sharing I was wondering if you have time to review the proposal and give me some comments? > -Original Messages- > From: "Kevin Grittner" <kgri...@gmail.com> > Sent Time: 2017-03-17 21:57:18 (Friday) > To: "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > Cc: > Subject: [HACKERS] Guidelines for GSoC student proposals > > I've found various sources that give hints about what a student > proposal should look like, but nothing I could just give as a link, > so I pulled together what I could find, tempered by my own ideas and > opinions. I suggest that we send the below, or something like it to > each student who expresses interest in making a proposal, or who > submits a proposal that doesn't meet the below guidelines. Thoughts > or suggestions for changes before we do? Remember, time is short, > so this cannot be a 200 message bike-shedding debate -- we just need > to provide some sort of guidance to students in a timely way, with > the timeline being: > > February 27 - March 20 > Potential student participants discuss application ideas with > mentoring organizations > March 20 16:00 UTC > Student application period opens > April 3 16:00 UTC > Student application deadline > > Each GSoC student proposal should be a PDF file of 6 to 8 pages. In > the end, Google will publish these documents on a web page, so the > student should make each proposal something which they will be happy > to have future potential employers review. > > Some ideas for desirable content: > > - A resume or CV of the student, including any prior GSoC work > - Their reasons for wanting to participate > - What else they have planned for the summer, and what their time > commitment to the GSoC work will be > - A clear statement that there will be no intellectual property > problems with the work they will be doing -- that the PostgreSQL > community will be able to use their work without encumbrances > (e.g., there should be no agreements related to prior or > ongoing work which might assign the rights to the work they do > to someone else) > - A description of what they will do, and how > - Milestones with dates > - What they consider to be the test that they have successfully > completed the project > > Note that a student proposal is supposed to be far more detailed > than the ideas for projects provided by the organization -- those > are intended to be ideas for what the student might write up as a > proposal, not ready-to-go proposal documents. > > > -- > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Guidelines for GSoC student proposals / Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
> > I agree that we can make skip list a general data structure. But > > can we use the fixed-level skip list as a Plan B? Or a quick attempt > > before the general data structure ? > > Because I am not familiar with shared memory structure and tricks > > used in it, and I cannot estimate how much time it would take. > > It's not really too bad for fixed allocation shared memory, and I > can help with that. If I thought it would save much I could see > doing a prototype without generalization, but you would still have > most of the same shared memory issues, since the structure *must* > live in shared memory. > Thank you. If there is no other problem, I will submit the proposal. -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
I send this email to Tony, too. Because he promised to help me with testing and benchmarking. > > >> The worst problems have been > >> seen with 32 or more cores on 4 or more sockets with a large number > >> of active connections. I don't know whether you have access to a > >> machine capable of putting this kind of stress on it (perhaps at > >> your university?), but if not, the community has access to various > >> resources we should be able to schedule time on. > > > > There is a NUMA machine ( 120 cores, 8 sockets) in my lab. > > Fantastic! Can you say a bit more about the architecture and OS? > Intel(R) Xeon(R) CPU at 2.3GHz, with 1TB physical DRAM and 1.5 TB SSD, running Ubuntu 14.04, Kernel 3.19. I guess NUMA is disabled in BIOS, but I will check that. However, there is only one NIC, so network could be the bottleneck if we use too many cores? > > I think it's enough to put this kind of stress. > > The researchers who saw this bottleneck reported that performance > started to dip at 16 cores and the problem was very noticeable at 32 > cores. A stress test with 120 cores on 8 sockets will be great! > > I think perhaps the first milestone on the project should be to > develop a set of benchmarks we want to compare to at the end. That > would need to include a stress test that clearly shows the problem > we're trying to solve, along with some cases involving 1 or two > connections -- just to make sure we don't harm performance for > low-contention situations. > Thank for your advice! It's really helpful for my proposal. There are several alternative benchmarks. Tony suggested that we should use TPC-E and TPC-DS. Personally, I am more familiar with TPC-C. And pgbench seems only have TPC-B built-in benchmark. Well, I think we can easily find the implementations of these benchmarks for PostgreSQL. The paper you recommended to me used a special benchmark defined by themselves. But it is quite simple and easy to implement. For me, the challenge is profiling the execution. Is there any tools in PostgreSQL to analysis where is the CPU cycles consumed? Or I have to instrument and time by myself? Regards. -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
> -Original Messages- > From: "Kevin Grittner" <kgri...@gmail.com> > Sent Time: 2017-03-12 04:24:29 (Sunday) > To: "Mengxing Liu" <liu-m...@mails.tsinghua.edu.cn> > Cc: "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > Subject: Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in > serializable transactions > > On Fri, Mar 10, 2017 at 9:12 PM, Mengxing Liu > <liu-m...@mails.tsinghua.edu.cn> wrote: > > > My name is Mengxing Liu. I am interested in the project "Eliminate > > O(N^2) scaling from rw-conflict tracking in serializable > > transactions”. After discussing with Kevin off-list, I think it's > > time to post discussion here. I am afraid that there are two things > > that I need your help. Thank you very much. > > Welcome to the -hackers list! This is a key part of how development > happens in the community. Don't be shy about posting questions and > ideas, but also expect fairly blunt discussion to occur at times; > don't let that put you off. > Thanks, Kevin. I will keep that in mind. > >>> So the task is clear. We can use a tree-like or hash-like data > >>> structure to speed up this function. > >> > >> Right -- especially with a large number of connections holding a > >> large number of conflicts. In one paper with high concurrency, they > >> found over 50% of the CPU time for PostgreSQL was going to these > >> functions (including functions called by them). This seems to me to > >> be due to the O(N^2) (or possibly worse) performance from the number > >> of connections. > > > > Anyone knows the title of this paper? I want to reproduce its > > workloads. > > I seem to remember there being a couple other papers or talks, but > this is probably the most informative: > > http://sydney.edu.au/engineering/it/research/tr/tr693.pdf > Thanks, It's exactly what I need. > >> Remember, I think most of the work here is going to be in > >> benchmarking. We not only need to show improvements in simple test > >> cases using readily available tools like pgbench, but think about > >> what types of cases might be worst for the approach taken and show > >> that it still does well -- or at least not horribly. It can be OK > >> to have some slight regression in an unusual case if the common > >> cases improve a lot, but any large regression needs to be addressed > >> before the patch can be accepted. There are some community members > >> who are truly diabolical in their ability to devise "worst case" > >> tests, and we don't want to be blind-sided by a bad result from one > >> of them late in the process. > >> > > > > Are there any documents or links introducing how to test and > > benchmark PostgreSQL? I may need some time to learn about it. > > There is pgbench: > > https://www.postgresql.org/docs/devel/static/pgbench.html > > A read-only load and a read/write mix should both be tested, > probably with a few different scales and client counts to force the > bottleneck to be in different places. The worst problems have been > seen with 32 or more cores on 4 or more sockets with a large number > of active connections. I don't know whether you have access to a > machine capable of putting this kind of stress on it (perhaps at > your university?), but if not, the community has access to various > resources we should be able to schedule time on. > There is a NUMA machine ( 120 cores, 8 sockets) in my lab. I think it's enough to put this kind of stress. Anyway, I would ask for help if necessary. > It may pay for you to search through the archives of the last year > or two to look for other benchmarks and see what people have > previously done. > I would try. -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GSOC Introduction / Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi George, I am Mengxing Liu. Happy to meet someone with the same idea : ) I have been concentrating on it for a long time, reading papers, reading source codes, and discussing details with Mr Grittner. So I really understand your passion on it. But definitely I don't want all these effects to be in vain. So, maybe a little ruthless, would you mind to consider transferring to the other one? > -原始邮件- > 发件人: "Kevin Grittner" <kgri...@gmail.com> > 发送时间: 2017-03-10 22:57:03 (星期五) > 收件人: "George Papadrosou" <gpapadro...@gmail.com>, "刘梦醒" > <liu-m...@mails.tsinghua.edu.cn> > 抄送: "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > 主题: Re: [HACKERS] GSOC Introduction / Eliminate O(N^2) scaling from > rw-conflict tracking in serializable transactions > > [including Mengxing Liu in response, for reasons that should become > obvious below...] > > Hi George, > > On Thu, Mar 9, 2017 at 6:49 PM, George Papadrosou <gpapadro...@gmail.com> > wrote: > > > my name is George Papadrosou, this is my first semester as > > graduate student at Georgia Tech and would like to submit a > > proposal to Google Summer of Code, for the project "Eliminate > > O(N^2) scaling from rw-conflict tracking in serializable > > transactions”. > > I was recently contacted off-list by Mengxing Liu, who has been > looking at the same project, and said he was planning to submit a > GSoC proposal. Rather than have one of you sit this out, do either > of you feel comfortable taking a different project instead? Since > you've both been looking at the serializable code and supporting > documents, perhaps one of you could change to the other suggested > Serializable project? > > > I am going to prepare a draft proposal for this project and share > > it with you soon. The project’s description is pretty clear, do > > you think it should be more strictly defined in the proposal? > > At a minimum, the proposal should include list of milestones you > expect to reach along the way, and a timeline indicating when you > expect to reach them. Some description of the benchmarks you intend > to run would be also be very good. > > > Until then, I would like to familiarize myself a bit with the > > codebase and fix some bug/todo. I didn’t find many [E] marked > > tasks in the todo list so the task I was thinking is "\s without > > arguments (display history) fails with libedit, doesn't use pager > > either - psql \s not working on OSX”. However, it works on my OSX > > El Capitan laptop with Postgres 9.4.4. Would you suggest some > > other starter task? > > There is a CommitFest in progress; reviewing patches is a good way > to become involved and familiar with the community processes. > > https://wiki.postgresql.org/wiki/CommitFest > > -- > Kevin Grittner -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi, all My name is Mengxing Liu. I am interested in the project "Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions”. After discussing with Kevin off-list, I think it's time to post discussion here. I am afraid that there are two things that I need your help. Thank you very much. > > > So the task is clear. We can use a tree-like or hash-like data > > structure to speed up this function. > > Right -- especially with a large number of connections holding a > large number of conflicts. In one paper with high concurrency, they > found over 50% of the CPU time for PostgreSQL was going to these > functions (including functions called by them). This seems to me to > be due to the O(N^2) (or possibly worse) performance from the number > of connections. Anyone knows the title of this paper? I want to reproduce its workloads. > > Remember, I think most of the work here is going to be in > benchmarking. We not only need to show improvements in simple test > cases using readily available tools like pgbench, but think about > what types of cases might be worst for the approach taken and show > that it still does well -- or at least not horribly. It can be OK > to have some slight regression in an unusual case if the common > cases improve a lot, but any large regression needs to be addressed > before the patch can be accepted. There are some community members > who are truly diabolical in their ability to devise "worst case" > tests, and we don't want to be blind-sided by a bad result from one > of them late in the process. > Are there any documents or links introducing how to test and benchmark PostgreSQL? I may need some time to learn about it. Thanks. -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GOSC' 17][Performance report] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi, all. I wrote a performance report to conclude what I've done so far. https://docs.google.com/document/d/16A6rfJnQSTkd0SHK-2XzDiLj7aZ5nC189jGPcfVdhMQ/edit?usp=sharing Three patch are attached. I used the benchmark below to test the performance. https://github.com/liumx10/pg-bench It requires golang (>= 1.6) if you want to reproduce the code. NOTE: 1. The reason why hash table or skip list didn't improve the performance is that maintaining the conflict list became slower even though conflict tracking was faster. So far, skip list is the most promising way. But the code is a little tricky. BTW, if there is a case in which inserting an conflict element is rare but conflict checking is common, my patch may be better. 2. Reducing contention on global lock has a better performance in this evaluation. But two weeks ago when I used another machine, it has a worse performance. It's hard to explain why... You can reply directly if you have any questions or comments. -- Sincerely Mengxing Liu HTAB-for-conflict-tracking.patch Description: Binary data skip-list-for-conflict-tracking.patch Description: Binary data reduce-contention-on-FinishedListLock.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Re: [GSOC][weekly report 9] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
In the last week, I tried these two ideas. > -Original Messages- > From: "Alvaro Herrera" <alvhe...@2ndquadrant.com> > Sent Time: 2017-08-08 01:51:52 (Tuesday) > * I wonder if a completely different approach to the finished xact > maintenance problem would be helpful. For instance, in > ReleasePredicateLocks we call ClearOldPredicateLocks() > inconditionally, and there we grab the SerializableFinishedListLock > lock inconditionally for the whole duration of that routine, but > perhaps it would be better to skip the whole ClearOld stuff if the > SerializableFinishedListLock is not available? Find out some way to > ensure that the cleanup is always called later on, but maybe skipping > it once in a while improves overall performance. > I implemented the idea by this way: using LWLockConditionalAcquire instead of LWLockAcquire. If the lock is held by others, just return. It's OK because the routine is used to clear old predicate locks but it doesn't matter who does the job. But we both ignored one thing: this idea doesn't speedup the releasing operation. It just avoids some processes waiting for the lock. If the function ClearOldPredicateLocks is the bottleneck, skipping doesn't help anymore. I attached the result of evaluation. This idea ( conditional lock) has the worst performance. > > * the whole predicate.c stuff is written using SHM_QUEUE. I suppose > SHM_QUEUE works just fine, but predicate.c was being written at about > the same time (or a bit earlier) than the newer ilist.c interface was > being created, which I think had more optimization work thrown in. > Maybe it would be good for predicate.c to ditch use of SHM_QUEUE and > use ilist.c interfaces instead? We could even think about being less > strict about holding exclusive lock on SerializableFinished for the > duration of ClearOldPredicateLocks, i.e. use only a share lock and > only exchange for exclusive if a list modification is needed. > I used the double linked list in ilist.c but it didn't improve the performance. I did a micro benchmark to compare the performance of SHM_QUEUE & ilist.c and didn't find any difference. So the result is reasonable. But there is a voice to get rid of SHM_QUEUE because it does not make sense to have two same implementations. What's your opinion? > -- > Álvaro Herrerahttps://www.2ndQuadrant.com/ > PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services -- Sincerely Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GSOC][weekly report 6] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
In the last week: 1) I tried to find out what's wrong with my last patch: reducing the contention on SerializableFinishedListLock. 2) I used a skip list to replace the linked list to speedup conflict tracking. But there are still some bugs resulting in segment fault. Here is the code: https://github.com/liumx10/postgresql/commit/c469e14e27c31edba5caff001647440040f53c84 I will figure it out in the next days. Here is the details. 1) Reducing the contention on SerializableFinishedListLock In the last email, I reported that reducing the contention on FinishedListLock didn't increase the performance. The system became even slower in some cases. I thought the key point was not the problem of my codes. The original Pseudo code looks like this: lockAcquire(SerializableFinishedListLock) for predlock in this Sxact: lockAcquire(patitionlock); // do something; unlock(paritionlock); releaseAcquire(SerializableFinishedListLock) SerializableFinishedListLock likes a coarse-grained lock, while partition locks like fine-grained lock. My patch essentially remove the outer lock. But unfortunately, there are many other places requiring partition locks. We have only 16 partition locks in all. So even without SerializableFinishedListLock, contentions will happen on partition locks. The performance wouldn't be improved. Why the performance became worse in some cases? Context switch may be one of the reason. It was easier to fail on getting locks when using fine-grained locks, which would hang the current process and result in a context switch. For example, if it failed to get partition locks 5 times in a for loop, there would be 5 context switch at least. I used vmstat to count the context switch. In the benchmark where my patch had a worse performance, there were more context switch happened than using the original code. I also modify the source code to count where requiring partition locks failed. In the original version, only a few (no more than 1%) locking failure came from the pseudo code above. But in my patch, more than 50% failure came from this part. 2) Skip list To make it simple, I didn't develop an independent data structure for skip list. Instead, I used two linked list to simulate skip list. Most transactions have no more than 50 conflicts, so two level skip list is enough now. I'll make a clean patch after I figure out bugs. -- Sincerely Mengxing Liu
[HACKERS] [GSOC][weekly report 5] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Sorry for report late. Our lab's machines crashed for several days. As I reported in the last email, https://www.postgresql.org/message-id/5b6b452.16851.15cf1ec010e.coremail.liu-m...@mails.tsinghua.edu.cn I tried to decrease the contention on SerializableFinishedListLock. It works actually. But I don't know why my optimization results in another problems: more contention on PREDICATELOCK_MANAGER_LWLOCK. Here is the result of statistics collector. There were 36 connections in all, so most of them are waiting for locks. (benchmark is ssibench, but other benchmarks have the same result) Original: SerializableXactHashLock, 0.36 predicate_lock_manager, 6.00 wal_insert, 0.07 SerializableFinishedListLock, 16.50 After optimization: SerializableXactHashLock, 0.35 predicate_lock_manager, 11.53 buffer_content, 0.12 SerializableFinishedListLock, 11.47 So in the end, the performance did not change obviously. Even if I enlarged the number of predicate locks (NUM_PREDICATELOCK_PARTITIONS) from 16 to 1024, there were still so many contentions. It bothered me for several days. The patch is attached. To focus on this issue, I removed other parts of modification. Do you have any advices for this ? -- Sincerely Mengxing Liu finishedlock.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GSOC][weekly report 7] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
In the last week, I focus on 1) Creating an independent skip list data structure and related interfaces. Now it has only two levels so that I don't have to modify too much existing code. But it is easy to be transformed into the data structure with any number of levels if necessary. Unfortunately, its performance is not good. In some cases, it's only 1/2 of original version. It reminded me that even conflict-tracking didn't consume too much CPU time, it was on the critical path and wrapped by a pair of lock acquiring and releasing. Slower conflicts tracking would result in more lock contentions, which would make the performance drop quickly. 2) Using some tricks to improve its performance. For example, I found if the length of the conflict list is smaller than 10, the original linked list is faster than the skip list. So I used it in a hybrid way: if the total conflicts are more than 10, using skip list; otherwise using linked list. Now, the performance is approximately equal to the original version in different benchmarks. But I don't found a case in which the new version is much faster. The patch is attached. So far, I have tried: 1) using hash table for conflict tracking. 2) reducing the global lock contention 3) using skip list for conflict tracking. But all of them did not improve the performance. So I'm a little confused now about what to do next. Could you please give me any suggestions? -- Sincerely Mengxing Liu skip-list-for-conflict-tracking.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GSOC] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi, all. There was a very strange phenomenon I couldn't explain. So I was
wondering if you can help me.
I was trying to replace the linked list with a skip list in serializable
transaction object for faster conflict tracking. But the performance is bad.
So I used the instruction "rdtsc" to compare the speed of my skip list and the
original linked list. The skip list was about 1.5x faster.
The interesting thing is that if I added the instruction "rdstc" at the end of
the function "RWConflictExists",
the performance of the whole system was increased by at most 3 times!
Here is the result.
| benchmarks | without rdtsc | with rdtsc |
| simpe read/write | 4.91 | 14.16 |
| ssibench | 9.72 | 10.24 |
| tpcb | 26.45 | 26.38 |
( The simple read/write benchmark has the most number of conflicts. )
The patch is attached. All the difference of the two columns is with/without a
simple line of code:
__asm__ __volatile__ ("rdtsc");
But I don't know why this instruction will influence the performance so much!
BTW, after adding the "rdtsc" instruction, the performance is better than the
original version about 10% at most.
That means, the skip list can work!
Looking forward to your advices.
--
Sincerely
Mengxing Liu
skip-list-for-conflict-tracking.patch
Description: Binary data
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GSOC][weekly report 4] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
In the last week: I added a tpcb benchmark and refactored the test code. It likes a framework now. We can add other benchmarks easily if necessary. https://github.com/liumx10/pg-bench Analyzed the code acquiring SerializableFinishedListLock and provided a new proposal to improve it. My proposal is as below. As I reported in previous emails, lots of backend were blocked by SerializableFinishedListLock in heavy contention. There are only three functions acquiring this lock: SummarizeOldestCommittedSxact: After transforming the conflict information into SLRU format, we need to release this SerailizableXact object. The lock protects the release operation and removing it from the finished list. ReleasePredicateLocks: After releasing the predicate locks of the current transaction, if the transaction is rolled back, we need to release the SerializableXact object; if the transaction is committed, we should insert it to the finished list. The lock protects the release operation or insert operation. ClearOldPredicateLocks: Look through the finished transaction list to find if any transaction object can be released. Thus the lock protects looking through the list, releasing transaction objects, and removing objects from the list. As we can see, the lock protects two things: 1) the finished transaction list 2) releasing serializable transaction objects. Using a single global lock to protect all will cause a lot of contentions. So I decoupled the lock's duty into two parts: protecting the finished transaction list and protecting releasing a single serializable transaction objects. The SerializableFinishedListLock is reserved to protect the finished transaction list. Thus the function SummarizeOldestCommittedSxact and ReleasePredicateLocks are not changed. For function ClearOldPredicateLocks, I scan the list and pick up the transactions which could be released first, but not release these objects directly. After releasing the SerializableFinishedListLock, invoking ReleaseOneSerializableXact to release them. At first, I want to use a partition lock or spinlock in each SerailizableXact object to protect ReleaseOneSerializableXact. But I found it is not necessary to add new locks. in ReleaseOneSerializableXact, firstly, it released all predicate locks, which is protected by SerializablePredicateLockListLock; Then, it released all conflicts, which is protected by SerializableXactHashLock. So I didn't change the function ReleaseOneSerializableXact. I have implemented this idea. But unfortunately, it didn't improve the performance or reduce the contention on SerializableFinishedListLock. I'll try to find out why in the next days. But I'm really looking forward to your advice for my proposal. We can't be too careful to modify the code related to locks. -- Sincerely Mengxing Liu
Re: [HACKERS] [GSOC] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Thanks for your reply.
Actually, the result of without "rdtsc" is reasonable. I used perf to analyze
the performance and found that
even thought the function tracking conflicts (RWConflictExists) was faster, the
function inserting conflicts (SetRWConflict)
was too slower. According to your suggestion, I found there were much more
waiting events of predicate_lock_manager.
That means, slower SetRWConflict resulted in more lock conflicts.
So I took some effort to made it faster in the last days.
Why the code with "rdtsc" is much faster? I thought that may be caused by some
mistakes.
When I changed a machine to run the code, this phenomenon didn't happen
anymore..
-Original Messages-
From: "Robert Haas" <robertmh...@gmail.com>
Sent Time: 2017-07-29 02:46:47 (Saturday)
To: "Mengxing Liu" <liu-m...@mails.tsinghua.edu.cn>
Cc: "Alvaro Herrera" <alvhe...@2ndquadrant.com>, kgrittn <kgri...@gmail.com>,
"pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
Subject: Re: [HACKERS] [GSOC] Eliminate O(N^2) scaling from rw-conflict
tracking in serializable transactions
On Wed, Jul 26, 2017 at 11:41 AM, Mengxing Liu <liu-m...@mails.tsinghua.edu.cn>
wrote:
Hi, all. There was a very strange phenomenon I couldn't explain. So I was
wondering if you can help me.
I was trying to replace the linked list with a skip list in serializable
transaction object for faster conflict tracking. But the performance is bad.
So I used the instruction "rdtsc" to compare the speed of my skip list and the
original linked list. The skip list was about 1.5x faster.
The interesting thing is that if I added the instruction "rdstc" at the end of
the function "RWConflictExists",
the performance of the whole system was increased by at most 3 times!
Here is the result.
| benchmarks | without rdtsc | with rdtsc |
| simpe read/write | 4.91 | 14.16 |
| ssibench | 9.72 | 10.24 |
| tpcb | 26.45 | 26.38 |
( The simple read/write benchmark has the most number of conflicts. )
The patch is attached. All the difference of the two columns is with/without a
simple line of code:
__asm__ __volatile__ ("rdtsc");
But I don't know why this instruction will influence the performance so much!
Lock contention is really expensive, so a slight delay that is just long enough
to prevent the contention from happening can sometimes improve performance.
This example is surprisingly dramatic, though. Of course, we can't commit it
this way -- it will break on non-x86.
I would suggest that you gather information on what wait events are occurring
in the "without rdtsc" case. Like this:
$ script
$ psql
psql=> select wait_event from pg_stat_activity;
psql=> \watch 0.5
...run test in another window...
^C
\q
^D
...use awk or perl or something to count up the wait events and see where the
contention is happening...
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
--
Sincerely
Mengxing Liu
[HACKERS] [GSOC][weekly report 8] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
In the last week, I focused on tuning the performance of skip list and fixed several bugs. 1. As only out-conflicts are checked in RWConflictExists, I removed all modification concerned with in-conflicts; 2. If the conflict list is too short, I inserted an item just like inserting into an ordered linked list, that is, comparing items existing in the list one by one to find the right position. Using skip list is slow when the list is short. 3. Not using the abstract skip list interface; I was afraid that it would bring a little overhead. But results showed that it had no influence. I will roll it back if necessary. Sadly, The performance is not better than the original version. But it's highest one among all efforts I did before. It likes hash table. Tracking conflict is faster but inserting conflicts is slower. In a quick test, cpu cycles consumed by two functions RWConflictExists/SetRWConflict is as below. | | RWConflictExists | SetRWConflict | | linked list | 1.39% | 0.14% | | skip list | 1.15% | 0.35% | According to the suggestions of Alvaro, I'll give a detailed performance report tomorrow. -- Sincerely Mengxing Liu skip-list-for-conflict-tracking.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Re: [GSOC][weekly report 9] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
> From: "Alvaro Herrera" <alvhe...@2ndquadrant.com> > * I wonder why did you settle on a skip list as the best optimization > path for this. Did you consider other data structures? (We don't > seem to have much that would be usable in shared memory, I fear.) > There are three typical alternative data structures: 1) unordered linked list, with O(N) searching and O(1) inserting/removing. 2) tree-like data structures, with O(log(N)) inserting/searching/removing. Skip list just likes a tree. 3) hash table , with O(1) inserting/searching. But constant is much bigger than linked list. Any data structures can be classified into one of data structures above. In PG serializable module, number of conflicts is much smaller than we excepted, which means N is small. So we should be very careful about constants before Big O notation. Sometimes O(N) complexity of linked list is faster than O(1) complexity of hash table. For example, when N is smaller than 5, HTAB is slower than SHM_QUEUE when searching an element. And in all cases, remove operation of hash table is slower than that of linked list, which would result in more serious problem: more contention on SeriliazableFinishedListLock. Skip list is better than HTAB because its remove operation has O(1) complexity. I think any other tree-like data structures won't do better. Shared memory is also the reason why I chose hash table and skip list at the beginning. It's quite difficult to develop a totally new data structure in shared memory, while there were well tested hash table and linked list code already. > * I wonder if a completely different approach to the finished xact > maintenance problem would be helpful. For instance, in > ReleasePredicateLocks we call ClearOldPredicateLocks() > inconditionally, and there we grab the SerializableFinishedListLock > lock inconditionally for the whole duration of that routine, but > perhaps it would be better to skip the whole ClearOld stuff if the > SerializableFinishedListLock is not available? Find out some way to > ensure that the cleanup is always called later on, but maybe skipping > it once in a while improves overall performance. > Yes, that sounds nice. Actually, for a special backend worker, it's OK to skip the ClearOldPredicateLocks. Because other workers will do the clean job later. I'll try it later. > * the whole predicate.c stuff is written using SHM_QUEUE. I suppose > SHM_QUEUE works just fine, but predicate.c was being written at about > the same time (or a bit earlier) than the newer ilist.c interface was > being created, which I think had more optimization work thrown in. > Maybe it would be good for predicate.c to ditch use of SHM_QUEUE and > use ilist.c interfaces instead? We could even think about being less > strict about holding exclusive lock on SerializableFinished for the > duration of ClearOldPredicateLocks, i.e. use only a share lock and > only exchange for exclusive if a list modification is needed. > I read the code in ilist.c but I didn't see too much difference with SHM_QUEUE. Anyway, I'll do a small test to compare the performance of these two data structures. > -- > Álvaro Herrerahttps://www.2ndQuadrant.com/ > PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services -- Sincerely Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GSOC][weekly report 9] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
In the last week, I focus on: 1) Continuing on optimization of skip list. Here is the new logic: At first, I use an unordered linked list to do all inserting/searching operations. When the number of conflicts is more than the threshold, transform the linked list into an ordered skip list. Then all inserting/searching operations are done by the skip list. By this way, for transactions with only a few conflicts, overhead of inserting is O(1). the patch is attached. It helped a little, but just a little. In the end, the skip list has the same performance of the linked list. 2) Studying the performance of less contention on FinishedListLock. I found it can get benefit when the number of conflicts is medium. It is easy to understand the optimization has no influence when conflicts are too rare. But when there are too many conflicts, partition lock will be the new bottleneck and the performance can't be improved. A chart is attached. This optimization can achieve 14% speedup at most. Do you think this optimization can be accepted? -- Sincerely Mengxing Liu skip-list-for-conflict-tracking.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi, Alvaro and Kevin. I'm Mengxing. This is a “synchronization” email to tell you what I've done and my next plan. I'm looking forward to your advice. According to my proposal, I want to prepare the experimental environment during the community bonding period. As this is the first time I discuss with Alvaro, here I will introduce the environment again. My lab have a Lenovo System x3950 X6 machine. https://www.lenovo.com/images/products/system-x/pdfs/datasheets/x3950_x6_ds.pdf More specifically, there are 8 sockets, each has 15 Intel(R) Xeon(R) CPU E7-8870 v2 @ 2.30GHz. Thus we have 120 cores in total. The storage is a 1 TB SSD, with SAS interface, 500MB write bandwidth. OS is ubuntu 14.04. I've compiled & installed PostgreSQL and have tested it by using pgbench. I tuned parameter for database according to http://www.dbdude.com/postgresql/postgresqlperformance.php#BESTPRACTICES For pgbench, I set scale factor (-s) 512. Other configurations are default values. Because we have too many cores, SSD becomes the bottleneck. In my test, pgbench can scale to 36 connections. ( 18 KTPS throughput). CPU utilization is smaller than 30%. Therefore: 1. Is there anything wrong in my tuning parameters？For example, should I close "fsync"? Because we don't care recovery here. 2. Can we use just two sockets (30 physical cores) to run database server? Then the CPU can be the bottleneck so that it shows the problem we try to solve. BTW. Here is the question of Stephen. > What method of communication will be used among the mentors and with > Mengxing. What method do you prefer? > Frequency of status updates (must be at least once a week and more often is > encouraged). How about reporting my status once a week? > What steps will be taken next during the community bonding period. As I wrote in the proposal, I want to establish the environment and read the related source code. Do you have any suggestions for me? -- Mengxing Liu
Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
> From: "Kevin Grittner" <kgri...@gmail.com> > <liu-m...@mails.tsinghua.edu.cn> wrote: > > > "vmstat 1" output is as follow. Because I used only 30 cores (1/4 of all), > > cpu user time should be about 12*4 = 48. > > There seems to be no process blocked by IO. > > > > procs ---memory-- ---swap-- -io -system-- > > --cpu- > > r b swpd free buff cache si sobibo in cs us sy id > > wa st > > 28 0 0 981177024 315036 7084376000 0 900 1 > > 0 99 0 0 > > 21 1 0 981178176 315036 7084378400 0 0 25482 329020 > > 12 3 85 0 0 > > 18 1 0 981179200 315036 7084379200 0 0 26569 323596 > > 12 3 85 0 0 > > 17 0 0 981175424 315036 7084380800 0 0 25374 322992 > > 12 4 85 0 0 > > 12 0 0 981174208 315036 7084382400 0 0 24775 321577 > > 12 3 85 0 0 > > 8 0 0 981179328 315036 7084533600 0 0 13115 199020 > > 6 2 92 0 0 > > 13 0 0 981179200 315036 7084579200 0 0 22893 301373 > > 11 3 87 0 0 > > 11 0 0 981179712 315036 7084580800 0 0 26933 325728 > > 12 4 84 0 0 > > 30 0 0 981178304 315036 7084582400 0 0 23691 315821 > > 11 4 85 0 0 > > 12 1 0 981177600 315036 7084583200 0 0 29485 320166 > > 12 4 84 0 0 > > 32 0 0 981180032 315036 7084584800 0 0 25946 316724 > > 12 4 84 0 0 > > 21 0 0 981176384 315036 7084586400 0 0 24227 321938 > > 12 4 84 0 0 > > 21 0 0 981178880 315036 7084588000 0 0 25174 326943 > > 13 4 83 0 0 > > This machine has 120 cores? Is hyperthreading enabled? If so, what > you are showing might represent a total saturation of the 30 cores. > Context switches of about 300,000 per second is pretty high. I can't > think of when I've seen that except when there is high spinlock > contention. > Yes, and the hyper-threading is closed. > Just to put the above in context, how did you limit the test to 30 > cores? How many connections were open during the test? > I used numactl to limit the test in the first two sockets (15 cores in each socket) And there are 90 concurrent connections. > > The flame graph is attached. I use 'perf' to generate the flame graph. Only > > the CPUs running PG server are profiled. > > I'm not familiar with other part of PG. Can you find anything unusual in > > the graph? > > Two SSI functions stand out: > 10.86% PredicateLockTuple > 3.51% CheckForSerializableConflictIn > > In both cases, most of that seems to go to lightweight locking. Since > you said this is a CPU graph, that again suggests spinlock contention > issues. > > -- Yes. Is there any other kind of locks besides spinlock? I'm reading locks in PG now. If all locks are spinlock, the CPU should be used 100%. But now only 50% CPU are used. I'm afraid there are extra time waiting for mutex or semaphore. These SSI functions will cost more time than reported, because perf doesn't record the time sleeping & waiting for locks. CheckForSerializableConflictIn takes 10% of running time. (refer to my last email) -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Thank you very much! I follow your advice and here is the result. SerializableXactHashLock 73 predicate_lock_manager 605 WALWriteLock 3 SerializableFinishedListLock 665 There are more than 90 events each time. SerializableXactHashLock/SerializableFinishedListLock are both used in SSI. I think that's why PG is so slow in high contention environment. > -Original Messages- > From: "Robert Haas" <robertmh...@gmail.com> > Sent Time: 2017-06-08 01:30:58 (Thursday) > To: "Mengxing Liu" <liu-m...@mails.tsinghua.edu.cn> > Cc: kgrittn <kgri...@gmail.com>, "Alvaro Herrera" <alvhe...@2ndquadrant.com>, > "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > Subject: Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from > rw-conflict tracking in serializable transactions > > On Tue, Jun 6, 2017 at 12:16 PM, Mengxing Liu > <liu-m...@mails.tsinghua.edu.cn> wrote: > > I think disk I/O is not the bottleneck in our experiment, but the global > > lock is. > > A handy way to figure this kind of thing out is to run a query like > this repeatedly during the benchmark: > > SELECT wait_event_type, wait_event FROM pg_stat_activity; > > I often do this by using psql's \watch command, often \watch 0.5 to > run it every half-second. I save all the results collected during the > benchmark using 'script' and then analyze them to see which wait > events are most frequent. If your theory is right, you ought to see > that SerializableXactHashLock occurs as a wait event very frequently. > > -- > Robert Haas > EnterpriseDB: http://www.enterprisedb.com > The Enterprise PostgreSQL Company > > > -- > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] [GSOC][weekly report 3] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
> From: "Heikki Linnakangas" <hlinn...@iki.fi> > > Hmm. The hash table ought to speed up the RWConflictExists() function > right? Where in the flame graph is RWConflictExists()? If it only > accounts for a small amount of the overall runtime, even drastic speedup > there won't make much difference to the total. > Yes. It is much smaller than we have expected. I did a small test for HTAB and linked list: when the set size is smaller than 10, linked list is as quick as HTAB. Here is the result. (x microseconds running 10 million searching) setSize: 5, LIST: 423569, HTAB: 523681 setSize: 10, LIST: 540579, HTAB: 430111 setSize: 15, LIST: 752879, HTAB: 429519 setSize: 20, LIST: 940792, HTAB: 431388 setSize: 25, LIST: 1163760, HTAB: 446043 setSize: 30, LIST: 1352990, HTAB: 429057 setSize: 35, LIST: 1524097, HTAB: 431547 setSize: 40, LIST: 1714976, HTAB: 429023 As we can see, the hash table can only benefit in a very extreme situation. However, even if there are 100 concurrent connections, the average length of conflict list is about 10. linked list is not the bottleneck. > > Nope, there is no such function, I'm afraid. > Oh, that's really a bad news. > > In a previous email, I reported that many backends wait for the lock > > “SerializableFinishedListLock”; > > If we don't implement functions like “ReleaseOneSerializableXact” quickly, > > they will be the bottleneck. > > Yeah, that's probably what's causing the decrease in throughput you're > seeing. > An new evidence: I use "SELECT wait_event_type, wait_event FROM pg_stat_activity;" and sum by event_type to analyze the wait event. The result of original version: SerializableXactHashLock 27 predicate_lock_manager 512 WALWriteLock 3 SerializableFinishedListLock 402 The result of new version: SerializableXactHashLock 38 predicate_lock_manager 473 WALWriteLock 3 SerializableFinishedListLock 1068 Obviously, more backends are blocked by SerializableFinishedListLock. > > You might need to also keep the linked lists, and use the hash table to > only look up particular items in the linked list faster. > > I was surprised to see that you're creating a lot of smallish hash > tables, three for each PredXact entry. I would've expected all the > PredXact entries to share the same hash tables, i.e. have only three > hash tables in total. That would be more flexible in allocating > resources among entries. (It won't help with the quick-release, though) > Yes, it would looks more elegant and require less memory resources. ( because hash table objects also consume memory ) But just for performance, it would be less efficient than my patch. Because it has to maintain linked lists, besides hash tables. In other words, it does more works than my patch. Another point is that removing linked list may have more opportunities to reduce lock contentions. Otherwise, we need a global lock to protect the linked list. -- Sincerely Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi, Alvaro and Kevin. > Anyway, this is just my analysis. > So I want to hack the PG and count the conflict lists' size of transactions. > That would be more accurate. In the last week, I hacked the PG to add an additional thread to count RWConflict list lengths. And tune the benchmark to get more conflict. But the result is still not good. > > > > > Yeah, you need a workload that generates a longer conflict list -- if > > you can make the tool generate a conflict list with a configurable > > length, that's even better (say, 100 conflicts vs. 1000 conflicts). > > Then we can see how the conflict list processing scales. > > > > Yes, I tried to increase the read set to make more conflicts. > However the abort ratio will also increase. The CPU cycles consumed by > conflict tracking are still less than 1%. > According to the design of PG, a transaction will be aborted if there is a > rw-antidependency. > In this case, a transaction with a longer conflict list, is more possible to > be aborted. > That means, the conflict list doesn't have too many chances to grow too long. > To solve this problem, I use just two kinds of transactions: Read-only transactions and Update-only transactions. In this case, no transaction would have an In-RWconflict and an Out-RWconflict at the same time. Thus transactions would not be aborted by conflict checking. Specifically, The benchmark is like this: The table has 10K rows. Read-only transactions read 1K rows and Update-only transactions update 20 random rows of the table. In this benchmark, about 91% lists are shorter than 10; lengths of 6% conflict lists are between 10 and 20. Only 2% lists are longer than 20. The CPU utilization of CheckForSerializableConflictOut/In is 0.71%/0.69%. I tried to increase the write set. As a result, conflict list become longer. But the total CPU utilization is decreased (about 50%). CPU is not the bottleneck anymore. I'm not familiar with other part of PG. Is it caused by LOCK? Is there any chance to get rid of this problem? BTW, I found that the email is not very convenient, especially when I have some problem and want to discuss with you. Would you mind scheduling a meeting every week by Skye, or other instant message software you like? I would not take you too much time. Maybe one hour is enough. Sincerely. -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
> -Original Messages- > From: "Kevin Grittner" <kgri...@gmail.com> > Sent Time: 2017-06-03 01:44:16 (Saturday) > To: "Alvaro Herrera" <alvhe...@2ndquadrant.com> > Cc: "Mengxing Liu" <liu-m...@mails.tsinghua.edu.cn>, > "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > Subject: Re: Re: Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from > rw-conflict tracking in serializable transactions > > > Mengxing Liu wrote: > > >> The CPU utilization of CheckForSerializableConflictOut/In is > >> 0.71%/0.69%. > > How many cores were on the system used for this test? The paper > specifically said that they didn't see performance degradation on > the PostgreSQL implementation until 32 concurrent connections with > 24 or more cores. The goal here is to fix *scaling* problems. Be > sure you are testing at an appropriate scale. (The more sockets, > cores, and clients, the better, I think.) > > I used 15 cores for server and 50 clients. I tried 30 cores. But the CPU utilization is about 45%~70%. How can we distinguish where the problem is? Is disk I/O or Lock ? > On Fri, Jun 2, 2017 at 10:08 AM, Alvaro Herrera > <alvhe...@2ndquadrant.com> wrote: > > > Kevin mentioned during PGCon that there's a paper by some group in > > Sydney that developed a benchmark on which this scalability > > problem showed up very prominently. > > https://pdfs.semanticscholar.org/6c4a/e427e6f392b7dec782b7a60516f0283af1f5.pdf > > "[...] we see a much better scalability of pgSSI than the > corresponding implementations on InnoDB. Still, the overhead of > pgSSI versus standard SI increases significantly with higher MPL > than one would normally expect, reaching around 50% with MPL 128." > Actually, I implemented the benchmark described in the paper at first. I reported the result in a previous email. The problem is that the transaction with longer conflict list is easier to be aborted, so the conflict list can not grow too long. I modify the benchmark by using Update-only transaction and Read-only transaction to get rid of this problem. In this way, dangerous structure will never be generated. > "Our profiling showed that PostgreSQL spend 2.3% of the overall > runtime in traversing these list, plus 10% of its runtime waiting on > the corresponding kernel mutexes." > Does "traversing these list" means the function "RWConflictExists"? And "10% waiting on the corresponding kernel mutexes" means the lock in the function CheckForSerializableIn/out ? > If you cannot duplicate their results, you might want to contact the > authors for more details on their testing methodology. > If I used 30 cores for server, and 90 clients, RWConflictExists consumes 1.0% CPU cycles, and CheckForSerializableIn/out takes 5% in all. But the total CPU utilization of PG is about 50%. So the result seems to be matched. If we can solve this problem, we can use this benchmark for the future work. Sincerely -- Mengxing Liu -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] [GSOC] [Weekly report 2] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi, all. In the last week, I replaced linked list with hash table in SerializableXact. I only replace inConflicts and outConflicts. The other linked lists, such as possibleUnsafeConflicts, I will modify them after other things work well. There are still some bugs: the abort rate is much higher than before (from 11.3% to 72%). I'll figure out what's wrong in the next few days. My design is as follow: For hash table, key is the pointer of SerializableXact; Value is the RWConflictData object. Hashcode is generated based on the SerializableXact pointer. So, given a SerializableXact, we can quickly find if it is conflict with another SerializableXact. Every SerializableXact has two tables: inConflictsTab and outConflictsTab. They are allocated and initialized when creating PredXactList (in the function InitPredicateLocks). When a SerializableXact object is released, it will release all its RWConflict objects, the hash tables are empty again. Thus They can be reused directly after releasing. NOTE: I stored RWConflictData in hash tables, instead of RWConflict object allocated by RWConflictPool. After I remove other linked lists, the RWConflictPool can be omitted. My code is on the : https://github.com/liumx10/postgresql/commit/3fd9a7488de5ae19ce2ce19eae5f303153a079ff There are 3 main modifications in summary: 1) Initializing hash table. Related functions: InitPredicateLocks 2) Setting, releasing and checking RWConflicts. Related functions: RWConflictExists, SetRWConflict, ReleaseRWConflict 3) There are some functions scanning all RWConflict in a SerializableXact. Related functions: ReleasePredicateLocks, ReleaseOneSerializableXact, CheckForSerializableConflictOut, CheckForSerializableConflictIn, OnConflict_CheckForSerializationFailure, PreCommit_CheckForSerializationFailure Sincerely -- Mengxing Liu
Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from rw-conflict tracking in serializable transactions
Hi, Kevin and Alvaro. I think disk I/O is not the bottleneck in our experiment, but the global lock is. For disk I/O, there are two evidences: 1) The total throughput is not more than 10 Ktps. Only a half are update transactions. An update transaction modifies 20 tuples; each tuple's size is about 100B. So the data written to the disk should be less than 10MB per second. Even we take write-ahead log in consideration (just double it), the data should be less than 20MB/s. I replaced ramdisk with SSD, and "iostat" shows the same result, while our SSD's sequential write speed is more than 700MB/s. 2) I changed isolation level from "serializable" to "read committed". As the isolation requirement becomes looser, throughput is increased. But in this case, the CPU utilization is nearly 100%. (It's about 50% in serializable model) Therefore, disk I/O is not the bottleneck. For the lock: I read the source code in predicate.c; I found many functions use a global lock: SerializableXactHashLock. So there is only one process on working at any time! As the problem of CPU not being fully used just happened after I had changed isolation level to "serailizable", this global lock should be the bottleneck. Unfortunately, "perf" seems unable to record time waiting for locks. I did it by hand. Specifically, I use function "gettimeofday" just before acquiring locks and after releasing locks. In this way, I found function CheckForSerializableIn/CheckForSerializableOut takes more than 10% of running time, which is far bigger than what reported by perf in the last email. If my statement is right, it sounds like good news as we find where the problem is. Kevin has mentioned that the lock is used to protect the linked list. So I want to replace the linked list with hash table in the next step. After that I will try to remove this lock carefully. But in this way, our purpose has been changed. O(N^2) tracking is not the bottleneck, the global lock is. By the way, using "gettimeofday" to profile is really ugly. Perf lock can only record kernel mutex, and requires kernel support, so I didn't use it. Do you have any good idea about profiling time waiting for locks? > -Original Messages- > From: "Mengxing Liu" <liu-m...@mails.tsinghua.edu.cn> > Sent Time: 2017-06-05 00:27:51 (Monday) > To: "Kevin Grittner" <kgri...@gmail.com> > Cc: "Alvaro Herrera" <alvhe...@2ndquadrant.com>, > "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org> > Subject: Re: Re: [HACKERS] Re: [GSOC 17] Eliminate O(N^2) scaling from > rw-conflict tracking in serializable transactions > > > > > > -Original Messages- > > From: "Kevin Grittner" <kgri...@gmail.com> > > > > I tried 30 cores. But the CPU utilization is about 45%~70%. > > > How can we distinguish where the problem is? Is disk I/O or Lock? > > > > A simple way is to run `vmstat 1` for a bit during the test. Can > > you post a portion of the output of that here? If you can configure > > the WAL directory to a separate mount point (e.g., use the --waldir > > option of initdb), a snippet of `iostat 1` output would be even > > better. > > "vmstat 1" output is as follow. Because I used only 30 cores (1/4 of all), > cpu user time should be about 12*4 = 48. > There seems to be no process blocked by IO. > > procs ---memory-- ---swap-- -io -system-- > --cpu- > r b swpd free buff cache si sobibo in cs us sy id wa > st > 28 0 0 981177024 315036 7084376000 0 900 1 0 > 99 0 0 > 21 1 0 981178176 315036 7084378400 0 0 25482 329020 12 > 3 85 0 0 > 18 1 0 981179200 315036 7084379200 0 0 26569 323596 12 > 3 85 0 0 > 17 0 0 981175424 315036 7084380800 0 0 25374 322992 12 > 4 85 0 0 > 12 0 0 981174208 315036 7084382400 0 0 24775 321577 12 > 3 85 0 0 > 8 0 0 981179328 315036 7084533600 0 0 13115 199020 6 > 2 92 0 0 > 13 0 0 981179200 315036 7084579200 0 0 22893 301373 11 > 3 87 0 0 > 11 0 0 981179712 315036 7084580800 0 0 26933 325728 12 > 4 84 0 0 > 30 0 0 981178304 315036 7084582400 0 0 23691 315821 11 > 4 85 0 0 > 12 1 0 981177600 315036 7084583200 0 0 29485 320166 12 > 4 84 0 0 > 32 0 0 981180032 315036 7084584800 0 0 25946 316724 12 > 4 84 0 0 > 21 0 0 981176384 315036 7084586400 0 0 24227 321938 12 > 4 84 0 0 >
