0

This is part of parking lot interview question where candidate are asked to design parking lot system. Designing entities for parking lot is fairly discussed problem. But I am stuck on a part where We have to assign a parking spot to a Vehicle.

Lets say we are implementing parking lot problem with external datastore. And there are many concurrent requests, requesting for a parking space. The very basic implementation is,

  1. Create separate database row for each parking slot, with column availability true/false.

  2. Whenever a vehicle comes, find one available slot (lets say slot id X)

  3. Update the DB 's availability as false with optimistic locking ( i.e. UPDATE if slotid=X and availability =false)

The above approach will not work well in high concurrency scenarios since same slot would might be allocated for multiple vehicle and step3 would fail for all those vehicles and we would have to retry from step 2 again.

To optimally process this, i should be merging step 2, 3 and offload the assignment to DB itself. And the new flow should look like below

  1. Create separate database row for each parking slot, with column availability true/false.
  2. Whenever a vehicle comes, fire sql query to find a row and update availability to false. And return the slotid to vehicle?

Is it possible to this in SQl DBs? Are there other approaches to achieve this functionality.

1 Answer 1

2

Depending on your DBMS, you can do something like this:

UPDATE table1 
SET availability = false 
WHERE availability = true 
LIMIT 1                     /* Find only the first available entry */ 
RETURNING id;               /* Return the id of that entry to the application */ 

Other DBMSes will have other ways of doing the same thing.
Worst case, you have to do it the hard way, but that might involve using an intermediate value for availability:

BEGIN TRANSACTION ; 

UPDATE table1 
SET availability = 'candidate' 
WHERE availability = 'free' 
LIMIT 1 ; 

SELECT id 
from table1 
WHERE availability = 'candidate' ; 

UPDATE table1 
SET availability = 'occupied' 
WHERE availability = 'candidate' ;

COMMIT ; 
10
  • Slick single atomic statement for the first part of the answer. I like it.
    – J.D.
    Jan 17 at 14:07
  • @J.D.@phill the lock would be only for one selected row? since all the first query might return same row till its value is updated, is it possible to randomise the row? so that contention can be minimised? Jan 18 at 6:01
  • i could not find any resource discussing these problems, it would immensely help if you can share some doc as well. Jan 18 at 6:01
  • i came across skip lock and it looks promising. percona.com/blog/using-skip-lock-for-queue-processing-in-mysql Jan 18 at 9:29
  • 1
    @bestwishes "the lock would be only for one selected row?" - The first part of the answer works because the statement is atomic. In other words, it does everything in a single statement - updates the row and returns the ID of the row that was updated. This means it's not possible for someone else to update or get the ID of the same row, regardless of how concurrent another instance of this query ran. Locking is an implementation detail and depends on the exact database system you're using. But generally only a row level lock should be taken for this atomic statement.
    – J.D.
    Jan 18 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.